(C언어) 피보나치 수열

피보나치 수열(Fibonacci sequence)은 앞의 두 항의 합이 다음 항이되는 수열이다.

 

1번째 수를 1, 2번째 수를 1로 두고 3번째 수부터 앞의 두 항의 수를 더해간다.

1   1   2   3  5   8   13   21   34   55   89   144   233   377   610  987 ...

 

컴퓨터 프로그램에서는 반복문과 재귀호출의2 가지 방법으로 구현을 할 수 있다.

 

반복문을 이용한 피보나치 수열 구하기

#include <stdio.h>
#define N   15   // 출력할 개수

int main()
{
    int first = 1;
    int second = 1;
    int i, third;

    printf("%d  %d  ", first, second);

    for (i = 3; i <= N; i++)
    {
        third = first + second;
        printf("%d  ", third);
        first = second;
        second = third;
    }
    return 0;
}

(Output)

 

재귀호출을 이용한 피보나치 수열 구하기

#include <stdio.h>
#define N   20   // 출력할 개수

unsigned int fibonacci_rcsv(unsigned int n) 
{
    if (n <= 1) return n; 
    else return fibonacci_rcsv(n - 2) + fibonacci_rcsv(n - 1);
}

int main()
{
    int i;
    for (i = 1; i <= N; i++)
        printf("%u  ", fibonacci_rcsv(i));

    return 0;
}

피보나치 수열: 재귀호출