フィボナッチで再帰メモ化

先日、AtCoderの勉強会で強い人からメモ化再帰いいよーといわれたので学んでみる

今回は単純にフィボナッチ数列を求めるプログラムを作る
フィボナッチ数列は、初期値とその次の値を足した数字が続いていく数列である
1, 2, 3, 5, 8....

今回の仕様は以下の通り
・入力Nを受け取り、N個の数列を作成する
・プログラムを2本つくり、一つは再帰を用いた形、もう一つはそこにメモ化を加えた形

N = int(input())

def calc(x):
  if x == 1:
    return 0
  elif x == 2:
    return 1
  else:
    return calc(x-1)+calc(x-2)
  
print(calc(N))


計算結果
N=30 222ms
N=33 893ms
N=36 3721ms
N=39 >10000ms

これでは時間がかかってしまい、Nが大きくなった時に対応できない
よって、ハッシュによるメモ化を実装する

計算した値をハッシュに登録し、結果をメモする

N = int(input())

dic = {1:1, 2:1}

def calc(x):
  if x in dic:
    return dic[x]
  else:
    dic[x] = calc(x-1)+calc(x-2)
    return dic[x]

print(calc(N))

計算結果
N=30 17ms
N=39 17ms
N=100 17ms
N=1000 18ms

ハハハ・・・・なんて違いだ。
再帰メモ化の恐ろしい強さを確認したところで、今回は終了