피보나치 수열(Fibonacci Sequence)

피보나치 수열(Fibonacci Sequence)의 점화식은 다음과 같다.

$F_{n}:=\begin{cases} 0 \quad (\text{if} \quad n = 1) \\ 1 \quad (\text{if} \quad n = 2) \\ F_{n-1} + F_{n-2} \quad (\text{if} \quad n > 2) \end{cases}$

이 점화식을 바탕으로 구한 피보나치 수열의 항과 값은 다음과 같다.

항	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	...
값	0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	1597	...

피보나치 수열은 재귀 함수 또는 반복문을 이용하여 구현할 수 있다.

1. 반복문을 이용하여 구현하기

#include <stdio.h>
 
int main() {
    int N;
    int num1 = 0;
    int num2 = 1;
    int num3 = 0;
    int sum = 0;
 
    printf("피보나치 수 입력 : ");
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        printf("%d ", num1);
        sum += num1;
        
        num3 = num1 + num2;
        num1 = num2;
        num2 = num3;
    }
    printf("\n");
    printf("1번째 항부터 %d번째 항까지의 합 : %d\n", N, sum);                                                                     
 
    return 0;
}

피보나치 수 입력 : 8
0 1 1 2 3 5 8 13
1번째 항부터 8번째 항까지의 합 : 33                                                                                                   

2. 재귀 함수를 이용하여 구현하기

#include <stdio.h>
#include <stdlib.h>
 
int Fib(int n);
 
int main() {
    int N;
    int sum = 0;
 
    printf("피보나치 수 입력 : ");
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        printf("%d ", Fib(i));
        sum += Fib(i);
    }
    printf("\n");
    printf("1번째 항부터 %d번째 항까지의 합 : %d\n", N, sum);                                                                       
 
    return 0;
}
 
int Fib(int n) {
    if (n == 0) return 0;
    else if (n == 1) return 1;
    else return Fib(n - 1) + Fib(n - 2);
}

피보나치 수 입력 : 9
0 1 1 2 3 5 8 13 21
1번째 항부터 9번째 항까지의 합 : 54