Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Stack overflow while processing large array in recursive function

Tags:

javascript

Why does the following recursive code cause a stack overflow if the array list is too large? How can I fix this and still retain the recursive pattern?

var list = readHugeList();

var nextListItem = function() {
    var item = list.pop();

    if (item) {
        // process the list item...
        nextListItem();
    }
};
like image 687
Bibek Sharma Avatar asked Jul 06 '15 15:07

Bibek Sharma


People also ask

Does recursive function cause stack overflow?

The most-common cause of stack overflow is excessively deep or infinite recursion, in which a function calls itself so many times that the space needed to store the variables and information associated with each call is more than can fit on the stack.

How does recursive function prevent stack overflow?

In order to prevent stack overflow bugs, you must have a base case where the function stops make new recursive calls. If there is no base case then the function calls will never stop and eventually a stack overflow will occur. Here is an example of a recursive function with a base case.

How many recursive calls cause stack overflow error?

So trouble will start at about 10^5 recursive calls (as in your case). Some sites use large values of stack size (>100MB).

Is recursion slower than iteration Javascript?

Since recursion makes use of the stack data structure and due to this overhead, it is slower than the iteration code format.


1 Answers

This will sound weird, but use a setTimeout.

Like this:

//fill it with 50000 elements
var list = Array(50001).join('1.1').split('.');

var nextListItem = function() {
    var item = list.pop();

    if (item) { //should be list.length

        // recursion here!
        setTimeout( nextListItem, 0 );

    }
};
nextListItem();

The recursion now is endless!

Notice that some browsers don't like that 0 there.
As a side-effect, your code won't block the browser.

like image 196
Ismael Miguel Avatar answered Oct 04 '22 17:10

Ismael Miguel