Shubh Shubh - 4 months ago 20
Javascript Question

Understanding recursion in javascript and alternative

Why does my browser slows down when this

list
data is huge in below code :

var list = [];

/*
Creating some huge dummy data
Interstingly, when I change the value of i from 10000
to 100000, the browser hangs(becomes unresponsive)
*/
for(i=0;i<10000;i++){
list.push(i);

}

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

if (item) {
console.log(item);
// process the list item...
nextListItem();
}
};
nextListItem(); // Commented this as browser becomes unresponsive.


jsbin

I could not find a straight answer to my question from google, so though off getting help from SO experts. I am assuming it has something to do with browser memory as I can see the loop starts in a great speed and slowly slows down and becomes unresponsive. But not sure why?

Answer

JavaScript doesn't have tail call elimination. Hence if you loop through a list recursively you'll be wasting a lot of resources. Eventually you might even end up exhausting the stack space.

One possible solution to this problem is to call the tail call asynchronously so that the main function finishes execution before the tail call function begins execution. This ensures that the stack space doesn't increase:

var list = [];

for (var i = 0; i < 10000; i++) list.push(i);

var start = new Date;

nextListItem();

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

    if (item) {
        console.log(item);
        setTimeout(nextListItem, 0);
    } else console.log(new Date - start);
}

See the following question for more details:

What's the difference between a continuation and a callback?


Edit: A faster solution (as suggested by T.J. Crowder):

var list = [];

for (var i = 0; i < 10000; i++) list.push(i);

var start = new Date;

nextListItem();

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

    if (item) {
        console.log(item);
        if (item % 100) nextListItem();
        else setTimeout(nextListItem, 0);
    } else console.log(new Date - start);
}

The loop is more sluggish as it prints to the console in bursts of 100 items. However it completes execution much faster.

Comments