[Algorithm] 재귀함수 개념과 동작방식

1. 재귀함수

재귀함수는 자기 자신을 호출하는 함수를 말한다.

반복문을 조금 더 간결한 코드로 풀어낼 때 사용한다.

스스로를 호출하는 함수이기 때문에 반드시 종료조건을 써줘야 하며, 무한루프 되지 않도록 주의해야 한다.

 

 

1) 재귀함수 구현(자바스크립트)

자연수 N이 입력되면 재귀함수를 이용하여 1부터 N까지 출력하는 프로그램을 작성하세요.

function solution(n){
    function DFS(L){
        if(L === 0) return;
        else {
            DFS(L-1);
            conosle.log(L);
        }
    }
}

//1, 2, 3

 

자바스크립트에서 재귀함수를 구현하는 방법은 간단하다.

자기 자신을 호출하는 함수를 사용하면 된다.

 

위 예시를 살펴보면 DFS 함수 내에서 스스로를 호출한 것을 확인할 수 있다.

호출하는 즉시 해당 함수가 다시 실행된다.

 

단, 재귀함수를 사용할 때에는 반드시 종료조건과 다른 입력값을 넣어야 한다는 두 가지 조건을 만족해야 한다.

종료 조건은 재귀함수가 멈추는 조건을 의미하고, 다른 입력값은 함수 호출 시 매번 다른 데이터가 입력되어야 함을 의미한다.

 

 

2) 동작방식 

DFS(L-1);
conosle.log(L); 
//123

conosle.log(L);
DFS(L-1);
//321

 

위 예시처럼 재귀함수를 사용하면, 위치를 어떻게 하냐에 따라 출력값이 달라지기도 한다.

따라서 재귀함수를 사용할 때는, 어떻게 함수가 동작하는지 아는 것이 중요하다.

 

우선, 함수를 호출하게 되면 해당 함수의 정보가 담겨 있는 실행 컨텍스트가 생성된다.

해당 컨텍스트에는 함수가 실행될 수 있는 환경과 그 결과가 저장된다.

 

함수가 중첩되어 호출되면, 현재 실행 중인 함수는 정지되고 실행콘텍스트는 스택 자료구조에 저장된다.

 

 

아까 작성했던 예시를 통해 설명해 보면, DFS 함수를 호출하는 즉시 동작이 멈추고 해당 함수는 스택에 쌓이게 된다.

따라서 함수 호출 아래에 있는 코드들은 실행되지 않고, 다음 함수를 실행한다.

위 그림의 첫 번째 처럼 함수가 쌓이는 것이다.

 

그 후, DFS(1) 함수가 실행되어서 스택에서 빠져나가게 되면, 그다음 함수인 DFS(2)가 실행된다.

이때 아까 실행하지 못했던 함수 호출 이후의 코드(conosle.log(L))가 실행된다.

 

DFS(L-1);
conosle.log(L); 
//123

 

console.log(L)은 위에 쌓인 함수부터 차례로 실행되므로 1, 2, 3 순서대로 출력된다. 

 

 

*주의할 점

 

실행 컨텍스트는 그 개수만큼 실행 컨텍스트가 저장될 메모리 공간이 필요하다.

반복문의 경우 하나의 실행 컨텍스트가 생성되기 때문에 사용하는 메모리 공간이 고정된다.

 

그러나 재귀함수는 n번 반복될 때마다 n개의 실행컨텍스트가 생성되기 때문에 그만큼 메모리가 늘어나게 된다.

따라서 재귀함수를 사용할 땐, 메모리 요구사항에 유의해야 한다. 

 

 

3) 예시

이번엔 재귀함수를 이용한 다른 예시를 살펴보자.

10진수 N이 입력되면 2진수로 변환하여 출력하는 프로그램을 작성하세요. 단 재귀함수를 이용해서 출력해야 합니다.

function solution(n) {
    let answer = '';

    function DFS(num) {
        if (num === 0) return
        else {
            DFS(Math.floor(num / 2))
            answer += String(num % 2);
        }
    }

    DFS(n)
    return answer;
}

console.log(solution(11));
//1011

 

10진수를 2진수로 변환하기 위해선 몫이 1이 될 때까지 해당 값을 2로 계속해서 나눠주면 된다.

따라서 num을 2로 나눈 값을 매개변수로 넣어서 함수를 계속해서 호출해 준다.

이때 나머지는 있으면 안 되므로 Math.floor 함수를 사용해 준다.

 

맨 마지막 몫까지 answer에 추가해야 하기 때문에 종료조건은 num === 0으로 설정해 준다. 

 

num%2를 통해 나머지를 answer에 추가해 준다.

뒤에서부터 나머지를 추가해줘야 하기 때문에 해당 코드는 반드시 함수 실행 이후에 있어야 한다.

만일, 함수 실행 이전에 코드를 작성한다면 거꾸로 된 답이 출력된다.

 

 

 

* 10진수를 2진수로 변환하는 방법

 

10진수 값을 몫이 1이 될 때까지 2로 나눠준 후, 나머지값을 출력한다.

 

ex) 11

11/2 = 1

5/2 = 1

2/2 = 0

1

> 1011