58 - (파이썬) 재귀 함수, 피보나치 수, 메모화(memorization)

# 피보나치 수열

: 수학에서 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열

 

즉, a_n을 n번째 항이라고 할 때, 다음과 같다.

a_1 = 1

a_2 = 1

a_n = a_{n-1} + a_{n-2} (n>=3인 자연수)

 

#피보나치 수열 Fibonacci numbers
def fbnc(n):
  if n == 1 or n == 2 :
    return 1
  elif n >= 3 :
    return fbnc(n-1) + fbnc(n-2)

print(fbnc(1))
print(fbnc(2))
print(fbnc(3))
print(fbnc(4))
print(fbnc(5))
print(fbnc(6))
>>>
1
1
2
3
5
8

 

※ 근디 말여... 숫자가 늘어나면 애는 착한디 좀 느려지는 문제가 생겨.. (n이 30 넘어가니까 버벅이네)

a_n = a_{n-1} + a_{n-2}니까 자기를 두 번씩 호출하는 함수여서 겁내 느려

그래프와 트리(아마도 수형도 같은 거 일 듯)-전위 순회를 배우면 이해되는 데 암튼 지금은 중복된 계산이 겁나리 많이 걸쳐서 그렇구나 생각하면 돼

 

🧐 그러면 말이여 중복된 계산을 줄이면 좀 빨라지지 않을까?

 

어떻게?

1. memo라는 딕셔너리를 만든다

2. a_{n-1} + a_{n-2}을 구하는 과정을 올려서 임시(temporary)라고 저장한다.

3. memo의 n번째에 temporary를 할당한다.

4. temporary라는 값으로 return한다.

memo = {}
def fbmm(n):
  if n == 1 or n == 2 :
    return 1
  elif n >= 3 :
    temporary = fbmm(n-1) + fbmm(n-2)
    memo[n] = temporary
    return temporary

print(fbmm(5))
print(memo)
>>>
5
{3: 2, 4: 3, 5: 5}

 

print(memo)에서 피보나치의 3번째 항이 2, 4번째 항이 3, 5번째 항이 5라는 것이 딕셔너리 형태로 저장되있는 것을 볼 수 있음.

 

이를 활용해서 fbmm(n)을 호출했는데, n이 memo에 있으면 memo에 있는 n을 return해주라고 코드를 추가하면

이렇게...!

memo = {}
def fbmm(n):
  if n in memo:
    return memo[n]
  if n == 1 or n == 2 :
    return 1
  elif n >= 3 :
    temporary = fbmm(n-1) + fbmm(n-2)
    memo[n] = temporary
    return temporary

print(fbmm(50))
>>>
12586269025

 

참고로 a_1 = 1, a_2 = 2도 memo에 넣어버리면 코드가 더 간단해진다.

 memo = {1: 1, 2: 1}
def fbmm(n):
  if n in memo:
    return memo[n]
  elif n >= 3 :
    temporary = fbmm(n-1) + fbmm(n-2)
    memo[n] = temporary
    return temporary

print(fbmm(50))
>>> 12586269025

겁나 빠르게 계산 가능

파이썬 튜터로 보면...

memo에 {1: 1, 2: 1}를 넣고 재귀함수로 함수 스택을 쌓은 것을 볼 수 있고

하나하나 쌓여가는 것을 볼 수 있다

이렇게 반복하게 된다...!

 

 

최신 파이썬에서는 더 간단한 코드도 가능하지만 일단 고급 기술이므로 안 적겠어...

---

https://replit.com/@wh3308/jaegwineun-dolaoneun-geoya#main.py