lisp - 尾调用和尾递归有什么区别？

Question

我知道尾递归是函数对自身进行尾调用的特殊情况。但我不明白尾调用和尾递归有何不同。在具有实现 TCO（尾调用优化）的“适当尾递归”语言中，如 Scheme，这意味着尾调用和尾递归不消耗堆栈或其他资源。在编译器无法优化尾递归的语言中，程序可能会耗尽堆栈并崩溃。我认为，在“适当的尾递归”语言中，为循环实现尾递归的效率不亚于使用循环。

Answer 1

让我们首先消除“尾调用”的歧义。

尾部位置的调用是一个函数调用，其结果立即作为封闭函数的值返回。尾部位置是一个静态属性。

可以在不将任何东西压入堆栈的情况下实现尾部位置的调用，因为旧的堆栈帧本质上是无用的（假设在函数式语言中通常是正确的，但在 C 语言中不一定是这样的）。正如盖伊斯蒂尔所说，尾声是传递参数的跳跃。

粗略地说，如果一种语言实现具有相同的渐近空间使用率，则它与将所有在尾位置的调用实现为没有堆栈增长的跳转的语言实现是正确的尾递归。这是一个非常粗略的简化。如果您想要完整的故事，请参阅 Clinger 的Proper Tail Recursion and Space Efficiency。

请注意，仅专门处理尾递归函数不足以实现正确的尾递归（必须专门处理任何尾调用）。该术语有些误导。

另请注意，还有其他方法可以在不将尾调用作为跳转实现的情况下实现渐近空间效率。例如，您可以将它们实现为正常调用，然后通过删除无用的帧（以某种方式）定期压缩堆栈。请参阅 MTA 上的 Baker 的Cheney。

Answer 2

正如您所说，尾递归是尾调用的一种特殊情况。因此，任何简单地实现通用 TCO 的语言都是“适当的尾递归”。

然而，逆不成立。有相当多的语言只优化尾递归，因为这要容易得多——您可以直接将其转换为循环，并且不需要以新方式操纵堆栈的特定“尾调用”操作。例如，这就是编译到没有尾调用指令的 JVM 的语言通常只优化尾（自）递归的原因。（有一些技术可以解决缺少此类指令的问题，例如蹦床，但它们非常昂贵。）

全尾调用优化不仅适用于自身（或相互）递归调用，还适用于尾部位置的任何调用。特别是，它扩展到目标不是静态已知的调用，例如在调用一等函数或动态分派方法时！因此，它需要更精细（尽管众所周知）的实现技术。

许多函数式编程技术——还有一些流行的 OO 模式（参见例如Felleisen 的 ECOOP'04 演示文稿或Guy Steele 的博客文章）——需要完整的 TCO 才能真正可用。

Answer 3

Well, the two are somehow related −as they both have the word 'tail' in them− but are completely differents…</p>

Tail recursion is a recursion with some specific constraints, and tails calls are function calls. Your question is a bit like "what is the difference between an animal and a cat?"…</p>

A tail call is a function call in tail position. Examples: f(x) in f(x), and g(★) in g(f(x)) Counter-examples: f(x) in 1+f(x) and in g(f(x))

Tail recursion is a recursion where recursive calls are tail calls. Examples: f(★) on the right of the "=" sign in f(x) = f(x), f(x,y) = if x == 0 then y else f(x-1,y+x) I have defined two recursive functions that call themselves with tail calls. That's it.

In languages with TCO, tail calls cost nothing, so (tail) recursion works in constant stack, and everyone is happy.