파이썬, 피보나치 수 구하기 (메모이제이션+재귀호출 방식)

 

파이썬, 피보나치 수 구하기 (메모이제이션 + 재귀호출 방식)

 

글. 오상문 sualchi@daum.net

 

n 번째 피보나치 수를 구할 때 기존에 구한 값은 리스트에 저장해서 재활용하는 메모이제이션 방식을 사용한 코드입니다. fibo 리스트는 인덱스 1을 제외하고 모두 0으로 초기화하고 fibo[1]만 1로 초기화합니다. 처음에 피보나치 수를 구할 때는 계산을 통해 진행하지만 이후에 다시 피보나치 함수를 수행할 때는 이미 구해진 값이 fibo 리스트에 있으면 그 값을 재활용하므로 속도가 빨라집니다.

 

#--------------------------------------------------

fibo = [0 for i in range(1000001)]
fibo[1] = 1

 

def fast_f(n):
  if n==0 or n==1:
    return n
  if fibo[n] == 0:
    fibo[n] = fast_f(n-1) + fast_f(n-2)    
  return fibo[n] 

 

def fibonacci(n):
  if n<=0 or n==1:
    return n        
  return fast_f(n)

#---------------------------------------

for n in range(1,21):
  print("%3i: %i" %(n, fibonacci(n)))

print("...") 

for n in range(90,101):
  print("%3i: %i" %(n, fibonacci(n)))

 
[실행 결과]
  1: 1
  2: 1
  3: 2
  4: 3
  5: 5
  6: 8
  7: 13
  8: 21
  9: 34
 10: 55
 11: 89
 12: 144
 13: 233
 14: 377
 15: 610
 16: 987
 17: 1597
 18: 2584
 19: 4181
 20: 6765
...
 90: 2880067194370816120
 91: 4660046610375530309
 92: 7540113804746346429
 93: 12200160415121876738
 94: 19740274219868223167
 95: 31940434634990099905
 96: 51680708854858323072
 97: 83621143489848422977
 98: 135301852344706746049
 99: 218922995834555169026
100: 354224848179261915075