Fibonacci(フィボナッチ)数列の計算

フィボナッチ数列の計算は古い話題で、いろいろなアルゴリズムの本に登場しています.今日この博文を書く出発点はネット上でMIT 6.00の公開授業を見て、ちょうどいくつかの構想を整理して、結局いくつかのものがあって、自分で実践してからやっと深い認識があります.
通常の再帰計算
これは最も簡単なアルゴリズムで、フィボナッチ数列の定義に基づいてfib(n)=fib(n-1)+fib(n-2)が得られ、具体的なコードは以下の通りである.(説明が必要なのは、コードにはパラメータのチェックが省略されており、実際のコードでは必要である).
 

function fib(n) {
    return (n === 0 || n === 1) ? 1 : fib(n - 1) + fib(n - 2);
}

 
ルックアップ・テーブルの再帰計算の使用
通常の再帰計算では多くの繰返し計算が実行され、テーブルを検索することで以前に計算したfib(k)の値が取得され、繰返し計算が回避されます.コードは次のとおりです.
 

function fib_m(n) {
    var f = arguments.callee, m = f._m || (f._m = {0:1, 1:1});
    return m[n] || (m[n] = f(n-1) + f(n-2));
}

 
ここでは,ルックアップテーブルをJavaScriptメソッドオブジェクトの属性とする.
反復計算
より簡単な方法は、反復を使用して計算することです.コードは次のとおりです.
 

function fib_i(n) {
    if (n === 0 || n === 1) { return 1; }
    var a = 1, b = 1, c;
    for (var i = 2; i <= n; i++) {
        c = a + b;
        b = a;
        a = c;
    }
    return c;
}

ここでは3つの変数を用い,aとbはそれぞれf(n−1)とf(n−2),cはf(n)を表す.