フィボナッチ数列を出力するコード(1)
| 再帰による方法

※コードはJavaScriptで記載する。

フィボナッチ数列を出力するコードを書いてみよう。

フィボナッチ数列とは?

1つ前の項と2つ前の項を、足していく数列である。

手法

再帰

再帰呼び出しを使ったコードを見てみよう。

関数

function fib(n){
if (n < 2) {
return n;
}
return fib(n - 1) + fib(n - 2);
}

関数呼び出し

for(var i = 1;i < 10;i++) {
console.log(fib(i));
}

出力

1
1
2
3
5
8
13
21
34

計算量

  • 重複する計算が発生する

例えばnが4の場合、fib(4)の呼び出しで、fib(3)、fib(2)が呼ばれ、fib(3)の呼び出しで、fib(2)、fib(1)が呼ばれる。

fib(4)の呼び出しで、結果的にfib(2)が2回重複して呼ばれてしまい、無駄な計算が発生している。

  • nが大きくなるほどfibを呼ぶ回数が増えていく=時間計算量が急激に増えていく

以下は、nと、fib呼び出し回数の推移である。

nが大きくなるほど、時間計算量が指数的に増え、実行時間が伸びていく。

n = 1 → 1回
n = 2 → 3回
n = 3 → 5回
n = 4 → 9回
n = 5 → 15回
n = 6 → 25回
n = 7 → 41回
n = 8 → 67回
n = 9 → 109回

n番目のフィボナッチ数を計算するのに、それ以前のn-1個のフィボナッチ数を再計算しており、関数内で再帰的なfib関数の呼び出しを2回行っている。

計算量は、0(2 ^ n)になる。

nが増えれば増えるほど、計算が極端に重くなっていく。

どのようにすれば、計算量を減らすことができるだろうか?

結果のキャッシュ

fib(n)の結果を、変数にキャッシュしておき、再計算しないようにすれば、計算量を減らせるのではないか?

関数

// キャッシュ用配列の初期化
var fibs = [];
function fib(n){
if (n < 2) {
return n;
}
// 配列のキャッシュを用いる
if (fibs[n] != undefined) {
return fib[n];
}
fibs[n] = fib(n - 1) + fib(n - 2);
return fibs[n];
}

fibsという配列を作り、一回でも計算したことのあるfib(n)に関しては、同じ計算をせずにキャッシュから取得するように変更した。

計算量を0(n)に抑え、高速化することができた。