기본 재귀함수

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

 

A:

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

 solution(3); //3,2,1

이렇게 호출을 하게 되면 3,2,1이라는 답이 반환된다. 그럼 어떻게 1,2,3으로 반환을 할까

function solution(n) {
  function DFS(L) {
    if (L === 0) return;
    else {
      DFS(L - 1);  //위 아래 위치 변경
      console.log(L);
    }
  }

  DFS(n);
}

solution(3); //1,2,3

위의 결과 그림으로 설명

함수는 호출이 되면 stack frame에 쌓이게 된다.

그러면 먼저 3을 호출받은 DFS(3)이 12번줄(vscode에서는 12번째 줄에 위치)에서 다시 DFS(2)가 호출되고 그 자리에서 대기가 된다.

이런 방법으로 쭉 stack에 쌓이면 파란색과 같은 모습으로 보일 수 있는데

여기서 return이 시작되면 맨 위에꺼 부터 pop되기 시작한다.

그래서 DFS(1)부터 시작하면 대기하고 있던 12번째줄 부터 시작을 하고 바로 밑에 console.log(L)이 실행되면 1,2,3과 같은 호출결과를 볼 수 있다.

 ** 간단하지만 꼭 알아 두어야 할 재귀함수 이론이므로 기록함.