재귀 함수와 스택 프레임(Stack Frame)

재귀 함수

 

재귀 함수는 함수가 직, 간접적으로 자신을 호출하는 프로세스이다.
반복적인 호출이 필요한 문제를 해결할 때 사용하고, 종료 시점을 유의해야 한다. 종료 시점을 신경 쓰지 않으면 무한 호출에 빠지게 된다.

 

---

스택 프레임(Stack Frame)

 

스택(Stack) 영역은 함수의 호출과 관계되는 지역 변수, 매개 변수가 저장되는 영역으로, 해당 영역은 함수가 호출되면서 할당되고, 함수가 종료되면 소멸된다.

 

함수가 호출되면 스택에 함수의 매개 변수, 지역 변수, 복귀 주소 등이 입력된다. 이렇게 스택 영역에 저장되는 함수의 정보를 스택 프레임(Stack Frame)이라고 한다.

 

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

console.log(solution(3)); // 1,2,3

 

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

console.log(solution(3)); // 3,2,1

 

위 예제에서 다른 곳은 console.log(L)의 위치다. DFS()함수를 재귀적으로 호출하기 이후와 이전에 위치하고 있는데 출력이 달라지게 된다.

첫번째 예시에서 DFS(3)은 DFS(2)를 호출하고, 다시 돌아올 주소를 기억해 둔다(돌아올 주소는 console.log(L);). DFS(2)도 마찬가지로 DFS(1)을 호출하고, 돌아올 주소를 기억해 둔다. 마지막으로 DFS(1)도 DFS(0)을 호출하고, 돌아올 주소를 기억해 둔다. DFS(0)은 if 조건문에 의해 함수가 종료된다. DFS(0)은 스택 영역에서 사라지게 되고, DFS(1)의 복귀 주소로 돌아오게 된다. 따라서 DFS(1)은 다음 할 일인 console.log(1)을 출력하게 된다. 그리고 DFS(1)도 스택 영역에서 소멸되고, 나머지 DFS(2), DFS(3)의 할 일을 수행하게 된다.

두번째 예시도 위 같이 동작하는데, 코드의 순서가 바뀌어 다음 함수를 호출하기 이전에 출력부터 하게 되어 둘의 출력에 차이가 발생하게 된다.