メモ化フィボナッチ

フィボナッチ数は fib(k) = fib(k-1) + fib(k-2) で決まります。この式をそのまま再帰にすると、数行で書けるのに、n を 40 にした途端に返ってこなくなります。式は正しいのに遅い。その理由を数えるところから始めます。

fib(5) を出すのに、fib(2) を 3 回計算している

fib(5) は fib(4) と fib(3) を呼び、fib(4) はまた fib(3) と fib(2) を呼びます。

fib 3 が 2 回、fib 2 が 3 回出てきます。しかも 2 回目の fib 3 は、1 回目とまったく同じ計算を最初からやり直しています。呼び出しの総回数を数えると、次のように伸びます。

n が 10 増えるごとに、およそ 123 倍です。答えは n + 1 種類しかないのに 3 億回計算しているのだから、無駄なのは計算の中身ではなく、同じ問いを何度も出していることのほうです。

2 回目からは、書き留めた答えを読む

対策は 1 つだけです。出した答えをその場で書き留めておき、次に同じ問いが来たら計算せずに読み出します。例として、組み合わせの数で試します。comb(n, k) は comb(n-1, k-1) + comb(n-1, k) で決まり、これも素朴に書くと同じ重複が起きます。

書き留める場所を用意し、答える前に覗き、返す前に書き込む。この 3 つだけです。同じ (n, k) は一度しか計算されなくなるので、計算回数は答えの種類の数までしか増えません。

こうして途中の答えを覚えておく手を メモ化、fib(k) = fib(k-1) + fib(k-2) のように自分自身で自分を表す式を 漸化式、小さいほうから順に埋めていくやり方を ボトムアップ と呼び、これらを使う設計法をまとめて 動的計画法 と言います。

書き留めた紙を、次の人に渡してしまう

書き留める場所を関数の外に作ると、前の呼び出しの結果が次の呼び出しにも残ります。同じ計算をする関数なら得に見えますが、途中で条件が変わる問題では前の答えが混ざり、原因の分かりにくい間違いになります。書き留める場所は、外から呼ばれる関数の中で作るのが安全です。

やってみよう

fibMemo(n) を書いてください。fib(0) は 0、fib(1) は 1、それ以外は 1 つ前と 2 つ前の和です。書き留める場所を用意し、答える前に覗いて、返す前に書き込む形にします。辞書でも、長さ n + 1 の配列でも構いません。n が 30 でも一瞬で返れば成功です。

1. fib(0) = 0、fib(1) = 1、それ以外は fib(k) = fib(k-1) + fib(k-2) を満たすこと
2. メモ化を使い、各 k についての計算が 1 回で済むようにすること (計算量 O(n))
3. n = 30 でも一瞬で結果が返ること (素朴再帰では数秒かかる)