[자바스크립트] 재귀함수와 스택 프레임(Stack Frame)

 

알고리즘을 풀다보면 항상 나를 괴롭혔던 재귀함수! 이제는 정말 쉽게 풀어보고 싶은 마음에 재귀함수 문제를 연습하다가 스택 프레임에 대해 여지까지 제대로 알지 못했다는 내 자신을 발견하고 정리를 해두려고 한다. 

 

스택 프레임(Stack Frame)

---

• 스택 영역: 함수의 호출과 관계되는 지역 변수, 매개 변수가 저장되는 영역이다. 함수가 호출되면서 할당되고, 함수가 종료되면 소멸된다. 
• 스택 프레임: 함수가 호출되면 스택에 함수의 지역 변수, 매개 변수, 복귀 주소 등이 입력된다. 스택 영역에 저장되는 함수의 정보가 스택 프레임이다. 

 

728x90

예제

---

간단한 재귀함수를 이용한 예제를 가져왔다.

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

  DFS(n);
}

solution(3); // 1 2 3

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

  DFS(n);
}

solution(3); // 3 2 1

위의 예제의 다른 점은 console.log(L)의 위치다. 즉, 재귀함수를 호출한 후와 호출하기 전 위치에 따라 출력 결과가 다른 것을 확인할 수 있다. 

반응형

그 이유는 재귀함수는 호출될 때마다 스택 영역에 스택 프레임을 저장하고, 스택 프레임에 저장된 복귀 주소를 기억해 두기 떄문이다. 

다시 말해, 첫 번째 예제를 보면 DFS(3)은 DFS(2)를 호출하게 되는데 이때 다시 돌아올 주소를 기억해두는 것이다.