JavaScript之斐波那契数列的实现

一个斐波那契（Fibonacci）数字是之前两个斐波那契数字之和。最前面的两个数字是0和1。

用函数方式表示：

1.递归函数

var fabonacci = function(n){
  return n < 2 ? n : fabonacci(n - 1) +  fabonacci(n - 2);
}

for(var i = 0; i < 10; i++){
  document.writeln('//' + i +':' + fabonacci(i));
}

缺点：
这样是可以实现的，但它做了很多无谓的工作。fabonacci函数被调用了453次。我们调用了11此，而它自身调用了442此去计算可能已被计算过的值。

2.闭包

我们在一个名为memo的数组里保存我们的存储结果，存储结果可以隐藏在闭包中。当函数被调用时，这个函数首先检查结果是否已经存在，如果已经存在，就立即返回这个结果。

var fibonacci = function(){
  var memo = [0,1];
  var fib = function(n){
    var result = memo[n];
    if(typeof result !== 'number'){
      result = fib(n - 1) + fib(n - 2);
      memo[n] = result;
    }
    return result;
  }
  return fib;
}();

for(var i = 0; i <= 10; i++){
  var fibona = fibonacci(i);
  console.log(fibona)
}

缺点：

这个函数返回同样的结果，但是只被调用了29次。我们调用了它11次，它调用了自己18次去取得之前存储的结果。