[백준 BOJ_10870] 피보나치 수 5 Python 풀이

출처: 백준 온라인 저지

문제

풀이

피보나치의 수를 구하는 공식은 문제에서 주어졌듯이 아래와 같습니다.

\[F_n = F_{n-1} + F_{n-2} \quad(n\ge2)\]

그러므로 기저 사례(base case)는 $F_0$과 $F_1$이 됩니다.
그 이후로는 $F_{n-1}$과 $F_{n-2}$에 해당하는 두 재귀호출의 반환 값의 합을 반환해주면 됩니다.

코드

def fib(n):
    if n == 0: # F0 = 0
        return 0
    if n == 1: # F1 = 1
        return 1
    return fib(n-1) + fib(n-2)

N = int(input())
print(fib(N))