从 Fibonacci 看堆栈溢出

探索一下，一个简单的斐波那契（Fibonacci）函数的实现能考到 JavaScript 的什么知识？

面试官：熟悉原生 JavaScript 把？写一个 Fibonacci 的实现？

小白：

这还不容易，我闭着眼就能写出五种语言的 Fibonacci 实现，用递归（recursion）实现起来简洁又美观：

1
2
3

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

面试官：

恩…你用到了递归，你知道用递归的坏处是什么吧？

小白：

比起循环，递归的效率低，但是 Knuth 大神说过：

We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.

也罢，面试官看来想让我写一个简单的循环实现，不如递归高大上，但同样实用：

function getFibonaccis2(n) {
  var i;
  var fib = [0, 1];

  for (i = 2; i < n; i++) {
    fib[i] = fib[i - 2] + fib[i - 1];
  }

  return fib;
}

面试官：恩（并没有想让你写一个循环版本出来）。那我问你递归在 JavaScript 中会出现什么特殊的性能问题吗，有的话要怎么修改递归实现的代码？

小白：敲头~！原来这厮要考我的是 JavaScript 运行栈的问题，如果函数递归调用过多会导致堆栈溢出（stack overflow），还好我码过 JavaScript Cookbook：

var getFibonaccis3 = (function () {
  var fib = [0, 1];

  return function (n) {
    if (typeof fib[n] !== 'number') {
      fib[n] = fib[n - 1] + fib[n - 2];
    }

    return fib[n];
  };
}());

面试官眼前一亮：（黝黑），可是你这里还是函数迭代调用函数，和之前的有什么不同呢？

小白：这里我的确还是函数迭代调用函数，但是我利用闭包（closure）实现了一个存活的私有变量对象 fib，保存每一次生成的新的值。

由于在 JavaScript 中原始类型放在栈中，object 放在堆中，我这里用空间来换时间，大大减少了函数迭代调用的次数，所以优化了运行栈的问题。

但我还可以写出一个更好的实现（闭包 + 循环）：

var getFibonaccis4 = (function () {
  var fib = [0, 1]; // lazy function definition

  return function (n) {
    var i;

    if (n >= fib.length) {
      for (i = fib.length; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
      }
    }

    return fib[n];
  };
}());

面试官：（这货竟然扯了这么多，不过我想考察的：

JavaScript 编程素养
JavaScript 运行栈的认识
堆和栈的区别
立即执行函数（IIFE）创建局部作用域
closure 的理解和使用

的目的达到了）

You got my offer~!