フィボナッチ数列を関数で求める

昔から実装されてる古典的なフィボナッチ数列を求める関数の意味をじっくり考えてみました。

前置き

フィボナッチの実装には再帰を使う方法と、ループを使う方法の2通りがあります。いろいろと初めての方にはわからない言葉がでてきましたね。説明しておきます。

フィボナッチ数列とは1、1、2、3、5、8、13というように1から始まり、どの項もその前の2つの項の和となっている数列のことです。

再帰とは「関数が自身を自身で呼び出すこと」です。ちょっとイメージしづらいですね。とりあえず後々また出てくるのでとりあえず進みましょう。

まずは再帰による実装をしていきましょう。

再帰による実装

今回作る関数はfib(n)という関数です。フィボナッチ数列のn番目の数を返します。fib(1) == 1、fib(2) == 1、fin(3) == 2です。

fib(n)はフィボナッチ数列の定義から fib(n - 1) + fib(n - 2) を返す関数です。だから次のようになります。

var fib = function(n) {
    return fib(n - 1) + fib(n - 2);
};

ただ、このままでは無限ループしてしまいます。ではどうすればいいのでしょうか?

簡単です。関数呼び出しをやめればいいのです。関数呼び出しをやめるには初期条件を指定します。

フィボナッチ数列の1番目は1です。つまりfib(1) = 1です。nが1のときはfibを呼び出さずに1を返せばループがここで止まります。

ただしフィボナッチ数列の場合2つ初期条件を用意しなければなりません。なぜならfib(2)が呼び出されると、fib(2)は fib(1)とfib(0)を呼び出します。これではfib(0)から更にfib(-1)とfib(-2)が呼び出されてしまいます。だから、fib(2)は1を返すようにします。フィボナッチ数列の2番目は1なので合ってますね。

以上を踏まえると次のようになります。

var fib = function(n) {
    if (n === 1 || n === 2) return 1;
    return fib(n - 1) + fib(n - 2);
};

速度は出ません。

実は上の関数はとても遅いです。例えばfib(10)を呼ぶとfib(9)とfib(8)が呼ばれます。そしてfib(9)からfib(8)、fib(7)が、fib(8)からfib(7)、fib(6)が呼ばれます。このようにしていくと何度も呼ばれるものが出てきます。そして呼ばれるたびに計算していくと計算量が膨大になっていきます。

fib(n)は常に同じ値を返すので一度計算したらその結果を保存して再び呼ばれたらその値を返すようにすると無駄をなくせます。

var memo = [];
var fib2 = function(n) {
    if (memo[n]) return memo[n];
    if (n === 1 || n === 2) return 1;
    memo[n] = fib2(n - 1) + fib2(n - 2);
        return memo[n];
};

以上で再帰による実装は終わりです。

ループによる実装

どちらかというとこちらのほうが直感的でわかりやすいです。原理としては

1. 1つ前の項と2つ前の項を変数に入れておきます。
2. その2つを足して変数に入れます。
3. 1つ前の項と2つ前の項を入れている変数を更新します。
4. 2に戻ります。

あとは大して説明することもないのでコードを解説して行きたいと思います

var fib = function(n) { 
    var result = 1,bef1 = 1,bef2 = 1;
    for (var i = 1; i < n; i++) {
        result = bef1 + bef2;
        bef2 = bef1;
        bef1 = result;
    }
    return result;
};

resultという変数が 2でいれる変数です。 bef1が1で出てきた1つ前の項、bef2が2で出てきた2つ前の項です。ループの中では2、3を繰り返しています。2はresult=bef1+bef2の部分です。では3はどこかというとbef1=bef2、bef2=resultという部分です。この部分の意味はbef2に1つ前の項、bef1に今の項をいれています。なぜなら、次のループでは今の項が1つ前の項、1つ前の項が2つ前の項になるからです。

ちなみにこのループの方法は動的計画法と呼ばれています。ただ、wikiには「このように最終的にfib(0)とfib(1)の呼び出しに収束し、fib(0)とfib(1)の呼び出し回数の和が結果の値となる」などと意味不明な説明がされていたので自分で考えた結果上のようなwikiと同じコードとなりました。

終わりに

つまりwikiはもっと簡単に書くべきということです。