Maximum call stack size exceeded RangeError when recursive function is countable in javascript

Question

I've created a script to divide numbers with the chosen number of decimal places. Everything works fine unless I set a huge number of decimal places. The file run via Node.js gives up when the decimal numbers array length reaches ~2400, Chrome gives up on ~1900.

I simplified my code and the script sample below throws Maximum call stack size exceeded RangeError up on ~20000 decimal numbers array length. I thought that this Error throws when the loop or recursive function is called endlessly, but in my case there is a countable number of iterations. It may be a huge number but my module is intended to do the math operations on big numbers.

Why does it happen and Can I avoid this RangeError to occur?

var decimals = [];
var max = 20000;

recurse();

function recurse() {
  decimals.push(Math.floor(Math.random()*10));
  if(decimals.length === max) return;
  recurse();
}

If this isn't an exercise, it would make more sense as a non-recursive function with a `for` loop. Then you won't need any outside variables — MCMastery, Jun 05 '18 at 15:50
@Pawel, I think you will find this Q&A helpful https://stackoverflow.com/a/43596323/633183 — Mulan, Jun 05 '18 at 16:12

Matus Dubrava · Accepted Answer · 2018-06-05T16:07:58.710

4

No, there is a limit to how many function calls you can place on to the call stack so even if your recursive function has a reachable base case, it will still throw the error if the number of recursive calls is too big.

One workaround would be to use technique called trampoline where you don't perform recursive call directly inside of the function, but insted return a new function that is then executed in a loop until the base case is reached.

Using this technique, your function can perform as many recursive calls as you want because you are not placing more of those function calls to the call stack at the same time, so it will not overflow.

var decimals = [];
var max = 20000;

function _recurse(){
  decimals.push(Math.floor(Math.random()*10));
  if(decimals.length === max) return;
  return () => _recurse();
}

const trampoline = fn => (...args) => {
  let res = fn(...args);
  while (typeof res === 'function') { res = res(); }
  return res;
}

const recurse = trampoline(_recurse);

recurse()

console.log(decimals);

Note that your problem can be solved without the use of recursion in a much simpler way, using loops. For example:

function createRandomSequence(amount) {
  const decimals = [];
  for (let i = 0; i < amount; i++) {
    decimals.push(Math.floor(Math.random()*10));
  }
  return decimals;
}

console.log(createRandomSequence(10));

edited Jun 05 '18 at 16:07

answered Jun 05 '18 at 15:48

Matus Dubrava

13,637
2
38
54

1

It looks too complex but works great :) I'll have to read more about `trampoline` and thank you for your explanation. It clarifies the code – Paweł Jun 05 '18 at 16:06
@user633183 That is correct, but only if your function doesn't take any arguments (which of course is the case here) but if it did, then you would need this structure. – Matus Dubrava Jun 05 '18 at 16:25
1

@Paweł I've just written about this if it works for you https://dev.to/pichardoj/do-you-even-recurse-and-if-you-do-do-you-do-it-safely-4mef – J. Pichardo Jun 05 '18 at 16:49
@J.Pichardo I am not sure how, in this case, you can grow the heap size. As soon as the `_recurse` function returns new function, that new function creates a closure , right, but that new function is immediately executed and thrown away together with its closure. So at any point of execution, you are holding only one closure. You would need to dynamically create new properties (each with a unique name) in each iteration to actually grow heap size. Or am I missing something? – Matus Dubrava Jun 05 '18 at 17:05
@MatusDubrava you are right, I did not read well, guess I'm low on coffee. – J. Pichardo Jun 05 '18 at 17:07

score 3 · Answer 2 · answered Jun 05 '18 at 15:57

3

Just use a regular loop, or something like:

 const random = length => Array.from({ length }, () => Math.floor(Math.random() * 10));

const decimals = random(20000);

answered Jun 05 '18 at 15:57

Jonas Wilms

132,000
20
149
151

KooiInc · Answer 3 · 2018-06-05T16:11:06.933

1

Concerning the call stack: see this web page

If it's 20,000 (pseudo random) decimals you're after, you can also use something like:

var maxDecimals = 20000;
var decimals = Array.from({length: maxDecimals})
  .map(v => Math.floor(Math.random()*10));
  
console.log(decimals);

edited Jun 05 '18 at 16:11

answered Jun 05 '18 at 16:03

KooiInc

119,216
31
141
177

Maximum call stack size exceeded RangeError when recursive function is countable in javascript

3 Answers3