javascript - javascript中的尾递归

Question

我对 JS 不是很有经验。但与大多数人一样，我有时需要向浏览器添加一些额外的功能。

在寻找其他问题的答案时，我遇到了 this answer at SO.答案与the responder受到高度赞扬，按照 SO 标准，这意味着它们非常可靠。引起我注意的是，在“整理”变体中，它使用尾递归来循环函数:

(function myLoop (i) {          
   setTimeout(function () {   
      alert('hello');          //  your code here                
      if (--i) myLoop(i);      //  decrement i and call myLoop again if i > 0
   }, 3000)
})(10);     

在我看来，这看起来像是糟糕的工程。用递归解决命令式/OO语言中的非递归问题是自找麻烦。 10 次或 100 次迭代应该是安全的。但是 10000 或无限循环呢？在 Erlang 和 Haskell 这样的纯函数式语言中，我知道尾递归会在编译时转换为循环，并且不会向堆栈添加额外的帧。据我所知，并非所有编译器(例如 C/C++ 或 Java)都是这种情况。

JS呢？在没有 SO 风险的情况下使用尾递归是否安全？还是这取决于运行脚本的实际解释器？

Answer 1

您提供的示例没有任何尾递归。考虑:

(function loop(i) {
    setTimeout(function main() {
        alert("Hello World!");
        if (i > 1) loop(i - 1);
    }, 3000);
}(3));

1. 我已将内部函数命名为 main，将外部函数命名为 loop。
2. loop 函数立即被调用，值为 3。
3. loop 函数只做一件事。它调用 setTimeout 然后返回。
4. 因此，对 setTimeout 的调用是尾调用。
5. 现在，main 在 3000 毫秒后由 JavaScript 事件循环调用。
6. 当 main 被调用时，loop 和 setTimeout 都已完成执行。
7. main 函数有条件地调用 loop，并使用递减值 i。
8. 当main调用loop时，是尾调用。
9. 但是，无论递归 100 次还是 10000 次，堆栈大小都不会增加太多而导致溢出。原因是当您使用setTimeout 时，loop 函数会立即返回。因此，当 main 被调用时，loop 不再在堆栈上。

视觉解释:

|---------------+ loop (i = 3)
                |---------------+ setTimeout (main, 3000)
                                |
                |---------------+ setTimeout return
|---------------+ loop return
~
~ 3000 milliseconds
~
|---------------+ main (i = 3)
                |---------------+ alert ("Hello World!")
                                |
                |---------------+ alert return
                | i > 1 === true
                |---------------+ loop (i = 2)
                                |---------------+ setTimeout (main, 3000)
                                                |
                                |---------------+ setTimeout return
                |---------------+ loop return
|---------------+ main return
~
~ 3000 milliseconds
~
|---------------+ main (i = 2)
                |---------------+ alert ("Hello World!")
                                |
                |---------------+ alert return
                | i > 1 === true
                |---------------+ loop (i = 1)
                                |---------------+ setTimeout (main, 3000)
                                                |
                                |---------------+ setTimeout return
                |---------------+ loop return
|---------------+ main return
~
~ 3000 milliseconds
~
|---------------+ main (i = 1)
                |---------------+ alert ("Hello World!")
                                |
                |---------------+ alert return
                | i > 1 === false
|---------------+ main return

这是发生了什么:

1. 首先，调用 loop(3) 并在返回 main 后调用 3000 毫秒。
2. main 函数调用 loop(2) 并在返回后 3000 毫秒再次调用 main。
3. main 函数调用 loop(1) 并在返回后 3000 毫秒再次调用 main。

因此，堆栈大小不会因为 setTimeout 而无限增长。

阅读以下问题和答案以获取更多详细信息:

What's the difference between a continuation and a callback?

希望对您有所帮助。

附言ECMAScript 6 (Harmony) 中的 JavaScript 将进行尾调用优化，这可能是列表中最受期待的功能。