재귀적 알고리즘

피보나치 수 \(F(n)\)을 구하는 프로그램을 "\(n\)이 1이나 2이면 1을 돌려주고, 아니면 \(F(n-1) + F(n-2)\)를 돌려준다"로 짰다. 정의를 그대로 옮긴 깔끔한 프로그램인데, \(F(30)\)을 구하는 데 함수가 160만 번 넘게 불렸다. 반면 \(a^{100}\)을 구하는 프로그램은 자기 자신을 부르는 같은 방식을 쓰는데도 곱셈 여덟 번 만에 끝났다. 자기 자신을 부르는 알고리즘은 언제 느리고 언제 빠를까?

2.4.1자기 자신을 부르는 알고리즘

문제를 같은 꼴의 더 작은 문제로 바꾸어 풀도록 자기 자신을 다시 부르는 알고리즘을 재귀적 알고리즘이라 한다. 재귀적 알고리즘에는 더 이상 나누지 않고 바로 답을 내는 기저 단계와, 작은 문제의 답으로 큰 문제의 답을 만드는 재귀 단계가 있어야 한다. 기저 단계가 없거나 문제가 작아지지 않으면 끝없이 자기 자신을 불러 멈추지 않는다. 재귀적 알고리즘은 점화 관계를 그대로 옮긴 것이어서 쓰기 쉽고 옳은지 확인하기도 쉽다.

피보나치의 재귀는 한 번 부를 때마다 두 번 다시 부르고, 그 두 갈래가 같은 값을 따로 계산한다. 그래서 호출 수가 피보나치 수 자체처럼 지수적으로 늘어난다. 한 번 계산한 값을 표에 적어 두고 다시 필요할 때 꺼내 쓰면, 각 \(F(k)\)를 한 번씩만 계산해 호출이 \(n\)번 정도로 줄어든다. 반면 빠른 거듭제곱은 문제를 절반 크기의 문제 하나로 바꾸므로 단계 수가 로그만큼만 늘어난다. 재귀가 빠른지 느린지는 문제를 몇 개로, 얼마나 작게 나누는지와 같은 계산을 되풀이하는지에 달려 있다.¹

2.4.2절반으로 줄이는 거듭제곱

\(a^{100}\)을 \(a\)를 99번 곱해 구하는 대신, \(a^{100} = (a^{50})^2\), \(a^{50} = (a^{25})^2\), \(a^{25} = a\cdot(a^{12})^2\)처럼 지수를 절반으로 줄여 가며 재귀적으로 구한다. 지수가 짝수이면 제곱 한 번, 홀수이면 제곱 한 번과 \(a\)를 곱하는 한 번이 필요하다. 이 과정은 지수를 2진법으로 쓴 것과 같아서, \(100 = 1100100_{(2)}\)의 자릿수가 제곱의 횟수를, 1의 개수가 추가 곱셈의 횟수를 정한다. 그래서 지수가 아주 커도 곱셈 횟수는 지수의 자릿수 정도로만 늘어난다.

2.4.3예제 풀이

호출 수는 \(C(n) = 2F(n) - 1\)이므로 \(C(30) = 2\times832040 - 1 = 1664079\)번이다. 값을 표에 적어 두면 \(F(3)\)부터 \(F(30)\)까지 한 번씩, 28번의 덧셈으로 끝난다.

빠른 거듭제곱은 \(a^{100} \leftarrow a^{50} \leftarrow a^{25} \leftarrow a^{12} \leftarrow a^6 \leftarrow a^3 \leftarrow a^1\)로 지수를 줄인다. 거꾸로 올라가며 세면 \(a^3 = a\cdot a^2\)에서 2번, \(a^6\), \(a^{12}\)에서 1번씩, \(a^{25} = a\cdot(a^{12})^2\)에서 2번, \(a^{50}\), \(a^{100}\)에서 1번씩이어서 모두 8번이다. 99번 곱하는 것보다 열 배 이상 빠르다. 즉 재귀적 알고리즘은 기저 단계와 재귀 단계로 문제를 작은 같은 꼴로 바꾸며, 같은 계산을 되풀이하면 지수적으로 느려지고 문제를 절반씩 줄이면 로그만큼만 늘어난다.

아래 탐구 카드에서 피보나치 재귀의 호출 나무를 그려 보고, 빠른 거듭제곱으로 \(a^{100}\)을 곱셈 몇 번 만에 구하는지 세어 보자.

1. 계산한 값을 적어 두었다가 다시 쓰는 방법을 동적 계획법이라 한다. 1950년대 미국의 벨먼이 이름을 붙였으며, 오늘날 길 찾기, 맞춤법 검사, 유전자 서열 비교처럼 작은 문제의 답이 여러 번 쓰이는 계산에 널리 쓰인다.