スポンサーリンク

再帰を使った場合

下記がサンプルコードになります。
f(n)からf(n-1)とf(n-2)を再帰的に呼び出します。
重複計算もあって、n=45で13秒かかっています。

下記が実行結果になります。

スポンサーリンク

動的計画法のメモ化再帰を使った場合

重複計算を避け、一度計算したら結果を記憶させておき、計算結果を再利用していきます。
0で初期化した配列を定義しておき、計算されていれば(配列の要素が!0なら)再利用し、
計算されていなければ(配列の要素が0なら)計算していきます。
n=45で1秒以下で収まりました(time関数なので精度は秒単位です)。

下記がサンプルコードになります。

下記が実行結果になります。

動的計画法で漸化式を使った場合

漸化式を使って、n=0, 1, 2, 3.......と、順にループ処理をして計算していきます。
数学的な思考になれていると、こちらの方が自然な方法に感じるかもしれません。
再帰処理のように重複計算もないので、計算量も削減できます。

下記が実行結果になります。

スポンサーリンク