javascript - 如何防止 JavaScript 执行堆栈被过多的递归级别填满？

Question

以下函数将我的 Chromium 浏览器卡在 50 输入上，而在 10 左右的低得多的输入上完美返回。我相信这是由于递归级别太多而导致的结果，这些级别的递归调用填满了堆栈，并且不允许代码完成执行。

var Y = function (f) {
  return f(function (x) {
    return Y(f)(x);
  });
};

console.log(Y(function (f) {
  return function (n) {
    if (n === 0) {
      return 0;
    } else if (n === 1) {
      return 1;
    } else {
      return f(n - 1) + f(n - 2);
    } 
  };
})(10)); // replace 10 by 50 to reproduce issue

例如，JavaScript 没有像Scheme 那样的尾部调用优化。那么，我们如何在 JavaScript 中编写递归函数，使其不会在输入非常大的情况下崩溃呢？

(请忽略 Y 函数。这只是我正在做的一些学习的一部分。传递给 console.log() 的 lambda 是等效的到一个简单的显式递归斐波那契函数。)

http://jsbin.com/decusumoyiwa/1/edit

Answer 1

我会尝试这样的事情:

var level = 0;

function f(n) {
  level++;
  if (level > 50) { // or another value other than 50
    throw '...';
  }
  var val = _f(n);
  level--;
  return val;
}

function _f(n) {
  if (n === 0) {
    return 0;
  } else if (n === 1) {
    return 1;
  } else {
    return f(n - 1) + f(n - 2);
  } 
}

然后像以前一样使用 f 函数，并且您可以在对 f 的调用周围使用 try-catch block 来检测函数何时到达太深的点.

(我没有测试过，但我认为它会起作用)