自分のブログに書いた Fibonacci Algorithm Benchmark の補足。
それぞれの実装のパフォーマンスはベンチマークの記事を参考にしてください

また fib(-1) のような負の引数に対する処理は仕様に入れてないので注意

そもそものフィボナッチ関数

やっぱり定義を表現するのに Haskell が一番楽だ

fib.hs

fib :: Int -> Integer
fib 0 = 0
fib 1 = 1
fib n
  | n < 0 = undefined
  | otherwise = fib (n - 1) + fib (n - 2)

定義通りの再帰実装

function fib(n) {
  return n < 2 ? n : fib(n - 2) + fib(n - 1);
}

処理時間: O(n^2)
スタックオーバーフロー: 余裕で起きる
メモリ消費: コールスタックが…

メモ化+再帰

var _fibs = [0, 1];

function fib(n) {
  if (n < 0) {
    return undefined;
  }
  if (_fibs.length > n) {
    return _fibs[n];
  }
  var l = _fibs.length;
  _fibs[l] = _fibs[l - 1] + _fibs[l - 2];
  return fib(n);
}

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

処理時間: O(n)
スタックオーバーフロー: 起きうる（メモ化してない領域が大きい場合）
メモリ消費: _fibs が GC されない
フィボナッチ数列を生成する分には効率が良い

蓄積変数をもったイテレータによる再帰

function fib(n) {
  function iterator(a, b, c) {
    return c <= 0 ? b : iterator(b, a + b, c - 1);
  }
  return iterator(1, 0, n);
}

処理時間: O(n)
スタックオーバーフロー: 起きる
メモリ消費: コールスタックが…
メモ化ほどメモリリークはしないが、フィボナッチ数列を for(;;) で回して生成するコストが大きい。
これでスタックオーバーフローになる以前の時点で、すべて戻りは Infinity なのでこれ以上パフォーマンス上げても無意味感はある

逐次平方処理による再帰

SICP やったことある人ならすぐこれを思い出すはず

function fib(n) {
  function iterator(a, b, p, q, c) {
    return c <= 0 ? b :
      (c % 2 === 0) ?
        iterator(a, b, p * p + q * q, (q + 2 * p) * q, c / 2) :
        iterator((a + b) * q + a * p, a * q + b * p, c - 1);
  }
  return iterator(1, 0, 0, 1, n);
}

処理時間: O(log2 n)
スタックオーバーフロー: ほとんど起きないが、起きうる（凄まじく巨大な数で）
メモリ消費: ほとんどしないが、ないわけではない
この実装だとメモ化するのは飛び飛びになるのであまり効果なし

fib(1000) -> fib(500) -> fib(250) -> fib(125) -> fib(124)
-> fib(62) -> fib(31) -> fib(30) -> fib(15) -> fib(14)
-> fib(7) -> fib(6) -> fib(3) -> fib(2) -> fib(1) -> fib(0)

と再帰する

蓄積変数による手続き

function fib(n) {
  var a, b, c, tmp;
  a = 1;
  b = 0;
  c = n;
  while (c > 0) {
    tmp = a + b;
    a = b;
    b = tmp;
    c--;
  }
  return b;
}

処理時間: O(n)
スタックオーバーフロー: なし
メモリ消費: 関数内の変数のみ (GC されやすい参照の弱さ)
日用レベルではこれで充分

当然非再帰版の方が速い。またスタックオーバーフローが起きない故に、こちらは無茶な数を引数に与えても、とりあえず計算は終了するまでやる。

メモ化 + 手続き

var _fibs = [0, 1];

function fib(n) {
  if (n < 0) {
    return undefined;
  }
  var l = _fibs.length;
  while (n >= l) {
    _fibs[l] = _fibs[l - 1] + _fibs[l - 2];
    l++;
  }
  return _fibs[n];
}

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

処理時間: O(n)
スタックオーバーフロー: なし
メモリ消費: _fibs が GC されない
フィボナッチ数列を作る場合、こちらがより処理の効率は良い
再帰版と同様、メモリの問題はある。

逐次平方処理による手続き

function fib(n) {
  var a, b, p, q, c, tmp_1, tmp_2;
  a = 1;
  b = 0;
  p = 0;
  q = 1;
  c = n;

  while (c > 0) {
    if (c % 2 === 0) {
      tmp_1 = p * p + q * q;
      tmp_2 = (q + 2 * p) * q;
      p = tmp_1;
      q = tmp_2;
      c = c / 2;
    } else {
      tmp_1 = (a + b) * q + a * p;
      tmp_2 = a * q + b * p;
      a = tmp_1;
      b = tmp_2;
      c--;
    }
  }
  return b;
}

処理時間: O(log2 n)
スタックオーバーフロー: なし
メモリ消費: 関数内の変数のみ (GC されやすい参照の弱さ)

関数呼び出しのコスト分だけ、こちらの方が再帰版よりも速い。
ベンチマークで検証した結果だと、 60fps で処理できる限界が再帰版で fib(997146) に対し、非再帰版で fib(5265634) と、五倍の開きがある。

(最速) fib(n) ≒ φ ^ n /√5

黄金比φをn乗して√5で割る

var SQRT_5 = Math.sqrt(5);
var PHY = (1 + SQRT_5) / 2;

function fib(n) {
  return Math.round(Math.pow(PHY, n) / SQRT_5);
}

処理時間: O(log2 n)
スタックオーバーフロー: するわけがない
メモリ消費: 定数 PHY と SQRT_5 くらいなので呼び出しによる増大無し (定数化した方がJITコンパイラ最適化がかかりやすい)
一番速いし無駄にリソース食わず、しかもコードも最短で、条件分岐や繰り返し無し
しかし、これが必要になるほどの局面も javascript には無い

オーダー数は非再帰の逐次平方と同じだけど、この場合ネイティブ実装の Math.pow を呼んでいるのと、js 側で条件分岐が無い分だけ高速になる

得られる教訓

javascript は発見されているアルゴリズムを再帰で書くと大体遅いし、コールスタック溢れさせうるので基本避ける
メモ化したり、別の手法と組み合わせて速度を出せるものの、普通に関数呼び出しを減らす努力をした方が効果がある。
頑張ってアルゴリズムに工夫を凝らし終わった後にそもそもの効率が良いアルゴリズムを知って馬鹿みたいな気分になる。
最適化に苦心する前に基礎のアルゴリズムを追求すべき
苦心する前に "そもそもこれは js でやるべきなのか" も頭に入れておくべき

Fibonacci 関数のそれぞれの実装