prog*sig

F(1) = 1
F(2) = 1
F(3) = 2 = 1+1
F(4) = 3 = 1+2
F(5) = 5 = 2+3
という感じで、1と2は例外で>2の時はF(n-1)-F(n-2)の値となる数列

上の式からそのまま導くと以下のような感じ。

function fib(n){
    if(n <= 2){
        return 1;
    }else{
        return fib(n-1) + fib(n-2);
    }
}
for(var i=1;i<10;i++){
    console.log(fib(i));
}

fibを再帰させてる*2なので数字が大きくなるとやばそう。
F(n-1)とF(n-2)は途中で同じ計算をやってるので、毎回やるのはもったいないからキャッシュしてみる。
メモ化というらしい

var fibs = {};
function fib(n){
    if(fibs[n]) return fibs[n];
    if(n <= 2)  return 1;
    return fibs[n] = fib(n-1) + fib(n-2);
}
for(var i=1;i<10;i++){
    console.log(fib(i));
}

404 Blog Not Found:アルゴリズム百選 - フィボナッチ数列にO()を学ぶ

http://blog.livedoor.jp/dankogai/archives/50958771.html