通过使用setTimeout避免堆栈溢出(Avoiding stack overflow by using setTimeout)

通过使用setTimeout避免堆栈溢出(Avoiding stack overflow by using setTimeout)

我在这里发现了以下问题：

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

答案是：

通过修改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。 因此，该方法从头到尾不经过直接递归调用即可处理，因此调用堆栈保持清晰，无论迭代次数如何。

有人可以向我解释一下：

这个用例是否可行 为什么long数组会导致堆栈溢出

I've found the following 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?

And the answer:

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.

Can somebody please explain to me:

whether this use case is ever practical why long array can cause stack overflow

最满意答案

这对蹦床来说只是一个很好的选择，而这对于TCO来说只是一个黑客的选择。

当你用Javascript调用一个函数时，你可以在调用堆栈中添加一个框架。 该框架包含关于函数范围内的变量以及它如何被调用的信息。

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

-------

如果我们调用函数foo ，那么我们添加一个新的框架到栈顶。

| foo | -------

当foo完成执行时，我们再次弹出框架，再次将其留空。

现在，如果foo又调用另一个函数bar ，那么我们需要在堆栈中添加一个新帧，同时foo正在执行。

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

希望你可以看到，如果一个函数递归地调用它，它会一直向调用堆栈的顶部添加新的帧。

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

递归函数会一直添加框架，直到它们完成处理，或者它们超出调用堆栈的最大长度，导致溢出。

因为setTimeout是一个异步操作，所以它不会阻塞你的函数，这意味着nextListItem将被允许​​完成并且它的框架可以从调用栈中弹出 - 防止它增长。 递归调用将使用事件循环来处理。

这种模式有用吗？ 调用堆栈的最大大小取决于您的浏览器 ，但最大可能低至1130.如果您想使用递归函数处理包含几千个元素的数组，那么您可能会吹动调用堆栈。

蹦床使用类似的技术，但不是将工作分流到事件循环，而是返回一个调用下一​​次迭代的函数，然后可以使用while循环来管理调用（这不会影响堆栈）。

var nextListItem = function() { var item = list.pop(); if (item) { // process the list item... return nextListItem; } }; while(recur = recur()) {}

This is just a hacky alternative to trampolines, which in turn are just a hacky alternative to TCO.

When you call a function in Javascript, you add a frame to the call stack. That frame contains information about the variables in the scope of the function and how it was called.

Before we call a function, the call stack is empty.

-------

If we call function foo, then we add a new frame to the top of the stack.

| foo | -------

When foo finishes executing, we pop the frame off the stack again, leaving it empty again.

Now, if foo in turn calls another function bar, then we'll need to add a new frame onto the stack, whilst foo is executing.

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

Hopefully you can see that if a function calls itself recursively it keeps adding new frames to the top of the call stack.

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

Recursive functions will keep adding frames until either they finish processing, or they exceed the max length of the call stack, resulting in an overflow.

Because setTimeout is an asynchronous operation, it doesn't block your function, which means nextListItem will be allowed to finish and its frame can be popped off the call stack—preventing it from growing. The recursive call will be handled with the event loop instead.

Is this pattern ever useful? The max size for the call stack depends on your browser, but it can be as low as 1130. If you wanted to process an array with a few thousand elements using a recursive function, then you'd risk blowing the call stack.

Trampolines use a similar technique, but rather than offloading the work to the event loop, you return a function which calls the next iteration instead, then the calls can be managed with a while loop (which doesn't affect the stack).

var nextListItem = function() { var item = list.pop(); if (item) { // process the list item... return nextListItem; } }; while(recur = recur()) {}