Pythonアルゴリズム

Pythonの再帰とメモ化によるフィボナッチ数

このレッスンでは、再帰でフィボナッチ数を計算し、メモ化で計算済みの結果をもう一度計算しないようにします。

  • 中級
  • 約2分で読めます
  • 実行できるサンプル 1 件

はじめに

どんな問題を解決するか

フィボナッチ数列の再帰的な定義は美しいのですが、そのままコードにするととても遅くなります。40番目の項を求めるだけで、同じ小さな計算を何億回も繰り返すからです。メモ化を使えばたった1行で解決でき、動的計画法の大事な考え方も学べます。

身近なたとえ

メモ化は、出した答えをすべてノートに書き留めておく生徒のようなものです。もう一度 fib(5) を聞かれても計算し直さず、ノートに書いた答えを読みます。どの問題も、解くのは一度だけです。

ノートからコードへ
@cache📓 答えを記録するノートを持つ
fibonacci(number - 1) + fibonacci(number - 2)🧮 2つの小さな問いを使って解く
if number < 2: return number🛑 最初の2つの答えは分かっている
fibonacci(10)⚡ 小さな答えはどれも1回だけ計算:速い
結果は最初に求めたときに保存し、そのあとは使い回します。
ひと言でいうと

メモ化とは、関数呼び出しの結果を引数ごとに保存しておき、同じ引数でまた呼ばれたら、計算し直さずに保存した結果を返す手法です。

重要なポイント

  1. if number < 2: return number は最初の2項、0と1を返します。
  2. fibonacci(number - 1) + fibonacci(number - 2) は、数列の定義をそのまま書いたものです。
  3. functools の @cache はすべての結果を覚えているので、各 fibonacci(k) は1回しか実行されません。
  4. @cache がないと fibonacci(10) の計算で関数が177回呼び出されますが、あれば11回で済みます。

どんな場面で使う?

  • 同じ部分問題を何度も解くことになる再帰関数。格子上の経路、硬貨の両替、単語の分割などです。
  • 動的計画法のもとになっている考え方を学ぶ。
  • 同じ引数で何度も呼ばれる純粋関数(同じ引数なら必ず同じ結果を返す関数)を速くする。

使わなくてよいとき

  • 副作用がある、または時間とともに結果が変わる関数:キャッシュが古い答えを返してしまいます。
  • 非常に深い再帰:キャッシュがあっても fib(5000) は再帰の上限を超えることがあります。ループならそれを避けられます。

動きで理解する

ステップを押して各呼び出しを追いましょう。fibが同じ小さな値を何度も計算していることに注目してください。これが単純な実装が遅い理由です。

サンプルコード

コードを実行 →
main.py
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. 空のリスト、要素が1つだけのリスト、重複した値を含むリストで試す。
  2. 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
  3. 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
Pythonコンパイラで実行 →

よくある間違い

キャッシュなしの再帰

同じ値が何度も計算し直され、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 のレビューも受けられます。

すべてのチャレンジ