RangeError: Превышен максимальный размер стека вызовов в моей первой функции скрипта Google - PullRequest
Новая
       20

RangeError: Превышен максимальный размер стека вызовов в моей первой функции скрипта Google

0 голосов
/ 29 февраля 2020

Я начинаю изучать Google Apps Script, и в моей первой функции (простой рекурсивной Фибоначчи) я получаю следующую ошибку:

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);
}

1 Ответ

2 голосов
/ 29 февраля 2020

В алгоритме последовательности Фибоначчи есть два рекурсивных шага. 

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 aka: 

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

Это все еще не безопасно в стеке. * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Время покажет '1023 *'

...