Understanding recursion in javascript and alternative - Stack Overflow

admin管理员组

文章数量:1022178

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(bees 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 bees 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 bees unresponsive. But not sure why?

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(bees 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 bees 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 bees unresponsive. But not sure why?

• javascript
• recursion

Share Improve this question Follow asked Oct 22, 2014 at 7:40 ShubhShubh 6,75199 gold badges5353 silver badges8686 bronze badges 6

• 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./questions/2805172/… – kockburn Commented Oct 22, 2014 at 7:44
• @Grimbode Thanks. This seems good... Let me read through... – Shubh Commented Oct 22, 2014 at 7:45
• 1 @Grimbode: That's not the problem here. – Cerbrus Commented Oct 22, 2014 at 7:46
• @Cerbrus I'm just pointing out the fact, that recursive functions are limited, reason why I posted it as a ment since it doesn't answer the performance question. – kockburn Commented Oct 22, 2014 at 7:48
• Without the console.log, I have no problem with the above in Chrome or IE11. Firefox does plain of too much recursion (it doesn't hang). – T.J. Crowder Commented Oct 22, 2014 at 7:53

 |  Show 1 more ment

2 Answers 2

Sorted by: Reset to default 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 pletes execution much faster.

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

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(bees 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 bees 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 bees unresponsive. But not sure why?

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(bees 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 bees 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 bees unresponsive. But not sure why?

• javascript
• recursion

Share Improve this question Follow asked Oct 22, 2014 at 7:40 ShubhShubh 6,75199 gold badges5353 silver badges8686 bronze badges 6

• 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./questions/2805172/… – kockburn Commented Oct 22, 2014 at 7:44
• @Grimbode Thanks. This seems good... Let me read through... – Shubh Commented Oct 22, 2014 at 7:45
• 1 @Grimbode: That's not the problem here. – Cerbrus Commented Oct 22, 2014 at 7:46
• @Cerbrus I'm just pointing out the fact, that recursive functions are limited, reason why I posted it as a ment since it doesn't answer the performance question. – kockburn Commented Oct 22, 2014 at 7:48
• Without the console.log, I have no problem with the above in Chrome or IE11. Firefox does plain of too much recursion (it doesn't hang). – T.J. Crowder Commented Oct 22, 2014 at 7:53

 |  Show 1 more ment

2 Answers 2

Sorted by: Reset to default 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 pletes execution much faster.

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 alternativeStack Overflow