我知道尾递归是一种特殊情况,其中函数对自身进行尾调用。 但我不明白尾部调用和尾部递归有何不同。 在实现了TCO(尾调用优化)的“适当尾递归”语言中,如Scheme,这意味着尾调用和尾递归不消耗堆栈或其他资源。 在编译器无法优化尾递归的语言中,程序可能会溢出堆栈并崩溃。 我认为,在“正确的尾递归”语言中,实现循环尾递归的效率并不比使用循环低。
让我们首先消除“尾调用”的歧义。
尾部位置的调用是一个函数调用,其结果立即作为封闭函数的值返回。尾部位置是静态属性。
可以在不将任何内容压入堆栈的情况下实现尾部位置的调用,因为旧的堆栈框架本质上是无用的(假设在函数语言中通常是正确的,但不一定在 C 等中)。正如 Guy Steele 所说,尾部调用是传递参数的跳转。粗略地说,如果一种语言实现与将尾部位置中的所有调用实现为没有堆栈增长的跳转的语言实现相同的渐近空间使用,则该语言实现是“正确的尾递归”。这是一个非常粗略的简化。如果您想了解完整的故事,请参阅 Clinger 的
正确的尾递归和空间效率。 请注意,仅专门处理 tail-recursive
函数不足以实现正确的尾递归(any 尾调用必须经过特殊处理)。该术语有些误导。 另请注意,还有其他方法可以实现渐进空间效率,而无需将尾部调用实现为跳转。例如,您可以将它们实现为普通调用,然后通过删除无用的帧(以某种方式)定期压缩堆栈。请参阅贝克的切尼谈 MTA
。正如你所说,尾递归是尾调用的一种特殊情况。因此,任何简单地实现一般 TCO 的语言都是“适当的尾递归”。完整的尾部调用优化不仅适用于自(或相互)递归调用,还适用于尾部位置的
任何
调用。特别是,它扩展到目标“不是静态已知”的调用,例如当调用一流函数或动态分派方法时!因此,它需要更复杂(尽管众所周知)的实现技术。许多函数式编程技术 - 还有一些流行的 OO 模式(例如,参见 Felleisen 的 ECOOP'04 演示文稿 或 Guy Steele 的博客文章
) - 需要完整的 TCO 才能真正可用。尾递归是带有一些特定约束的递归,尾调用是函数调用。你的问题有点像“动物和猫有什么区别?”……f(x)
f(x)
g(★)
中的
g(f(x))
反例:
f(x)
中的
1+f(x)
和
g(f(x))
中
尾递归是一种递归,其中递归调用是尾调用。 示例:
f(★)
位于“=”符号右侧
f(x) = f(x)
、f(x,y) = if x == 0 then y else f(x-1,y+x)
我定义了两个递归函数,它们通过尾调用来调用自身。就是这样。
在具有 TCO 的语言中,尾调用不需要任何成本,因此(尾)递归在常量堆栈中工作,每个人都很高兴。