javascript 中的尾递归

Question

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

在寻找其他问题的答案时，我发现 this answer at SO. The answer and the responder 得到了高度评价，按照 SO 标准，这意味着它们非常可靠。引起我注意的是，在 "neatened up" 变体中，它使用尾递归来循环函数：

(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);

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

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

Answer 1

这不是一个明确的递归。 myLoop 的每次调用都会在另一个执行堆栈上执行（有点像一个单独的线程）并且不依赖于之前的调用。与原始答案一样：

The setTimeout() function is non-blocking and will return immediately.

有一个 myLoop 函数，它启动一个超时和一个匿名函数，它处理超时后应该执行的操作。 myLoop() 返回的值（将是 undefined）在以后的调用中不会使用。

Answer 2

该代码本身不是递归的，恰恰相反，它使用 continuation passing 来消除尾调用。这是一个没有 setTimeout 的例子：

// naive, direct recursion

function sum_naive(n) {
  return n == 0 ? 0 : n + sum_naive(n-1);
}

try {
  sum_naive(50000)
} catch(e) {
  document.write(e + "<br>")
}


// use CPS to optimize tail recursive calls

function sum_smart(n) {
  
  function f(s, n) {
    return n == 0 ? s : function() { return f(s+n, n-1) };
  }
  
  var p = f(0, n)
  
  while(typeof p == "function")
    p = p()
    
  return p;
}

document.write(sum_smart(50000) + "<br>")

CPS 通常用于不支持开箱即用的语言中的尾递归优化。 Javascript 的 setTimeout 基本上将当前的延续和 "throws" 带到主线程。一旦主线程准备就绪，它 "catches" 继续并在恢复的上下文中运行代码。

Answer 3

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

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

我已将内部函数命名为 main，将外部函数命名为 loop。
立即调用 loop 函数，值为 3。
loop函数只做一件事。它调用 setTimeout 然后 returns.
因此，对 setTimeout 的调用是尾调用。
现在，main 在 3000 毫秒后由 JavaScript 事件循环调用。
当调用 main 时，loop 和 setTimeout 都已完成执行。
main 函数有条件地调用 loop 并减去 i 的值。
当main调用loop时，是尾调用
但是，不管你递归100次还是10000次，堆栈大小永远不会增加到溢出的程度。原因是当你使用setTimeout时，loop函数立即returns。因此，在 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

这是正在发生的事情：

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

因此，由于setTimeout，堆栈大小永远不会无限增长。

阅读以下问答以了解更多详情：

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

希望对您有所帮助。

P.S。尾调用优化将在 ECMAScript 6 (Harmony) 中实现 JavaScript，它可能是列表中最受期待的功能。

Answer 4

目前，大多数 JS 运行时不支持尾递归。因此，除非您确切知道您的代码将在哪个运行时运行，否则依靠尾递归来避免 "Maximum call stack size exceeded" 错误是不安全的。

它是 not supported in Node（版本 >6.4 和 <8 除外，它可以通过标志启用）。

Safari 版本 11 和 12 似乎也支持它，但是 no other major browsers do。

博士。 Axel Rauschmayer 在他的博客 2ality on 2018-05-09 中提到广泛的支持可能永远不会到来。

javascript 中的尾递归

Tail recursion in javascript

javascript

recursion

tail-recursion