javascript - 使用 setTimeout 避免堆栈溢出

Question

我发现了以下问题 here :

The following recursive code will cause a stack overflow if the array list is too large. How can you fix this and still retain the recursive pattern?

答案:

The potential stack overflow can be avoided by modifying the nextListItem function as follows:

var list = readHugeList();

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

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

The stack overflow is eliminated because the event loop handles the recursion, not the call stack. When nextListItem runs, if item is not null, the timeout function (nextListItem) is pushed to the event queue and the function exits, thereby leaving the call stack clear. When the event queue runs its timed-out event, the next item is processed and a timer is set to again invoke nextListItem. Accordingly, the method is processed from start to finish without a direct recursive call, so the call stack remains clear, regardless of the number of iterations.

谁能给我解释一下:

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

Answer 1

这只是 trampolines 的替代品，这反过来只是 TCO 的替代品.

当您在 Javascript 中调用一个函数时，您会在调用堆栈中添加一个框架。该框架包含有关函数范围内的变量及其调用方式的信息。

在我们调用一个函数之前，调用栈是空的。

-------

如果我们调用函数 foo，那么我们会在堆栈顶部添加一个新帧。

| foo |
-------

当 foo 完成执行时，我们再次将帧从堆栈中弹出，再次将其留空。

现在，如果 foo 依次调用另一个函数 bar，那么我们需要在堆栈上添加一个新帧，而 foo 正在执行。

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

希望您能看到，如果函数递归调用自身，它会不断向调用堆栈的顶部添加新帧。

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

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

因为 setTimeout 是一个异步操作，它不会阻塞你的函数，这意味着 nextListItem 将被允许完成并且它的帧可以从调用堆栈中弹出——阻止它成长。递归调用将由 event loop 处理。相反。

此模式有用吗？ 调用堆栈的最大大小 depends on your browser , 但它可以低至 1130。如果您想使用递归函数处理具有几千个元素的数组，那么您可能会冒破坏调用堆栈的风险。

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

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

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

while(recur = recur()) {}