我理解尾递归,是一个特殊情况,函数对它自己进行尾调用.但我不明白尾调用和尾递归是如何不同的.在具有已实现的TCO(尾调用优化)的"正确尾递归"语言中,如Scheme,这意味着尾调用和尾递归不消耗堆栈或其他资源.在编译器无法优化尾递归的语言中,程序可能会耗尽堆栈并崩溃.在"正确的尾递归"语言中,实现尾递归以进行循环的效率并不比使用循环高,我猜想.
Rya*_*per 26
让我们首先消除"尾调用"的歧义.
甲在尾部位置的呼叫是一个函数调用,其结果被立即返回作为封闭函数的值.尾部位置是静态属性.
可以在不将任何东西推入堆栈的情况下实现尾部位置调用,因为旧的堆栈帧基本上是无用的(假设在函数式语言中通常是正确的,但不一定在C中等等).正如Guy Steele所说,尾调用是一个通过参数的跳跃.
粗略地说,语言实现是正确的尾递归,如果它具有相同的渐近空间使用,就像在没有堆栈增长的情况下将尾部位置的所有调用实现为跳跃一样.这是一个非常粗略的简化.如果你想要完整的故事,请参阅克林格的正确尾部递归和空间效率.
请注意,仅仅处理尾递归函数不足以实现正确的尾递归(必须专门处理任何尾调用).这个术语有点误导.
还要注意,还有其他方法可以实现渐近空间效率而不将尾调用实现为跳转.例如,您可以将它们实现为普通调用,然后通过删除无用的帧(以某种方式)定期压缩堆栈.在MTA上看到Baker的Cheney.
And*_*erg 13
如你所说,尾递归是尾调用的特例.因此,任何实现一般TCO的语言都是"正确的尾递归".
然而,反过来并不成立.有很多语言只能优化尾递归,因为这非常简单 - 您可以直接将其转换为循环,并且不需要以新方式操作堆栈的特定"尾调用"操作.例如,这就是编译为没有尾调用指令的JVM的语言通常只优化尾(自)递归的原因.(有一些技术可以解决缺乏这种指导的问题,例如蹦床,但它们非常昂贵.)
全尾调用优化不仅适用于自(或相互)递归调用,而且适用于尾部位置的任何调用.特别是,它扩展到目标不是静态知道的调用,例如在调用第一类函数或动态调度方法时!因此,它需要更精细(但众所周知)的实现技术.
许多函数式编程技术 - 以及一些流行的OO模式(参见例如Felleisen的ECOOP'04演示文稿或Guy Steele的博客文章) - 要求完全TCO才能实际使用.