재귀란?
프로그래밍에서 재귀(Recursion)란 자신을 정의할 때 자기 자신을 재참조하는 것을 말한다. 따라서 재귀 함수란 함수가 호출되어 실행할 때, 함수 내부에서 자기 자신을 다시 호출하는 재귀 호출(Recursive call)의 형태를 말한다.
Recursive vs Iterative
보통 Recursive와 Iterative가 많이 비교되곤 한다. Iterative는 '반복적인'이란 뜻을 가지고 있다. 즉, 우리가 흔히 사용하는 for문이나 forEach문과 같은 반복 연산을 가리킨다. 항상 그런 것은 아니지만 많은 경우에 Recursion으로 처리할 수 있는 문제는 Iterator로도 처리할 수 있고, 반대로 Iterator로 처리할 수 있는 것은 Recursion으로 처리할 수 있다. 어떤 방법으로 문제를 해결하느냐는 프로그래머의 마음이지만 때로는 Iterative 코드보다 Recursive 코드를 사용했을 때 더 이해하기 쉬운 코드가 될 때가 있다. 그러므로 우리는 두 가지 방법을 모두 명확하게 알고 있어야 한다.
팩토리얼 (Factorial) 구하기
재귀 함수를 설명할 때 가장 많이 등장하는 예제 코드가 바로 팩토리얼 구하기이다. 팩토리얼이란 자기 자신부터 시작해서 1 감소한 숫자들을 곱한 값이다. 예를 들어서 5!은 5 4 3 2 1 = 120이다.
function factorial (n) {
var result = 1;
for (var i = n; i >= 1; i--) {
result *= i;
}
return result;
}
n부터 1까지의 수를 반복하여 result 변수에 곱한다. 곱셈을 해야 하므로 result 변수의 초기값은 당연히 1이어야 한다.
이제 재귀 함수로 만들어보자. 만약에 factorial(5)부터 factorial(1)을 쭉 써보면 다음과 같을 것이다.
factorial(5) = 5 4 3 2 1 = 5 * factorial(4);
factorial(4) = 4 3 2 1 = 4 factorial(3);
factorial(3) = 3 2 1 = 3 * factorial(2);
factorial(2) = 2 1 = 2 factorial(1);
factorial(1) = 1;
여기서부터 어떤 규칙이 보이기 시작한다. 저 규칙대로라면 factorial(n) = n * factorial(n - 1);이 될 것이다.
이 것을 코드로 표현해보면 다음과 같다.
function factorial (n) {
return n * factorial(n - 1);
}
언뜻 보면 위 코드는 그럴듯해 보이지만 심각한 오류를 가지고 있다.
위 코드를 실제로 실행해보면 브라우저는 지구 끝까지 갈 기세로 코드를 계속해서 실행하다가 어느 시점에 저런 에러를 출력하고 멈출 것이다. Maximum call stack size exceeded. 최대 호출 스택 사이즈가 초과되었다. 이 부분이 바로 우리가 재귀 함수를 사용할 때 가장 유의해야하는 부분이다.
재귀 함수를 작성하여 호출하면 함수는 자기 자신을 계속해서 호출하여 실행한다. 이 때 특정 조건이 되었을 때, 재귀 호출을 종료하는 문장이 반드시 하나 이상 존재해야 하는데, 이렇게 재귀 호출을 중단시키는 조건 문장을 Base case 또는 Termination case라고 한다.
위의 팩토리얼 코드는 Base case가 없으므로 factorial(4), factorial(3), ..., factorial(-1), factorial(-2) ... 이렇게 음수의 영역까지 계속해서 호출하며 순차적으로 스택에 쌓을 것이고 어느 순간 정해진 메모리 용량을 초과하여 위와 같은 에러 메시지를 출력하게 된다.
function factorial (n) {
if (n === 1) { // Base case, Termination case
return 1;
}
return n * factorial(n - 1);
}
factorial(3); // 6
그러므로 위와 같이 우리는 재귀 호출을 종료하는 Base case로 n이 1이 되었을 때, 1을 return하는 문장을 반드시 추가해주어야 한다.
이제 위 코드는 완벽한 재귀 함수의 형태를 하고 있으며, 위 코드의 실행 순서는 다음과 같다.
- 먼저 파라미터 n의 값으로 3이 전달된다.
- stack에 3을 저장하고 factorial(3 - 1) = factorial(2)을 실행한다.
- n의 값으로 2가 전달된다. stack에 2를 저장하고 factorial(2 - 1) = factorial(1)을 실행한다.
- n의 값으로 1이 전달된다. n이 1이면 1을 리턴하고 함수를 종료한다.
- factorial(1)이 1을 return하고 종료하였으므로 2 * 1을 연산하고 그 값인 2를 return한다.
- 2와 3을 곱한 후 그 값인 6을 리턴하고 모든 함수가 종료된다.
