재귀

원판 64개짜리 하노이 탑을 옮기려면 18,446,744,073,709,551,615번 움직여야 하지만, 재귀 함수로는 그 풀이를 네 줄로 적을 수 있습니다.

자기 자신을 부르는 함수

어떤 문제는 안에 자기보다 작은 복사본을 품고 있습니다. 5의 계승 5!는 5 × 4 × 3 × 2 × 1 = 120입니다. 다시 보면 5 × (4 × 3 × 2 × 1)이고, 이것은 5 × 4!입니다. 일반적으로 n! = n × (n − 1)!이므로 계승을 구하려면 더 작은 계승을 구해서 곱하면 됩니다. 이처럼 작은 버전의 자기 자신을 불러서 문제를 푸는 함수를 재귀 함수라고 합니다.

function factorial(n) {
  if (n <= 1) return 1;          // base case: stop here
  return n * factorial(n - 1);   // recursive case: a smaller problem
}
console.log(factorial(5)); // 120

재귀 함수에는 두 부분이 꼭 있어야 합니다. 기저 사례는 다시 부르지 않고 바로 답할 수 있을 만큼 작은 입력입니다. 여기서는 1의 계승이 1입니다. 재귀 사례는 문제를 줄여서 함수를 다시 부릅니다. 부를 때마다 기저 사례에 가까워져야 합니다. 실수로 factorial(n + 1)이라고 쓰는 식으로 그렇지 않으면 호출이 끝나지 않습니다.

호출 스택

컴퓨터는 끝나지 않은 호출들을 어떻게 기억할까요? factorial(5)는 5 * factorial(4)에 이르러 답을 기다려야 합니다. 컴퓨터는 기다리는 호출을 스택에 올려 둡니다. 스택은 마지막에 올린 것을 가장 먼저 꺼내는 더미입니다. factorial(4)는 factorial(3)을 기다리고, 이렇게 factorial(1)까지 내려가면 1을 바로 돌려줍니다. 그러면 스택이 거꾸로 풀립니다. factorial(2)가 2, factorial(3)이 6, factorial(4)가 24, factorial(5)가 120을 돌려줍니다.

스택의 크기는 정해져 있습니다. 기저 사례에 닿지 못하는 재귀는 공간이 바닥날 때까지 호출을 쌓고, 자바스크립트는 오류를 내고 멈춥니다. 크롬과 Node.js에서는 「RangeError: Maximum call stack size exceeded」라는 메시지가 나옵니다. 같은 이유로 수십만 층처럼 아주 깊은 재귀는 반복문으로 쓰는 편이 낫습니다.

하노이 탑

하노이 탑은 프랑스 수학자 에두아르 뤼카가 1883년에 내놓은 퍼즐입니다. 기둥이 세 개 있고, 첫 기둥에 크기가 다른 원판들이 큰 것이 아래로 가게 쌓여 있습니다. 목표는 원판 더미 전체를 셋째 기둥으로 옮기는 것입니다. 한 번에 원판 하나만, 기둥의 맨 위 원판만 옮길 수 있고, 큰 원판을 작은 원판 위에 놓을 수 없습니다.

원판마다 어디로 갈지 한 수씩 생각하면 금방 헷갈립니다. 재귀로 생각하면 짧아집니다. 원판 n개를 A에서 C로 옮기려면, 먼저 위의 n − 1개를 A에서 B로 비켜 놓습니다. 다음에 가장 큰 원판을 A에서 C로 옮깁니다. 마지막으로 B의 n − 1개를 C에 있는 큰 원판 위로 옮깁니다. n − 1개를 옮기는 일은 한 단계 작은 같은 퍼즐이고, 원판 하나를 옮기는 일이 기저 사례입니다. 원판 3개라면 7번 움직이며, 실험실은 움직일 때마다 기다리는 호출의 스택을 보여 줍니다.

function hanoi(n, from, to, via) {
  if (n === 0) return;
  hanoi(n - 1, from, via, to);
  console.log("disk " + n + ": " + from + " -> " + to);
  hanoi(n - 1, via, to, from);
}
hanoi(3, "A", "C", "B");  // 7 moves

원판 n개는 몇 번 움직여야 할까요? n개를 옮기려면 n − 1개 옮기기 두 번에 한 번을 더해야 하므로 M(n) = 2M(n − 1) + 1이고 M(1) = 1입니다. 그러면 1, 3, 7, 15, 31이 나오고 M(n) = 2ⁿ − 1이며, 이보다 적게 움직이는 풀이는 없습니다. 원판 10개는 1,023번입니다. 64개는 2⁶⁴ − 1 = 18,446,744,073,709,551,615번이고, 1초에 한 번 움직이면 약 5,850억 년이 걸립니다. 앞 단원에서 본 O(2ⁿ) 증가입니다.

재귀, 반복문, 되풀이되는 일

재귀로 쓴 것은 반복문과 직접 만든 스택으로도 쓸 수 있고, 계승처럼 간단한 경우에는 반복문이 더 읽기 쉬울 때가 많습니다. 재귀가 빛나는 것은 문제 자체가 나무 모양일 때입니다. 병합 정렬의 목록 쪼개기, 폴더 안의 폴더 뒤지기, 다음 단원 주제인 미로 탐색이 그렇습니다. 조심할 함정은 되풀이되는 일입니다. 피보나치 수 0, 1, 1, 2, 3, 5, 8, …은 fib(n) = fib(n − 1) + fib(n − 2)를 따릅니다. 이것을 그대로 재귀로 쓰면 fib(10) = 55를 구하는 데 177번, fib(20)에 21,891번, fib(30)에 2,692,537번 호출합니다. 같은 작은 값을 거듭 다시 계산하기 때문입니다. 이미 구한 답을 기억해 두거나, 반복문으로 아래부터 쌓아 올리면 이 낭비가 사라집니다.