피보나치 수를 구하는 여러 가지 해법

fibonacci.py

"""피보나치 수를 구하는 함수를 만들어라

함수의 기본적인 골격은 다음과 같을 겁니다.

f(n):  {
    0                : if n == 0 
    1                : if n == 1    
    f(n-1) + f(n-2)  : else
}
"""

# 1. 원시적인 풀이
def fibonacci(nth):
    if nth == 0:
        return 0
    elif nth == 1:
        return 1
    else:
        return fibonacci(nth-1) + fibonacci(nth-2)
        
        
# 2. 바람직한 풀이(dynamic programming)
MAX = 1000
CACHE = [0] * (MAX + 1)
CACHE[1] = 1

for n in range(2, 1000+1):
    CACHE[n] = CACHE[n-1] + CACHE[n-2]
    

def fibonacci(nth):
    return CACHE[nth]