Error traversing large arrays in JavaScript without timeout

Question

When I'm am executing the following code in Node.js, I get the folliowing error:

RangeError: Maximum call stack size exceeded

This is the code:

var arr = [];
for (var i = 0; i <= 1000000; i++)
    arr.push(i);

function nextStep(index) {
    if (index === arr.length) {
        return;
    } else {
        console.log(index);
    }
    nextStep(++index);
}

nextStep(0);

I have no clue what is happening, but near index = 17938, the execution terminates.

Using a setTimeout() helps. What could be wrong here?

You are calling nextStep inside nextStep and get a stack overflow. — some, Nov 12 '13 at 18:43
Check this http://stackoverflow.com/questions/7826992/browser-javascript-stack-size-limit/7828803#7828803 — PSL, Nov 12 '13 at 18:50

score 7 · Accepted Answer · answered Nov 12 '13 at 18:50

7

You are entering a recursive function. This means that the first function won't return until all the other functions have returned. So if you had four items,

fn(item1)
    calls ->  fn(item2)
                  calls ->  fn(item3)
                                calls ->  fn(item4)

As you can see, the nesting builds up and up. This is called the stack. There is a maximum size for the stack, to prevent infinite recursion and runaway processes. You have found it with 17938.

This is an inherent flaw with recursion. It can be a stylish way to approach a task, but it has its limitations. The best way to correct it is to use a loop instead:

for (var i = 0; i < arr.length; i++) {

Using setTimeout also works, because the function is not called from the function itself, but is executed with a new stack. However, it will have significantly lower performance than a loop or than a normal recursive function.

answered Nov 12 '13 at 18:50

lonesomeday

233,373
50
316
318

I love how this was the only answer that actually suggested a solution. – Nick Mitchinson Nov 12 '13 at 18:59
@lonesomeday So, I could put the `nextStep(++index);` in a callback function as an argument like calling `doSomeOtherStuffFirst(function(){ nextStep(++index); }));`, and then it would work? – sprijk Nov 12 '13 at 19:31
Because I really would like to traverse this array by executing a task for every element in a serial order. – sprijk Nov 12 '13 at 19:37
@sprijk Not unless there's something that will start a new call stack. – lonesomeday Nov 12 '13 at 19:39
@lonesomeday Is there a way of traversing this array in serial, working on every element separately, and calling back to `nextStep(++index);`? – sprijk Nov 12 '13 at 19:45
@lonesomeday ah, got it :) – sprijk Nov 12 '13 at 19:53
@sprijk I don't understand what you mean by in serial. There is no way of traversing this array recursively. – lonesomeday Nov 12 '13 at 19:53
@lonesomeday Well, to do a task with the current element, and then continue to the next element when the task is done. – sprijk Nov 12 '13 at 20:12
@sprijk Yes! The best way is with a loop. – lonesomeday Nov 12 '13 at 20:23

some · Answer 2 · 2013-11-12T19:02:54.630

Calling nextStep inside nextStep causes a stack overflow since you never return from the function (unless you found the end of the array, and if the array is too big you will never reach it until the stack overflows).

An example: You are going to move all the stones from one place to another. Your function is like going to the place where the stones are and pick up one to be delivered to another place. But before you can deliver the stone, you must pick up another, and before you can deliver that you need to pick up another... and soon you are carrying 17938 stones. That is a little bit to heavy and you get crushed under all the stones. (or in the javascript case you get an exception)

When you use setTimetout it is like you are going to the place, pick up a stone, and make a note that you should pickup another stone. Then you deliver the stone. After that you look at your notes and see that you should pick up at stone. And you can do this 1000000 times since you are only carrying one stone at a time.

It does "return" in the end of the array, but quits already at 17938. Wouldn't it be more like memory exhaustion? Using setTimout() in here solves the problem... — sprijk, Nov 12 '13 at 18:52
@sprijk You get an exception, not a return. You get the exception because there isn't enough room in the stack. The stack is limited, so technically it is a memory exhaustion of a specific type of memory. — some, Nov 12 '13 at 18:55

score 0 · Answer 3 · answered Nov 12 '13 at 18:52

There's a certain number of calls that can be made, based on the call stack of different browsers. Most likely, you are testing your code in Chrome, since, I believe, it has the call stack near 20.000. Your code will execute the nextStep function more than 20.000 times (1 million), which means that if your function will not return something until it reaches the call stack limit of that particular browser, it will generate the error that you are getting.

Error traversing large arrays in JavaScript without timeout

3 Answers3