CODEWITHSUNDEEP
javascriptrecursion
Shubh
Shubh

Reputation: 6741

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?

Upvotes: 3

Views: 2363

Answers (2)

Aadit M Shah
Aadit M Shah

Reputation: 74204

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.

Upvotes: 7

Ashish Patel
Ashish Patel

Reputation: 345

I would suggest to use Javascript Promise for this.

function nextListItem2 (list) {
    return new Promise(function(resolve, reject) {
        var item = list.pop();
        if(item) {
            console.log(item);
            return nextListItem(list);
        } else {
            resolve();
        }
    });
}

nextListItem2(list);

Upvotes: 0

Related Questions