javascript - 递归调用导致调用堆栈溢出但事件队列不会溢出？

Question

我最近遇到了这段代码:

如果数组列表过大，下面的递归代码会导致堆栈溢出。您如何解决这个问题并仍然保留递归模式？

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

      if (item) {
          // process the list item...
          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。因此，该方法从头到尾处理，没有直接递归调用，因此调用堆栈保持清晰，无论迭代次数如何。

那么，事件队列处理了调用堆栈的开销？是否存在最大数量的事件，在此之后事件队列无法再接收更多事件，以及该数量与它可以堆叠的函数调用的调用堆栈限制相比如何？另外，是否有其他方法可以实现相同的目的？

Answer 1

So, the overhead of the call stack was being handled by the event queue?

不完全是。一次只有一个事件排队。不同之处在于它忘记了它是从哪里调度的 - 如果它必须保留该信息，它也会耗尽内存。

对于递归，编译器/解释器可能会做类似的事情，丢弃不再需要的调用堆栈作为tail call optimisation。 .例如，Safari 浏览器已经实现了这一点。

Also, is there an alternative way to achieve the same thing?

当然是一个循环:-)

function nextListItem = function() {
    for (var item = list.pop(), item, item = list.pop()) {
        // process the list item...
    }
}

How can you fix this and still retain the recursive pattern?

您可以使用 trampolining手动执行 TCO。

function call(run) {
    return { done: false, run };
}
function stop(value) {
    return { done: true, value };
}
function runTrampoline(cont) {
    while (!cont.done) cont = cont.run();
    return cont.value;
}

var list = readHugeList();
function nextListItem() {
    return runTrampoline(nextListItemT());
}
function nextListItemT() {
    var item = list.pop();
    if (item) {
        // process the list item...
        return call(nextListItemT);
    } else {
        return stop();
    }
}