본문 바로가기

컴퓨터 공학/알고리즘

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


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


피보나치 수열

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

$$ 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#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, 01);
}
 
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));
    }
}
cs


Output

1
2
3
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
cs