Codilityを解く #1 フィボナッチ数列

はじめに

最近、Codilityというプログラミングテストサイトを見つけて、色々な問題に取り組んでいます。
英語圏、外資系企業のプログラマー採用試験としても使われているみたいです。

問題

以下のJavaScriptコード（フィボナッチ数列の表示）の入出力の関係を崩さずに、
冗長な部分を省き、より速い動作のコードに書き換えよう。
（問題元：Codilityのトップページ）
※一般に公開されている問題で、実際の試験問題とは異なります。

Fibo_0.js

var yourself = {
    fibonacci : function(n) {
        if (n === 0) {
            return 0;
        }
        if (n === 1) {
            return 1;
        }
        else {
            return this.fibonacci(n - 1) +
                this.fibonacci(n - 2);
        }
    }
};

アプローチ

１．n=0,n=1の場合を分けなくてよい。

どちらもnの値を返すという同じ処理なので、分ける必要がない。
「nが1以下の時」と一括りにしてしまおう。

Fibo_1.js

var yourself = {
    fibonacci : function(n) {
        if (n <= 1) {
            return n;
        } else {
            return this.fibonacci(n - 1) +
                this.fibonacci(n - 2);
        }
    }
};

２．elseがいらない。

いちいちelseで分けなくても、n>1のときは勝手に処理してくれる。
n <= 1となれば、関数はnを返して停止する。
else{}も取り払ってしまおう。

Fibo_2.js

var yourself = {
    fibonacci : function(n) {
        if (n <= 1) {
            return n;
        }

        return this.fibonacci(n - 1) +
            this.fibonacci(n - 2);
    }
};

３．アキュムレータ関数でもっと簡単にする。

ここが難しい。
今の状態だと、反復動作が多すぎる。

【例】

fibonacci(n)をf( n )と表現する。

f( 4 )
= f( 3 ) + f( 2 )
= f( 2 ) + f( 1 ) + f( 1 ) + f( 0 )
= f( 1 ) + f( 0 ) + 1 + 1 + 0
= 1 + 0 + 1 + 1 + 0
= 3

右辺に出てくる「f( )」の数が、再帰呼出しの回数である。
n(≧2)の値1つごとに、2回の再帰呼出しが行われており、
その回数はnに対して指数関数的に増大する。→ O（n^2）

計算時間を、なんとか減らせないだろうか？
アキュムレータという、状態を保持する役割の関数を追加して減らしてみよう。

Fibo_3.js

var yourself = {
    fibonacci : function(n) {
        if (n <= 1) {
            return n;
        }

       return this.fibonacci_ac(n, 1, 0);
    },

    fibonacci_ac : function (n, prev, ac) {
        if (n <= 0) {
            return ac;
        }

        return this.fibonacci_ac(n - 1, ac, prev + ac);
    }
};

(例)：n = 4 (答えは3)

n	prev	ac
4	1	0
3	0	1
2	1	1
1	1	2
0	2	3

n=0の時のacが出力されるので、出力は3となり正解。
今までの方法(Fibo_2.jsまで)だと、nの数値1つごとに2回再帰呼び出しをしていたが、
この手法ならnの数値一つごとに1回に抑えられる。

n=4　のときの　ac = f( 0 )
n=3　のときの　prev = f( 1-1 ) = f( 0 )　ac = f( 1 )
...
n=1　のときの　prev = f( 3-1 ) = f( 2 )　ac = f( 3 )
n=0　のときの　prev = f( 4-1 ) = f( 3 )　ac = f( 4 )

常にf( n )の値をn = 0 から蓄積することで、いちいち計算する手間を省いている。
f( 3 )まで求めていれば、f( 2 )の値まで分かっているはず。

再帰呼び出しの回数は、表で言うn=3以下の行数なので、O(4)=4。
結果、nに対して線形関数的に増大する。→ O（n）

終わりに

アキュムレータのもうちょっと分かりやすい説明を考えています。
多分、関数ばらけさせなくても何とかなる。
調べ次第更新予定。