所有递归函数都可以重写为尾递归吗？

Question

可能重复： 是否存在不能用尾递归编写的问题？

据我所知，当递归调用不需要来自递归调用的信息时，可以使用尾递归。

那么，是否有可能使用尾递归来实现所有递归函数呢？像DFS这样的东西怎么样?在DFS中，您需要最内部的孩子在父级返回之前返回？

Answer 1

这完全取决于你要求的是什么。

如果希望将所有函数保留为具有相同签名的函数(没有可变状态)，则不需要。最明显的例子是快速排序，这两个调用都不能是尾调用。

如果您可以以各种方式修改函数，那么是的。有时，本地修改就足够了--通常您可以添加一个“累加器”来构建一些返回的表达式，尽管如果结果涉及非交换操作，那么您需要小心(例如，当天真地构造链接列表时，顺序被颠倒)，或者您可以添加一个堆栈。

或者，您可以对整个程序进行全局修改，其中每个函数都将包含未来操作的函数作为额外的参数。这是传递该是在谈论的延续。

如果您是手工工作，那么本地修改通常是相当容易的。但是，如果您正在进行自动化重写(例如在编译器中)，那么采用全局方法就更简单了(它需要更少的“智能”)。

Answer 2

是也不是。

是的，与其他控制流机制(例如连续传递)一起使用，您可以将任意控制流表示为尾递归。

不，除非您用其他控制流机制来补充尾递归，否则不可能将所有递归表示为尾递归。

Answer 3

可以使用连续传递将所有程序重写为尾调用。只需向尾部调用添加一个参数，表示当前执行的延续。

任何转向完整的语言都会执行与连续传递相同的转换--为程序和输入参数创建一个G del号，而非尾调用返回这些参数，并将其作为参数传递给尾调用--尽管很明显，使用连续、共例程或其他一流构造为您完成此操作的环境会使转换变得容易得多。

CPS被用作编译器优化，我以前编写过使用连续传递的解释器。方案编程语言的设计使其能够以这样的方式实现，并满足尾部调用优化和一流延续标准中的要求。