使用setTimeout避免堆栈溢出

Question

我在这里找到了以下问题:

如果数组列表太大,以下递归代码将导致堆栈溢出.你如何解决这个问题仍然保留递归模式？

答案是:

通过修改nextListItem函数可以避免潜在的堆栈溢出,如下所示:

var list = readHugeList();

var nextListItem = function() {
    var item = list.pop();

    if (item) {
        // process the list item...
        setTimeout( nextListItem, 0);
    }
};

由于事件循环处理递归而不是调用堆栈,因此消除了堆栈溢出.当nextListItem运行时,如果item不为null,则将超时函数(nextListItem)推送到事件队列并退出函数,从而使调用堆栈保持清零.当事件队列运行其超时事件时,将处理下一个项目并设置计时器以再次调用nextListItem.因此,在没有直接递归调用的情况下从开始到结束处理该方法,因此无论迭代次数如何,调用栈都保持清晰.

有人可以向我解释一下:

1. 这个用例是否实用
2. 为什么长数组会导致堆栈溢出

Answer 1

这只是蹦床的一种骇人听闻的替代品,而蹦床又只是TCO的一种替代品.

在Javascript中调用函数时,可以向调用堆栈添加一个框架.该框架包含有关函数范围内的变量及其调用方式的信息.

在调用函数之前,调用堆栈为空.

-------

如果我们调用函数foo,那么我们将新的框架添加到堆栈的顶部.

| foo |
-------

当foo完成执行,我们再次弹出框出栈,再次离开它空.

现在,如果foo依次调用另一个函数bar,那么我们需要在执行时将新帧添加到堆栈中foo.

| bar |
| foo |
-------

希望您可以看到,如果函数以递归方式调用自身,它会不断地将新帧添加到调用堆栈的顶部.

| ...          |
| nextListItem |
| nextListItem |
| nextListItem |
| nextListItem |
----------------

递归函数将继续添加帧,直到它们完成处理,或者它们超过调用堆栈的最大长度,从而导致溢出.

因为它setTimeout是一个异步操作,它不会阻止你的功能,这意味着nextListItem将允许完成它的框架可以从调用堆栈中弹出 - 防止它增长.将使用事件循环处理递归调用.

这种模式有用吗？调用堆栈的最大大小取决于您的浏览器,但它可以低至1130.如果您想使用递归函数处理具有几千个元素的数组,那么您冒着吹掉调用堆栈的风险.

Trampolines使用类似的技术,但不是将工作卸载到事件循环,而是返回调用下一次迭代的函数,然后可以使用while循环(不影响堆栈)来管理调用.

var nextListItem = function() {
  var item = list.pop();

  if (item) {
    // process the list item...
    return nextListItem;
  }
};

while(recur = recur()) {}