データ構造とアルゴリズム
フィボナッチ数を求める関数 fib(n) を「n が1以下なら n を返し、そうでなければ fib(n−1) + fib(n−2) を返す」と再帰で定義した。fib(5) を呼んだとき、fib が呼ばれる回数は最初の呼び出しを含めて何回か。
- A6回
- B9回
- C15回
答えと解説を見る
正解：C. 15回
fib(n) の呼び出し回数を C(n) とすると、C(0) = C(1) = 1、C(n) = 1 + C(n−1) + C(n−2) なので、C(2) = 3、C(3) = 5、C(4) = 9、C(5) = 15 です。同じ値を何度も計算し直すため、回数は n に対して指数関数的に増え、fib(30) では約269万回になります。計算した値を表に覚えておくメモ化(動的計画法)を使えば、計算は fib(0)〜fib(5) の6通りで済み、呼び出しも9回(2n − 1)に減ります。6回は異なる引数の数、9回はメモ化した場合の呼び出し回数です。
- A. 異なる引数 fib(0)〜fib(5) の数で、同じ値の再計算を数えていません。
- B. メモ化して、一度計算した値を表から返す場合の呼び出し回数です。
- C. 正しい。C(n) = 1 + C(n−1) + C(n−2) から、C(5) = 15 です。