理解 javascript 和替代中的递归 [英] Understanding recursion in javascript and alternative

问题描述

为什么我的浏览器在以下代码中的 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(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

我无法从谷歌找到我的问题的直接答案，所以尽管从 SO 专家那里得到了帮助.我假设它与浏览器内存有关，因为我可以看到循环以极快的速度开始，然后慢慢减慢并变得无响应.但不知道为什么?

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?

推荐答案

JavaScript 没有尾调用消除.因此，如果您递归地遍历列表，您将浪费大量资源.最终，您甚至可能会耗尽堆栈空间.

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:

延续和回调有什么区别?

更快的解决方案(由 T.J. Crowder 建议):

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

循环更加缓慢，因为它以 100 个项目的形式打印到控制台.但是它的执行速度要快得多.

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

这篇关于理解 javascript 和替代中的递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！