Python Algorithm) Fibonachi sort(recursive call, dynamic programming)

🎃 재귀함수를 이용하는 경우

: 스택에 데이터가 계속 쌓이고 코드의 가독성도 떨어진다.

# 2020.08.20
# 피보나치 수열

# 재귀함수(recursive call)로 구현
def recallFibo(num):
    if num <= 1:
        return num
    else:
        return recallFibo(num-1)+recallFibo(num-2)

print(recallFibo(0)) #0
print(recallFibo(1)) #1
print(recallFibo(2)) #1
print(recallFibo(3)) #2
print(recallFibo(4)) #3
print(recallFibo(5)) #5
print(recallFibo(6)) #8
print(recallFibo(7)) #13

🎄 동적계획법을 이용하는 경우

: 보다 간단하고 가독성 좋은 코드를 구현할 수 있다. 단, dynamicFibo(0)을 출력할 경우 fibo_list[1]이 들어갈 공간이 없기 때문에 에러가 출력된다.

# 동적계획법(dynamic programming)으로 구현
def dynamicFibo(num):
    fibo_list = [ 0 for i in range(num+1) ]
    fibo_list[0] = 0
    fibo_list[1] = 1
    for idx in range(2, num+1):
        fibo_list[idx] = fibo_list[idx-1] + fibo_list[idx-2]
    return fibo_list[num]

print(dynamicFibo(3)) #2
print(dynamicFibo(4)) #3
print(dynamicFibo(5)) #5
print(dynamicFibo(6)) #8
print(dynamicFibo(7)) #13