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
– MCMastery, Commented Jun 5, 2018 at 15:50
@Pawel, I think you will find this Q&A helpful stackoverflow.com/a/43596323/633183 — Mulan
– Mulan, Commented Jun 5, 2018 at 16:12

Matus Dubrava · Accepted Answer · 2018-06-05 16:07:58Z

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 5, 2018 at 16:07

answered Jun 5, 2018 at 15:48

Matus Dubrava

14.6k3 gold badges44 silver badges60 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Paweł Over a year ago

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

Matus Dubrava Over a year ago

@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.

J. Pichardo Over a year ago

@Paweł I've just written about this if it works for you dev.to/pichardoj/…

Matus Dubrava Over a year ago

@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?

J. Pichardo Over a year ago

@MatusDubrava you are right, I did not read well, guess I'm low on coffee.

Jonas Wilms · Accepted Answer · 2018-06-05 15:57:40Z

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 5, 2018 at 15:57

Jonas Wilms

139k20 gold badges164 silver badges164 bronze badges

Comments

KooiInc · Accepted Answer · 2018-06-05 16:11:06Z

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 5, 2018 at 16:11

answered Jun 5, 2018 at 16:03

KooiInc

124k32 gold badges145 silver badges181 bronze badges

Collectives™ on Stack Overflow

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

3 Answers 3

5 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related