为什么带有setTimeout的函数不会导致堆栈溢出 [英] why does a function with setTimeout not lead to a stack overflow

问题描述

我正在编写一个处理大量数据的测试.令我惊讶的是，如果我在函数中添加了setTimeout，它将不再导致堆栈溢出(对于该站点是多么合适).这怎么可能，代码似乎真的是递归的.每个setTimeout调用都会创建自己的堆栈吗?

I was writing a test for handling huge amounts of data. To my surprise, if I added a setTimeout to my function, it would no longer lead to a stack overflow (how appropriate for this site). How is this possible, the code seems to be really recursive. Is every setTimeout call creating it's own stack?

是否可以在不增加所需内存的情况下实现此行为(异步并按顺序处理庞大的数组/数字)?

Is there way to achieve this behavior (handle a huge array/number asynchronous and in order) without increasing the needed memory?

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

推荐答案

因为它不再递归.至少从技术上来说不是.

Because it is no longer recursive. At least not technically.

源代码的确看起来是递归的，因此程序员可以编写类似递归的代码，但是从CPU的角度来看，它不再是递归的.它会按循环顺序进行处理.

The source code does look recursive so a programmer may write such code as if it is recursive but from the point of view of the CPU it is no longer recursive. It is processed sequentially in a loop.

一个递归函数调用自己.发生这种情况时，堆栈会不断增加，直到最后一个函数返回为止.在函数返回之前，不会从栈中删除函数的栈框架(现在让我们忽略忽略闭包)，因为递归函数调用其自身，直到返回对自身的调用，它才会返回.这就是导致堆栈增长的原因.

A recursive function calls itself. What happens when this happens is that the stack keeps increasing until the last function returns. A function's stack frame isn't removed from the stack until the function returns (let's ignore closures for now) so because recursive function calls itself it won't return until that call to itself returns. This is what causes the stack to grow.

诸如Lisp，Haskell和Scala之类的语言认识到在某些情况下可以在递归时释放堆栈框架.通常，如果递归调用是函数中的最后一条指令，并且未对返回值进行任何其他处理，则可以删除当前堆栈帧，因为在递归函数返回后将不再使用它.因此，此类语言实现了所谓的尾部递归:无限制递归而无需增加堆栈的能力.

Languages such as Lisp, Haskell and Scala recognize that there are some cases where a stack frame can be released while doing recursion. Generally, if the recursive call is the last instruction in the function and no other processing is done to the return value you can remove the current stack frame because it will no longer be used after the recursive function returns. Therefore, such languages implement what's called tail recursion: the ability to recurse infinitely without growing the stack.

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

This is especially useful for very pure functional languages where the only programming structure you have is functions because without the existence of statements you cannot have loop statements or conditional statements etc. Tail recursion makes infinite loops in Lisp possible.

但是，Javascript没有尾递归.因此，这不会影响递归在Javascript中的行为.我提到这一点是为了注意，并非所有递归都需要增加堆栈.

However, Javascript does not have tail recursion. So this does not affect how recursion behaves in Javascript. I mention this to note that not all recursion need to grow the stack.

Timer函数(例如 setTimeout()和 setInterval())不会调用传递给它们的函数.他们不仅不立即打电话给他们，甚至根本不打电话给他们.他们所做的只是将函数与何时应调用该函数的信息一起传递给事件循环.

Timer functions such as setTimeout() and setInterval() does not call the functions passed to them. Not only do they not call them immediately, they don't call them at all. All they do is pass the function to the event loop along with information of when should the function be called.

事件循环本质上是javascript的核心.当且仅当不再有要执行的javascript时，解释器才进入事件循环.您可以将事件循环视为解释器的空闲状态.事件循环不断检查事件(I/O，UI，计时器等)并执行事件附带的相关功能.这是您传递给 setTimeout()的函数.

The event loop is essentially the core of javascript. The interpreter enters the event loop if and only if there is no more javascript to execute. You can think of the event loop as the idle state of the interpreter. The event loop continuously checks for events (I/O, UI, timer etc.) and execute the relevant functions attached to the event. This is the function you passed to setTimeout().

因此，根据上述事实，我们可以看到通过 setTimeout 进行的递归"实际上不是递归.

So with the facts given above we can see how "recursion" via setTimeout is not really recursion.

1. 首先，您的函数调用 setTimeout 并将其自身传递给它.

setTimeout 将函数引用保存到事件侦听器列表，并设置计时器以触发将触发函数的事件

setTimeout saves the function reference to a list of event listeners and sets up the timer to trigger the event which will trigger the function

您的函数继续并返回，请注意，尚未调用递归"函数.自函数返回以来，其堆栈框架已从堆栈中删除.

Your function continues and returns, note that the "recursed" function is not yet called. Since your function returns it's stack frame gets removed from the stack.

JavaScript进入事件循环(不再需要处理JavaScript).

Javascript enters the event loop (there's no more javascript to process).

您的函数的计时器到期，并且事件循环调用它.重复执行直到停止调用 setTimeout

Timer for your function expires and the event loop calls it. Repeat until you stop calling setTimeout

这篇关于为什么带有setTimeout的函数不会导致堆栈溢出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！