[재귀 알고리즘] 피보나치 수열(재귀, 꼬리 재귀, 반복문)

[재귀 알고리즘] 피보나치 수열(재귀, 꼬리 재귀, 반복문)

피보나치 수열

피보나치 수열은 앞에 두 수를 더해서 현재 위치의 수를 만드는 수열이다.

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

수학적으로 표현하면,

\[ Fibonacci(n) = \begin{cases} 0 & \quad \dots \text{ n = 1}\\ 1 & \quad \dots \text{ n = 2}\\ Fibonacci(n-1) + Fibonacci(n-2) \quad \dots \text{ otherwise}\\ \end{cases} \]

아래는 피보나치 수열을 일반적인 재귀, 꼬리 재귀, 반복문으로 구현한 코드이다.

(꼬리 재귀 설명 : http://ledgku.tistory.com/37)

Code

#include <stdio.h>
 
//***** 일반 재귀  *****//
int Fibo(int n){
    if (n == 1)
        return 0;
    else if (n == 2)
        return 1;
    else
        return Fibo(n - 1) + Fibo(n - 2);
}
 
//***** 꼬리 재귀 *****//
int FiboTail(int n){
    return FiboTailRec(n, 0, 1);
}
 
int FiboTailRec(int n, int before, int next){
    if (n == 0)
        return before;
    else
        return FiboTailRec(n - 1, next, before + next);
}
 
//***** 반복문 *****//
int FiboLoop(int n){
    int before=0, cur=1, i, temp;
 
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    else{
        for (i = 1; i < n; i++){
            temp = cur;
            cur = before + cur;
            before = temp;
        }
        return cur;
    }
}
 
int main(int arc, char** argv){
    int num = 10;
    int i = 1;
 
    for (; i <= num; i++){
        printf("%d ", Fibo(i));
    }
 
    printf("\n");
 
    for (i=0; i < num; i++){
        printf("%d ", FiboTail(i));
    }
 
    printf("\n");
 
    for (i = 0; i < num; i++){
        printf("%d ", FiboLoop(i));
    }
}

Output

0 1 1 2 3 5 8 13 21 34
0 1 1 2 3 5 8 13 21 34
0 1 1 2 3 5 8 13 21 34