재귀 함수에 대하여.
컴퓨터 과학에 있어서 재귀(再歸, Recursion)는 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻하며, 이를 프로그래밍에 적용한 재귀 호출(Recursive call)의 형태로 많이 사용된다. 또 사진이나 그림 등에서 재귀의 형태를 사용하는 경우도 있다. -wikipidia.
쉽게 말해, 어떠한 문제를 해결할때 자기 자신을 재참조하게끔 만들어, 문제를 보다 쉽게 해결하게 만드는 방법.
간단하게,
재귀의 장점은 사람이 이해하기 쉽다. 또한, 무수한 반복문을 쉽게 처리할 수 있다.
재귀의 단점은 컴퓨터가 이해하기 어렵다. 또한, memory leak 이 발생 될 수 있다.
재귀 함수를 이해하기란 그렇게 어렵지 않다. 하지만 여기서 Call stack 에 대한 개념을 좀 단단하게 하고 넘어가야 할 것같다.
Call stack.
Call Stack은 여러 함수를 호출하는 상황에서 해당 위치를 추적하는 자바스크립트 엔진을 위한 메커니즘입니다. 현재 어떤 함수가 동작하고 있는지, 그 함수 내에서 어떤 함수가 호출되는지, 다음에 어떤 함수가 호출되어야 하는지 등을 추적합니다.
Call stack 제어 원리.
- 함수 A가 호출될 경우 해당 함수가 Call stack에 쌓인다.
- 함수 A에 의해 호출된 함수 B가 1번에서 호출된 A stack 위에 쌓인다.
- 함수 실행이 종료될 경우, 종료된 함수는 Call stack에서 제외된다. B가 실행이 종료되면, A함수는 B함수가 실행이 종료되길 기다렸다가 실행됨.
- 이 과정에서 stack이 과도하게 쌓일 경우 maximum call stack error 가 뜸.
아래의 함수는 피보나치 수열을 재귀함수로 만든 것이다. 이를 크롬 브라우저에서 디버그 해보면, Call stack 의 의미를 조금 이해하기 쉬울 것이다.
function rabbits(n) {
if (n === 0) {
return 0;
}
if (n === 1) {
return 1;
}
return rabbits(n - 1) + rabbits(n - 2);
}
debugger;
rabbits(3);아래 그림은
함수가 호출되기전의 상황이다. 호출 스택엔 아무것도 없다.
함수가 호출되고 호출스택에 rabbits가 하나 추가된게 보일것이다. n 값으로 3이 들어갔으니 n=3 인자를 갖는 rabbit 함수가 호출되고 Call stack에 하나 쌓인다. 아래 그림에 갈색 배경의 n = 3인 부분이 첫번째 콜스택이 진행중인 상황을 말해주고, if 조건문에 걸리지 않으니, 자연스럽게 return rabbits(n-1) + rabits(n-2)가 실행됨.
여기서 중요한건, 함수는 왼쪽부터 실행되기때문에, rabbits(n-1) 함수가 먼저 실행됨.
아래의 그림에서 호출 스택을 보면 하나가 쌓인게 보인다. 이는 n=3일때 rabbits(n-1)에서 rabbits(2)로 호출된 함수의 스택이다. 이 호출 스택 밑에 있는 스택은 맨 처음 스택이다.
n=2일때도 마찬가지로 조건문과 걸리는 것이 없기 때문에 다시 rabbits(n-1) + rabits(n-2)로 오는것을 볼 수있다. 이 또한 rabbits(n-1)이 먼저 실행되므로, rabbits(1)이 다시 호출된다.
아래의 그림을 보면, 이전 호출에서 rabbits(1)이 호출됬으므로 n=1이 되었고, 호출스택 또한 하나 더 쌓인 모습을 볼 수 있다. 조건문에 n=1일때 조건이 있으므로 거기에서 1이 리턴이 된다. 이는 다음 스샷에서 볼 수 있다.
아래의 스샷에서 보이듯, n=1일때의 조건에 걸리기 때문에 반환값 1을 리턴해 주는데, 여기서 함수의 리턴값은 함수를 실행할때의 코드를 찾아간다. 즉, 현재 함수가 실행됬을떄 함수는 n=2일때 첫번째 함수 rabbits(n-1)에 들어간 rabbits(1)이 된다.
n=2일때 왼쪽 함수 rabbits(n-1)의 함수 실행이 종료 됬으므로, 다시 호출 스택은 2개가 되었고, 이제 오른쪽 rabbits(n-2) 함수 실행을 해야한다. 스택은 하나 더 쌓일태고 n=0인 rabbits(0)이 호출된다.
아래 스샷에서 보이듯 n=0일때, 그리고 호출스택이 하나 추가됬을때이다. 조건문에 N===0 조건이 있기 때문에, return 값으로 0을 리턴해주고 이 함수는 n=2일때의 오른쪽 rabbits(n-2)함수 이다.
N=2일때 왼쪽과 오른쪽 함수를 모두 호출하여 완료했다. 함수를 리턴한 순간 콜스택은 사라지고, N=3일때 왼쪽 rabbits함수의 처리를 완료했다. 반환 값은 1 이고, 이제 나머지 오른쪽 함수를 처리해야함.
아래 스샷처럼, n=3일때, 오른쪽 rabbits(n-2) 함수를 호출해 줘야한다. 이때의 호출 스택은 n=3일때 밖에 없다는 점을 명심하자. rabbits(1)로 호출된다. 콜스택도 하나 더 쌓일것이다.
rabbits(1)이 실행되므로, 콜스택에 rabbits 스택이 하나 쌓이고, n=1일때의 조건문에 걸리게 된다. n===1일때 1을 리턴해주므로, n=3일때 오른쪽 함수 rabbits(1)의 값은 1이된다.
아래 스샷에 호출 스택이 1개 없어지고, return 반환값이 더해진 상태가 나온다. return 값이 나오면, 호출은 사라지게되고 해당 함수 결과값이 return 값이 된다.즉, 이제 남은 스택은 1개이고 그것은 처음 15번째 줄에있는 Rabbits(3)함수다.
아래 스샷은 최종적으로 호출 스택이 다 사라지게 된 모습을 볼 수 있다.
이렇든 간단한 피보나치 수열도 상당히 많은 스택과 함수 호출이 일어난다. 재귀가 많아지면 많아질 수록, 함수의 호출과 콜스택의 갯수가 많아지게 되기 때문에 무수히 많은 재귀를 사용하면, memory Leak 이 발생 할 수 밖에 없을 것이다.
Reference
wikipidia
