백준 10870번

BOJ 10870 : 피보나치 수 5

피보나치 수열은 아래와 같이 표현될 수 있다

$F_n = F_{n-1} + F_{n-2}\ \ (if\ n > 1)$

n = 0 일때는 0, n = 1일 때는 1로 잡으면

이 수열은 위의 표현에 따라 0, 1, 1, 2, 3, 5, 8, 13, ... 과 같이 이어진다.

따라서, 이 식 자체를 재귀함수로 구현하면 바로 해결되는 문제이다.

#include <stdio.h>

int Fibonacci(int);

int main()
{
    int n;

    while (scanf("%d", &n) != 1);

    printf("%d", Fibonacci(n));
}

int Fibonacci(int num)
{

    if (num > 1)
    {
        return Fibonacci(num - 1) + Fibonacci(num - 2);
    }
    else if (num == 1)
    {
        return 1;
    }
    else
        return 0;
}