JavaScript中的尾递归优化

Question

如果JavaScript中的递归步骤是块中的最后一个表达式，它只会优化为非递归循环（如果我理解正确）。这是否意味着以下代码中右侧的递归调用将被优化，而左侧的递归调用将不会被优化？

function fibonacci(n) {
  if(n < 2) return n;
  return fibonacci(n-1) + fibonacci(n-2);
}

- Ben Aston

---

定义“优化”。 - Niet the Dark Absol

改为循环而非利用调用栈。 - Ben Aston

@NiettheDarkAbsol 意味着该调用仅使用常量堆栈空间。 - cs95

好的。老实说，我不知道，但我只是想澄清一下，因为“优化”是一个非常通用的术语。例如，你可以通过意识到fibonacci（n-1）作为其自身递归的一部分几乎总是会调用fibonacci（n-2）来进行优化，所以你可以进行优化。或者你可以有一个known_fib列表，首先检查它，只有当一个数字不在列表中时才计算fibonacci()。（后者将把fibonacci（n-2）减少到单个查找）。 - Niet the Dark Absol

我不这么认为。上面的代码不能在循环中编写，除非采取另一种方法（解析器无法做到）。 - Jonas Wilms

由于两个术语都是递归的，我认为它不能被优化为非递归循环。除非所有术语都可以非递归地解决，否则这种情况只会发生在一个术语上。那个术语是否必须在右侧取决于优化器。 - Chris Walsh

Answer 1

这是否意味着在以下情况下，右递归调用将被优化而左递归调用不会被优化？

我不这么认为。只有当你直接返回其他函数的返回值时，才可能进行TCO。由于您的函数在返回结果之前处理了两个结果，因此两个调用都无法进行尾部优化。

低级解释

从基于堆栈的机器的角度来看，像这样的代码：

function fun1()
   return fun2(42)

function fun2(arg)
    return arg + 1

被翻译成这个

fun1:
    push 42
    call fun2
    result = pop
    push result
    exit

fun2:
    arg = pop
    arg = arg + 1
    push arg
    exit

TCO（尾调用优化）可以消除掉 call-pop-push 的过程，直接跳转到 fun2 方法中：

fun1:
    push 42
    goto fun2
    exit

然而，像你的代码片段一样的代码是这样的：

fun1:
    push n - 1
    call fun2
    result1 = pop

    push n - 2
    call fun2
    result2 = pop

    result3 = result1 + result2
    push result3
    exit

这里不可能用跳转替换调用，因为我们需要返回到fun1执行加法操作。

免责声明：这是一个相当理论化的解释，我不知道现代JS编译器实际上如何实现TCO。它们非常智能，所以也许有一种方法来优化这样的东西。

- georg

---

您第一段“翻译”的代码的意思是针对fun1： “为调用fun2创建一个堆栈帧，其中包含42作为参数，在调用堆栈帧中捕获结果作为帧的返回值并弹出该帧”？任何关于跳转优化为什么有效的阐述也将非常有帮助。 - Ben Aston

当你直接返回其他函数返回值时，TCO是可行的。这是不正确的。例如，return 1 + myself(); 可以被“优化”。 - user663031

@torazaburo：你能详细说明一下吗？也许可以编辑我的答案或者发表一个新的回答？ - georg