フィボナッチ数をjavascriptで算出してみた。

はじめに

急にフィボナッチ数を解きたい！と思った。ということで、書いてみた。

オリジナル：フィボナッチ数(JavasScript)

• 5分で考えた、書いたコード

function fibonacci(p, n, max_num){
    if(n > max_num){
        return 0;
    }
    console.log(n);
    return fibonacci(n, n + p, max_num);
}
fibonacci(0, 1, 100)

本当にパッと思いついたもので、フィボナッチ数列の定義（アルゴリズム上での公式）を無視している。 このmax_numというのは、max_numまでの数値を算出するというモノ。普通は何番目のが欲しいか、ってのが引数になるよね。

引数の 0, 1 がきもいので、ちょっと変えた。

function fibonacci(max_num, p, n) {
    if(p === undefined) { p = 0;}
    if(n === undefined) { n = 1;}
    if(n > max_num) { return 0; }
    console.log(n);
    return fibonacci(max_num, n, n + p)
}
fibonacci(100)

デフォルト値を入力する感じ、ifが多くてパフォーマンスが落ちるかな。（この程度は気にしないレベルだと思うけど）

定義？を知った上で書きなおしてみる。

function fibonacci(n) {
    if(n < 2) {
        return 0;
    } else {
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

これが現実的な解答であるんだが、パフォーマンスがすごく悪いよね。俺のほうが早くてびっくりした。（厳密には違う解法だけど！！！）

メモ化を使ってみる

メモ化とは、一度計算した数値を配列に保存しておくことで、すぐに呼び出せるよね！ってやつ。

for で済ませるパターン

var _fibs = [0, 1];

function fib(n) {
  for(var i = _fibs.length; i <= n; i++){
    _fibs[i] = _fibs[i-1] + _fibs[i-2];
  }
}

function fibs(n) {
  fib(n);
  return _fibs.slice(0, n + 1);
}

fibs(10)

これでオッケーかな。グローバル変数を使うのは嫌なんだが...しょうがないかな。

次の記事には、「メモ化」で「再帰呼び出し」パターンのがある。

さいごに

今まで避けてきた再帰呼び出しを実際にやってみた。

意外と簡単にロジックが組め、すぐにコードで表現できるようになった。今回は少し、デフォルト値とか工夫してみた。こういうのも勉強になった。

フィボナッチ数列のような、数学が好きなので、次回もこういうやつをやってみたい。それと、Rubyで書きなおす。

頑張るぞぉ

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

波紋と螺旋とフィボナッチ: 数理の眼鏡でみえてくる生命の形の神秘

フェルマーの最終定理 (新潮文庫)