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

Question

I'm starting study about Google Apps Script, and in my first function (a simple recursive Fibonacci), I'm receiving the following error:

RangeError: Maximum call stack size exceeded

Ok, ok expected risk using a recursive approach, can anybody help me where I mistake?

My code below:

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

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

Answer 1

There are two recursive steps in the algorithm of the Fibunacci sequence.

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

So even for a relatively small number a lot of frames are pushed onto the call stack. Here is a visualization:

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

Consequently you rather quickly exhaust the call stack.

Please note that Fibonacci numbers are more naturally expressed with corecursion a.k.a. unfolding:

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

This is still not stack safe though. Since Javascript doesn't pursue tail call elimination you would have to use a trampoline.