[Python]피보나치수열 구현 및 방법 비교: 재귀 함수,동적 프로그래밍 활용(Fibonacci numbers, recursion and dynamic programming)

이번 글에서는 파이썬 언어로 피보나치수열을 구현합니다.

이때, 재귀함수 및 동적 프로그래밍 방법을 모두 구현하여 실행시간을 비교합니다.

1. 재귀 함수로 구현(Recursion)

def Fibo_recursion(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return Fibo_recursion(n-1) + Fibo_recursion(n-2)

2. 동적 프로그래밍으로 구현(Dynamic programming)

def Fibo_dynamic(n):
    arr = [0]*(n+1)
    arr[1] = 1
    for i in range(2,n+1):
        arr[i] = arr[i-1] + arr[i-2]
    return arr[n]

3. 실행시간 비교

# 재귀함수 실행
start = time.time()
re = Fibo_recursion(40)
print("답은 : {}, 걸린시간 :{:.8}초".format(re,time.time() - start))
#=> 32.484307초

# 동적프로그래밍 실행
start = time.time()
re = Fibo_dynamic(40)
print("답은 : {}, 걸린시간 :{:.8}초".format(re,time.time() - start))
#=> 0.0000714초

동적프로그래밍 방식이 훨씬 적은 실행시간을 가지는 것을 확인할 수 있다.