아래는 1부터 n까지의 숫자를 순서대로 출력하는 재귀함수의 예시이다.
function printNumber(n){
function DFS(L){
if(L==0) return;
else{
DFS(L-1)
console.log(L)
}
}
DFS(n)
}
printNumber(3)
위 코드는 DFS(3)-DFS(2)-DFS(1)-return(종료)-console.log(1)-console.log(2)-console.log(3) 순서대로 동작한다. DFS(1)까지 간 후 함수가 종료되면 그 다음의 console.log()가 순차적으로 실행되고 함수가 순서대로 종료되는 것이다.
이러한 동작은 함수 호출 시 함수의 지역변수, 매개변수, 복귀 주소 등이 저장되는 공간인 스택 프레임을 이용해 이루어진다.
함수가 호출되면 스택에 함수의 매개변수, 호출이 끝난 뒤 돌아갈 복귀 주소값, 함수의 지역변수 등이 저장된다. 이렇게 스택에 차례대로 저장되는 함수의 호출 정보를 스택 프레임이라고 한다. 재귀 함수도 함수이므로 호출 정보가 스택 프레임에 저장된다.
스택 = [{함수정보},{함수정보},{함수정보}...]
함수가 return을 하는 순간 스택 프레임에서는 pop이 일어나고 함수는 종료된다. 종료된 함수는 스택에서 사라지고, 해당 함수의 복귀 주소로 실행이 넘어간다.
위 예제의 재귀 함수의 스택프레임은 아래와 같이 동작한다.
순서대로 동작하다보면 console.log()는 1-2-3의 순서로 숫자를 출력하게 된다.
만약 역순으로 출력하고 싶다면, console.log()의 위치를 함수를 호출하는 위치의 위로 옮기면 된다. 콘솔 출력 후 자신을 호출하기 때문에 3-2-1 순서로 출력하게 된다.