为什么带有 setTimeout 的函数不会导致堆栈溢出

Question

我正在编写一个处理大量数据的测试。令我惊讶的是，如果我在我的函数中添加了一个 setTimeout，它就不会再导致堆栈溢出（对于这个站点来说多么合适）。这怎么可能，代码好像真的是递归的。每个 setTimeout 调用都会创建自己的堆栈吗？

有没有办法在不增加所需内存的情况下实现这种行为（处理巨大的 array/number 异步和有序）？


function loop(
    left: number,
    callbackFunction: (callback: () => void) => void,
) {
    if (left === 0) {
        return
    }
    console.log(left)
    callbackFunction(() => {
        loop(left - 1, callbackFunction)
    })
}

function setTimeoutCallback(callback: () => void) {
    setTimeout(
        () => {
            callback()
        },
        Math.random() * 5
    )
}

function nonSetTimeoutCallback(callback: () => void) {
    callback()
}

loop(100000, setTimeoutCallback) //no stack overflow

loop(100000, nonSetTimeoutCallback) //stack overflow

Answer 1

第一个不是递归的（虽然乍一看很像）

让我们简化并想象一个递归方法f，我们将调用深度限制为 5。第二个示例是递归的，类似于

f(){ f(){ f(){ f(){ f(){ }}}}}

在另一个例子中，我们创建了 5 个超时 f 作为回调（该数组并不完全准确，它更像是一个具有随机超时值的优先级队列 - 但这种抽象有助于理解问题）

[f, f, f, f, f]

javascript 不是多线程的，所以所有 5 个函数都被一个接一个地调用。最终，函数将创建另一个超时，当发生这种情况时，新的 f 回调将添加到列表（或队列）中。

所以基本上，超时在这里序列化递归。请注意，在这种情况下，f 将被调用近 200 万次，因为除最后一次外，所有其他人都会将另一个 f 添加到列表中，该列表也将被执行。

Answer 2

因为它不再递归了。至少在技术上不是。

源代码看起来确实是递归的，因此程序员可能会编写这样的代码，就好像它是递归的，但从 CPU 的角度来看，它不再是递归的。它在循环中按顺序处理。

递归和堆栈

递归函数调用自身。当发生这种情况时，堆栈会一直增加，直到最后一个函数 returns。直到函数 returns（让我们暂时忽略闭包），函数的堆栈帧才会从堆栈中移除，因此因为递归函数调用自身，它不会 return 直到调用自身 return秒。这就是导致堆栈增长的原因。

尾递归

Lisp、Haskell 和 Scala 等语言认识到在某些情况下可以在执行递归时释放堆栈帧。通常，如果递归调用是函数中的最后一条指令并且没有对 return 值进行其他处理，则可以删除当前堆栈帧，因为在递归函数 return 之后将不再使用它秒。因此，此类语言实现了所谓的尾递归：无需增加堆栈即可无限递归的能力。

这对于非常纯的函数式语言特别有用，在这种语言中，您唯一的编程结构是函数，因为如果不存在语句，您就无法拥有循环语句或条件语句等。尾递归使 Lisp 中的无限循环成为可能。

然而，Javascript没有尾递归。所以这不会影响 Javascript 中的递归行为。我提到这一点是为了注意并非所有递归都需要增加堆栈。

计划

setTimeout() 和 setInterval() 等定时器函数不会调用传递给它们的函数。他们不仅不立即打电话给他们，甚至根本不打电话给他们。他们所做的就是将函数传递给事件循环以及何时调用该函数的信息。

事件循环本质上是javascript的核心。当且仅当没有更多 javascript 可执行时，解释器才进入事件循环。您可以将事件循环视为解释器的空闲状态。事件循环不断地检查事件（I/O、UI、定时器等）并执行附加到事件的相关函数。这是您传递给 setTimeout().

的函数

设置超时

根据上面给出的事实，我们可以看出 "recursion" 通过 setTimeout 并不是真正的递归。

首先你的函数调用 setTimeout 并将自身传递给它。
setTimeout 将函数引用保存到事件侦听器列表，并设置定时器来触发将触发函数的事件
你的函数继续 returns，注意 "recursed" 函数还没有被调用。 因为你的函数 returns 它的堆栈框架被从堆栈中移除。
Javascript进入事件循环（没有更多的javascript处理）。
您的函数的计时器到期，事件循环调用它。重复直到你停止调用 setTimeout

为什么带有 setTimeout 的函数不会导致堆栈溢出

why does a function with setTimeout not lead to a stack overflow

javascript

stack-overflow

asynchronous

settimeout

large-data

递归和堆栈

尾递归

计划

设置超时