メモ化再帰 レベル1 フィボナッチ数列

フィボナッチ数列とは

1,1,2,3,5,8,13,21

というように二つ前の値と一つ前の値を加算して作る数列のこと。

黄金比や自然界にちょこちょこ見られる神秘的な数列である。

メモ化とは

文字通り値をメモしていき、同じ計算等はしないようにする。無駄に計算しないことにより、レスポンスを速くすることができる。

フィボナッチ数列のコード

memo = [0 for _ in range(100)]

n = 10

def fib(n):

if memo[n] > 0: return memo[n]

if n <= 1:

memo[n] = 1

else:

memo[n] = fib(n-1)+fib(n-2)

return memo[n]

fib(n)

print(*memo[:n])

## 1 1 2 3 5 8 13 21 34 55

最初のmemoがちょっと雑だな。。

キャッシュを利用して見る

##キャッシュ利用

from functools import lru_cache

@lru_cache(maxsize=1000)

def fib(n):

if n <= 1:

return 1

else:

f = fib(n-1)+fib(n-2)

print(f,end=' ')

return f

fib(10)

便利すぎる!!