Pythonの再帰とメモ化によるフィボナッチ数
このレッスンでは、再帰でフィボナッチ数を計算し、メモ化で計算済みの結果をもう一度計算しないようにします。
はじめに
どんな問題を解決するか
フィボナッチ数列の再帰的な定義は美しいのですが、そのままコードにするととても遅くなります。40番目の項を求めるだけで、同じ小さな計算を何億回も繰り返すからです。メモ化を使えばたった1行で解決でき、動的計画法の大事な考え方も学べます。
身近なたとえ
メモ化は、出した答えをすべてノートに書き留めておく生徒のようなものです。もう一度 fib(5) を聞かれても計算し直さず、ノートに書いた答えを読みます。どの問題も、解くのは一度だけです。
@cache📓 答えを記録するノートを持つfibonacci(number - 1) + fibonacci(number - 2)🧮 2つの小さな問いを使って解くif number < 2: return number🛑 最初の2つの答えは分かっているfibonacci(10)⚡ 小さな答えはどれも1回だけ計算:速いメモ化とは、関数呼び出しの結果を引数ごとに保存しておき、同じ引数でまた呼ばれたら、計算し直さずに保存した結果を返す手法です。
重要なポイント
if number < 2: return numberは最初の2項、0と1を返します。fibonacci(number - 1) + fibonacci(number - 2)は、数列の定義をそのまま書いたものです。functoolsの@cacheはすべての結果を覚えているので、各fibonacci(k)は1回しか実行されません。@cacheがないとfibonacci(10)の計算で関数が177回呼び出されますが、あれば11回で済みます。
どんな場面で使う?
- 同じ部分問題を何度も解くことになる再帰関数。格子上の経路、硬貨の両替、単語の分割などです。
- 動的計画法のもとになっている考え方を学ぶ。
- 同じ引数で何度も呼ばれる純粋関数(同じ引数なら必ず同じ結果を返す関数)を速くする。
使わなくてよいとき
- 副作用がある、または時間とともに結果が変わる関数:キャッシュが古い答えを返してしまいます。
- 非常に深い再帰:キャッシュがあっても
fib(5000)は再帰の上限を超えることがあります。ループならそれを避けられます。
動きで理解する
ステップを押して各呼び出しを追いましょう。fibが同じ小さな値を何度も計算していることに注目してください。これが単純な実装が遅い理由です。
サンプルコード
from functools import cache
@cache
def fibonacci(number):
if number < 2:
return number
return fibonacci(number - 1) + fibonacci(number - 2)
print(fibonacci(10))
実行結果
55
コードの解説
デコレーター@cacheは、入力値ごとに関数の結果を自動で記憶します。fibonacci(8)を一度計算すれば、以降の呼び出しは保存された結果を使うだけです。これで実行時間は指数関数的なものからO(n)に減り、その代わりに結果を保存するためのO(n)のメモリを使います。
値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。
発展問題
下のヒントにしたがってコードを書き換えてみましょう。自分で変えて結果を確かめると、コードを読むだけよりずっと深く理解できます。
- 空のリスト、要素が1つだけのリスト、重複した値を含むリストで試す。
- 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
- 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
よくある間違い
キャッシュなしの再帰
同じ値が何度も計算し直され、fib(40) は何秒もかかります。
def fibonacci(number):
if number < 2:
return number
return fibonacci(number - 1) + fibonacci(number - 2)
@cache
def fibonacci(number):
if number < 2:
return number
return fibonacci(number - 1) + fibonacci(number - 2)
このレッスンを終えましたか?
学習済みにすると進み具合を記録できます。
チャレンジで練習する
このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。
すべてのチャレンジ