[파이썬] 피보나찌 수열 값 구하기 (반복문/재귀함수)

파이썬 피보나찌 수열 값 구하기 - 반복문 version

def fibonacci(n): 
    if n==1: 
        return 1 
    if n==2: 
        return 1 
    a = 1 
    b = 1 
    result = 0 
    for i in range(n-2): 
        result = a + b 
        a = b 
        b = result 
    return result 

print(fibonacci(1)) 
print(fibonacci(2)) 
print(fibonacci(3)) 
print(fibonacci(4)) 
print(fibonacci(5)) 
print(fibonacci(10)) 
print(fibonacci(20)) 
print(fibonacci(30)) 
print(fibonacci(40)) 
print(fibonacci(50)) 

1 
1 
2 
3 
5 
55 
6765 
832040 
102334155 
12586269025 

파이썬 피보나찌 수열 값 구하기 - 재귀함수 version (잘못된 사례)

def fibonacci(n): 
    if n == 1: 
        return 1 
    if n == 2: 
        return 1 
    return fibonacci(n-1) + fibonacci(n-2) 

print(fibonacci(1)) 
print(fibonacci(2)) 
print(fibonacci(3)) 
print(fibonacci(4)) 
print(fibonacci(5)) 
print(fibonacci(10)) 
print(fibonacci(20)) 
print(fibonacci(30)) 
print(fibonacci(40)) 
print(fibonacci(50)) 

 위 방법은 피보나찌 수열을 직관적으로 구현하였지만, 같은 연산을 여러번 하는 문제가 있습니다. 이로 인해서 피보나찌 수열의 30번째 정도 구할려고 하면 중복되는 연산의 개수가 많아져서 속도가 급격히 저하되는 문제가 있습니다. 이를 해결하기 위해서는 이미 계산했던 값들을 어딘가에 저장해놓고 필요한 경우 해당 값을 뽑아서 써야 합니다. 이를 memorization 기법이라고 합니다.

 

파이썬 피보나찌 수열 값 구하기 - 재귀함수 version (memorization 기법사용)

재귀함수는 같은 연산을 여러번 재귀적으로 호출하는 문제가 있습니다. 이를 방지하기 위해서는 이미 계산했던 연산을 저장해두고 이를 꺼내 쓰는 방법이 필요합니다. 이를 위해 예전 계산들을 dictionary에 저장하고 이미 연산 기록이 있으면 그 값을 사용하는 식으로 코드를 수정합니다.

answer = { 
    1: 1, 
    2: 1 
} 

def fibonacci(n): 
    if n in answer: 
        return answer[n] 
    else: 
        result = fibonacci(n-1) + fibonacci(n-2) 
        answer[n] = result 
        return result 

print(fibonacci(1)) 
print(fibonacci(2)) 
print(fibonacci(3)) 
print(fibonacci(4)) 
print(fibonacci(5)) 
print(fibonacci(10)) 
print(fibonacci(20)) 
print(fibonacci(30)) 
print(fibonacci(40)) 
print(fibonacci(50))
print(fibonacci(70))
print(fibonacci(100))

1
1
2
3
5
55
6765
832040
102334155
12586269025
190392490709135
354224848179261915075

memorization기법을 활용하면 100번쨰 피보나찌 수열의 값을 구하는 것도 거뜬합니다.