Understanding recursion in javascript and alternative

Question

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?

Recursive functions are limited. I have over the years, tried using them but they are frowned upon in js due to this limit. What exactly are the limits? stackoverflow.com/questions/2805172/… — kemicofa
– kemicofa, Commented Oct 22, 2014 at 7:44
@Cerbrus I'm just pointing out the fact, that recursive functions are limited, reason why I posted it as a comment since it doesn't answer the performance question. — kemicofa
– kemicofa, Commented Oct 22, 2014 at 7:48
Without the console.log, I have no problem with the above in Chrome or IE11. Firefox does complain of too much recursion (it doesn't hang). — T.J. Crowder
– T.J. Crowder, Commented Oct 22, 2014 at 7:53

Aadit M Shah · Accepted Answer · 2018-10-05 08:45:27Z

7

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.

edited Oct 5, 2018 at 8:45

answered Oct 22, 2014 at 7:47

Aadit M Shah

74.5k31 gold badges177 silver badges311 bronze badges

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

5 Comments

T.J. Crowder Over a year ago

"JavaScript doesn't have tail call elimination." I don't think you can make a blanket statement like that. An engine can do any optimization it wants as long as the externally-observed results are in spec. Given how advanced modern engines are, I wouldn't rule out tail call elimination.

elclanrs Over a year ago

@T.J.Crowder No engine has TCO nowadays afaik, but it is standard in ES6, so it will be coming in the future.

Shubh Over a year ago

Thanks @Aadit! I guess I first need to understand what is tail call elimination :( +1 for the solution thought , never thought setTimeout would be of help here :)

T.J. Crowder Over a year ago

Doing the setTimeout on every loop will dramatically slow things down, as that's a 0-5ms delay (at least). Instead, a simple loop would be the best solution, or a setTimeout every hundred (or thousand) iterations, etc.

Aadit M Shah Over a year ago

@T.J.Crowder Indeed, a setTimeout every 100 iterations would be a good optimization.

Ashish Patel · Accepted Answer · 2016-07-19 18:47:21Z

0

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);

answered Jul 19, 2016 at 18:47

Ashish Patel

3451 silver badge9 bronze badges

Collectives™ on Stack Overflow

Understanding recursion in javascript and alternative

2 Answers 2

5 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related