RangeError: Maximum call stack size exceeded on my first google script function

Question

我开始研究 Google Apps 脚本，在我的第一个函数（一个简单的递归 Fibonacci）中，我收到以下错误：

RangeError: Maximum call stack size exceeded

好的，好的，使用递归方法的预期风险，有人能帮我解决我的错误吗？

我的代码如下：

function FIBONACCI(input) {
  const number = parseInt(input);

  if (number < 2) { return number; }
  return FIBONACCI(number - 1) + FIBONACCI(number - 2);
}

Answer 1

斐波那契数列的算法有两个递归步骤。

return FIBONACCI(number - 1) + FIBONACCI(number - 2);
       ^^^^^^^^^^^^^^^^^^^^^   ^^^^^^^^^^^^^^^^^^^^^

因此，即使数量相对较少，也会将大量帧推送到调用堆栈中。这是一个可视化：

const log = x => (console.log(`fib(${x})`), x);

function FIBONACCI(input) {
  const number = parseInt(input);

  if (number < 2) { return number; }
  return log(FIBONACCI(number - 1)) + log(FIBONACCI(number - 2));
}

FIBONACCI("10");

因此，您很快就会耗尽调用堆栈。

请注意，使用 corecursion a.k.a 可以更自然地表达斐波那契数列。展开：

const fibs = i => {
  const go = (x, y, j) =>
    j === 1
      ? [x]
      : [x].concat(go(y, x + y, j - 1));

  return go(1, 1, i);
};

console.log(
  fibs(100)); // 55

虽然这仍然不是堆栈安全的。由于 Javascript 不追求尾调用消除，因此您将不得不使用蹦床。

RangeError: Maximum call stack size exceeded on my first google script function

RangeError: Maximum call stack size exceeded on my first google script function

javascript

functional-programming

google-apps

google-apps-script