Fibonacci(斐波那契數列)的最佳實踐方式(JavaScript)

Fibonacci(斐波那契數列)的最佳實踐方式(JavaScript)

1)低級版本

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

　　基本上算到fibonacci(50), 就不行了, 老半天。

2) 進階版一

var fibonacci = function(n) {
    var cache = {};
    return function(n) {
        if (!cache[n])
            cache[n] = n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
        return cache[n];
    }
}();

　　利用閉包,緩存已計算好的值, fibonacci(200)不超過4ms

3) 進階版二

var fibonacci = function(n) {
    if (n == 0 || n == 1) {
        return n;
    } else {
        var cache = arguments[1] || {};
        if (!cache[n]) {
            cache[n] = fibonacci(n - 1, cache) + fibonacci(n - 2, cache);
        }
        return cache[n];
    }
}

　　傳遞緩存的數據, fibonacci(200) 不超過4ms

4) 終極版

var fibonacci = (function() {
  var cache = {};
  return function(n) {
    if (n == 0 || n == 1)
      return n;
    if (cache[n - 2] === undefined)
      cache[n - 2] = fibonacci(n - 2);
    if (cache[n - 1] === undefined)
      cache[n - 1] = fibonacci(n - 1);

    return cache[n - 1] + cache[n - 2];
  }
})();

　　遞歸緩存的數據,fibonacci(200) 不超過4ms