재귀 (2) - 피보나치 수열 (Fibonacci Series)

1. 알고리즘 개요

Fibonacci Series (피보나치 수열)은 재귀함수가 활용되는 대표적인 경우이다. 피보나치 수열은 이전 두 요소의 합이 다음 원소가 되는 수열로 정의된다. 이 때, 1, 2번 원소는 이전 두 요소가 없기 때문에 1로 정의된다. 자세한 수학적 정의는 아래와 같다.

 

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

단, $F_1 = F_2 = 1$

 

2. 소스코드

 

#include <stdio.h>

int fibonacci(int n) {
    if (n == 1 || n == 2) return 1;
    else return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int fibo = fibonacci(10);
    printf("%d", fibo);
    return 0;
}

 

소스코드는 위와 같다. 피보나치 수열의 기저는 n이 1 혹은 2일때 이며, 이 때 재귀가 종료(return 1)된다. 또한 파라미터 n은 1과 2를 향해서 점점 내려가고 있기 때문에 이 구현은 Devide & Conquer 전략을 수행하기 위한 올바른 재귀함수에 해당한다. 따라서 이 함수를 이용하면 피보나치 수열을 찾을 수 있다. 재귀함수를 이용할 때의 장점 중 한가지는 코드의 가독성이 매우 좋다는 것이다. 아래 코드는 위 수식을 거의 그대로 옮겨놓은 수준의 가독성을 가진다.

 

모든 소스코드는 Github에서 확인할 수 있습니다.

gusdnd852/TIL

 

3. Recurssion Tree

위 소스코드를 실행하면 실제로는 어떤일이 생길까? 우리가 fibonacci(4)를 호출한다고 해보자. 그러면 fibonacci(4)는 fibonacci(3)과 fibonacci(2)를 호출하게 되고, 이들은 다시 fibonacci(2), fibonacci(1), fibonacci(0)등을 호출하게 되고, 결국 결과값을 찾게 된다. 그러나 이런 방식으로 구현하면 이미 결과값을 알고있는 함수가 반복해서 호출된다는 문제가 발생한다. 아래의 트리는 Recurrsion Tree라고 불리는데, 재귀함수의 호출을 이해하기 쉽게 하기 위한 그림으로 이해하면 좋다. 트리를 보면 fibonacci(2)는 총 2번, fibonacci(1)은 3번, fibonacci(0)은 총 2번 호출되었다. 때문에 만약 fibonacci(40)와 같은 함수를 호출하면 계산 속도가 매우 느리다. ($O(2^n)$)의 시간 복잡도를 가지게 된다.)

 

 

 

원래대로라면 이들은 한번씩만 호출되어도 이미 결과를 알기 때문에 다시 호출할 필요가 없다. 따라서 이러한 문제를 해결하기 위한 몇가지 기법(Memoization, Dynamic Programming)이 존재하는데, 이는 다음에 다시 소개하도록 한다. 

 

4. Reference