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? http://stackoverflow.com/questions/2805172/what-are-the-js-recursion-limits-for-firefox-chrome-safari-ie-etc — kemicofa ghost, Oct 22 '14 at 07: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 ghost, Oct 22 '14 at 07: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, Oct 22 '14 at 07:53
Same here, it's pretty much the console that hangs the process. — elclanrs, Oct 22 '14 at 07:57

Aadit M Shah · Accepted Answer · 2018-10-05T08:45:27.433

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 05 '18 at 08:45

answered Oct 22 '14 at 07:47

Aadit M Shah

72,912
30
168
299

*"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. – T.J. Crowder Oct 22 '14 at 07:49
1

@T.J.Crowder No engine has TCO nowadays afaik, but it is standard in ES6, so it will be coming in the future. – elclanrs Oct 22 '14 at 07:50
Thanks @Aadit! I guess I first need to understand what is [tail call elimination](http://stackoverflow.com/questions/1240539/what-is-tail-recursion-elimination) :( +1 for the [solution](http://jsfiddle.net/shubh0602/tvdohjrn/) thought , never thought `setTimeout` would be of help here :) – Shubh Oct 22 '14 at 07:53
2

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. – T.J. Crowder Oct 22 '14 at 07:58
@T.J.Crowder Indeed, a `setTimeout` every 100 iterations would be a good optimization. – Aadit M Shah Oct 22 '14 at 08:00

score 0 · Answer 2 · answered Jul 19 '16 at 18:47

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

Understanding recursion in javascript and alternative

2 Answers2

Linked