🧠 フィボナッチ数列とは？
フィボナッチ数列とは、以下のような規則で定義される数列です。
0, 1, 1, 2, 3, 5, 8, 13, ...
数式で書くとこう
F(n) = F(n-1) + F(n-2)
F(0) = 0, F(1) = 1
🐢 遅い再帰実装
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
シンプルだけど超遅いです。
例えば fib(40) を計算しようとすると、何十万回も同じ関数が呼ばれるため、爆遅になります。
⚡ 裏技：キャッシュ（メモ化）で爆速に！
✅ 方法①：functools.lru_cache を使う
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
これだけで 劇的に高速化されます。
print(fib(100)) # 354224848179261915075（即出る！）
🔥 なぜ速くなるの？
再帰関数の中で同じ引数が何度も計算されるのを、キャッシュして再利用してくれるからです。
例えば fib(10) を求めるとき、普通なら fib(8) を2回計算するところを、1回で済ませて再利用できます。
✅ 方法②：手動で辞書を使うメモ化（試験で lru_cache が使えないとき）
memo = {}
def fib(n):
if n in memo:
return memo[n]
if n <= 1:
result = n
else:
result = fib(n - 1) + fib(n - 2)
memo[n] = result
return result
memo に計算済みの結果を保存しながら進むことで、無駄な再計算を防ぎます。
✅ まとめ
| 実装 | 特徴 | 実行速度 |
|---|---|---|
| 普通の再帰 | シンプルだけど遅い | ❌ |
@lru_cache 使用 |
速くて楽 | ✅✅✅ |
| 手動メモ化 | 試験対応にも使える | ✅✅ |