재귀함수(2): 피보나치 수열 구하기

1. 피보나치 수열이란?

피보나치 수열에 대해 길게 설명할 이유는 없으므로 간단히 식만 쓰도록 하자. 누구나 알고 있을 것이라 생각한다.

$$F_n = \begin{cases}0 \; (n=0)\\1 \; (n=1)\\F_{n-1}+F_{n-2} \; (n>1) \end{cases}$$

2. 재귀함수를 사용하지 않고 피보나치 수열 구하기

사실 그리 어렵지는 않다.

앞의 수를 기억하고 있어야 하므로 0, 1에서 시작해서 (a, b) -> (b, a+b)로 바꾸어주면 된다.

int fib1(int n) {
	if (n == 0) return 0;
	if (n == 1) return 1;
	int a, b, t;
	a = 0; b = 1;
	for (int i = 1; i < n; ++i) {
		t = b;
		b = a + b;
		a = t;
	}
	return b;
}

머릿속에 알고리즘이 그려지면 바로 코드로 옮겨낼 수 있어야 진정한 프로그래머라고 할 수 있다.

3. 재귀함수를 사용하여 피보나치 수열 구하기

1번에 쓰여있는 식을 그대로 쓰면 된다.

int fib2(int n) {
	if (n == 0) return 0;
	if (n == 1) return 1;
	return fib2(n - 1) + fib2(n - 2);
}

아주 간단하다. 아주 간단해 보인다.

위 함수의 문제점이 있을까? 답을 미리 말하자면, 시간복잡도가

$O(F(n)) = O(1.618^n)$이다.

(앞으로 알고리즘에서 시간복잡도라는 말이 많이 나올 예정인데, 이에 관한 설명은 여기를 참고하자)

그 이유를 살펴보자. 이 때 편의상 함수가 1회 호출되는데 비용은 모두 같다고 가정하자. 어차피 if문 2개 후 return이라서 비슷하다.

fib(5)를 구하는 과정을 생각해보자.

/*

fib(5)

= fib(4) + fib(3)

= fib(3) + fib(2) + fib(3)

= fib(2) + fib(1) + fib(2) + fib(3)

= fib(1) + fib(0) + fib(1) + fib(2) + fib(3)    

= 1 + fib(0) + fib(1) + fib(2) + fib(3)

= 1 + 0 + fib(1) + fib(2) + fib(3)

= 1 + 0 + 1 + fib(2) + fib(3)

= 1 + 0 + 1 + fib(1) + fib(0) + fib(3)

= 1 + 0 + 1 + 1 + fib(0) + fib(3)

= 1 + 0 + 1 + 1 + 0 + fib(3)

= 1 + 0 + 1 + 1 + 0 + fib(2) + fib(1)

= 1 + 0 + 1 + 1 + 0 + fib(1) + fib(0) + fib(1)

= 1 + 0 + 1 + 1 + 0 + 1 + fib(0) + fib(1)

= 1 + 0 + 1 + 1 + 0 + 1 + 0 + fib(1)

= 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1

= 5

*/

총 15번 함수가 실행되었다. 이 함수의 호출 횟수 또한 재귀적 성질을 가지고 있는데,

fib(n)은 1번 실행 후 fib(n-1)과 fib(n-2)를 반환하므로 (n > 1)

$F_n = F_{n-1} + F_{n-2} + 1$

의 재귀적 관계를 가진다. 대략적으로 피보나치 수열과 증가속도가 같다.

이 말은, n이 1 커질때마다 시간이 약 1.6배씩 더 커진다는 것이다.

fib(10)을 100만번 구하는 데에 4.43초가 걸렸으니

fib(10) = 4.43 * 10^-6초

fib(20) = 5.45 * 10^-4초

fib(30) = 6.70 * 10^-2초

fib(40) = 8.24초

fib(50) = 1012.85초 (=약 17분)

여기까지는 그래도 무난하다..

하지만 fib(100)정도만 구하려고 해도 이 방법으로는 무려 90만년의 시간이 소요된다. 지수형 시간복잡도의 힘이다.

보다 효율적인 방법을 생각해보자.

4. 메모이제이션(memoization)을 활용한 재귀함수

그렇다면 그 동안 계산했던 것들을 메모리에 저장해놓은 뒤, 불러다가 사용하면 훨씬 더 빠르게 계산해낼 수 있지 않을까?

이러한 방법이 메모이제이션이라는 방법이며, 동적 프로그래밍의 기초가 되는 아이디어다.

코드는 간단하다. 계산된 것을 저장하는 배열을 만든 뒤, 반환하려는 값이 배열에 저장이 되있으면 계산없이 바로 그 값을 반환하면 된다.

코드는 다음과 같다.

int fib3(int n) {
	static int mem[40] = { 0 };
	if (n == 0) return mem[0] = 0;
	if (n == 1) return mem[1] = 1;
	if (mem[n] > 0) return mem[n];

	return mem[n] = fib3(n - 1) + fib3(n - 2);
}

static을 사용하면 그 함수 내에서만 사용가능한 배열을 만들 수 있다.

물론, 전역 변수를 사용해도 되지만 이게 더 안정적이다.

약 fib(45)부터 int의 값을 넘기 때문에, 배열의 길이는 40으로 하였다.

실행해보면 호출 횟수가 눈에 띄게 줄어들어서, 코드가 훨씬 빨라진 것을 확인할 수 있다.

시간 복잡도는 $O(n)$이다.

물론 피보나치 수열은, 재귀함수를 사용하지 않는 것이 가장 효율적인, 재귀함수의 좋은 않은 예시로 알려져 있다.

(너무 간단한 식은 굳이 오버헤드가 큰 재귀함수를 사용할 필요가 없다는 말)

하지만, 이처럼 계산된 값을 저장해서 중복 계산을 피하면 비교할 수 없을만큼 빠른 속도로 값을 구할 수 있다.

이제 앞으로는 어떤 식으로 저장을 해야 중복 계산을 피할 수 있을지를 중점적으로 생각하게 될 것이다.