N번째 피보나치 수 구하기

문제

피보나치 수열은 아래와 같이 정의한다.

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) (n ≥ 2)

정수 n이 주어질 때, F(n)을 구해서 출력한다.

재귀 함수로 쓰면 이렇게 된다.

int fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

이 재귀는 같은 값을 여러 번 다시 계산한다. 시간이 많이 걸린다면 반복문이나 메모이제이션으로 바꿔 본다.