백준 2748번_피보나치 수 2 [python/파이썬]

def fibonacci(n, cnt, result1, result2): # tail_recursion ver
    if cnt == n:
        return result1
    return fibonacci(n, cnt+1, result2, result1+result2)
 
num = int(input())
print(fibonacci(num, 0, 0, 1)) # 피보나치 수열의 0번째와 첫번째 수가 0, 1 이므로

 

 # 보통 피보나치 수열을 재귀적으로 구현할 때 n의 값을 하나씩 감소시키며 값을 구한다. 그러나 이럴 경우 중복되는 계산의 양이 많아지므로 구하고자 하는 숫자가 커질 때 많은 시간을 필요로 한다. 이를 해결하기 위해 가장 작은 수에서부터 역으로 올라가는 bottom-up 방식으로 구현하였다.