[C언어] 재귀적 피보나치 수열 구현

피보나치 수열에서는 앞의 두 개의 숫자를 더해서 뒤의 숫자를 만든다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...

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

이 코드를 이용해서 fib(6)를 실행하면 fib()함수가 25번이나 호출된다. fib() 함수가 25번이나 호출된다. 중간에 계산되었던 값을 기억하지 않고 다시 계산하기 때문이다.

fib(6)	1번 호출
fib(5)	1번 호출
fib(4)	2번 호출
fib(3)	3번 호출
fib(2)	5번 호출
fib(1)	8번 호출

시간복잡도 O(2^n)

따라서 n이 커지면 커질수록 엄청난 순환호출이 필요하게 된다. 그래서 순환보다는 반복 구조를 사용하면 더 좋은 결과를 얻을 수 있다. 

int fib_iter(int n)
{
    if (n == 0) return 0;
    if (n == 1) return 1;
        
    int pp = 0;	
    int p = 1;
    int result = 0;
        
    for (int i = 2; i <= n; i++) {
        result = p + pp;
        pp = p;
        p = result;
    }
    return result;
}