是否可以将所有递归函数重写为尾递归？

Question

可能重复:
是否存在无法使用尾递归写入的问题？

根据我的理解,尾递归是一种优化,当递归调用不需要来自它将发送垃圾邮件的递归调用的信息时,您可以使用它.

那么可以使用尾递归实现所有递归函数吗？像DFS这样的东西,你需要最内层的孩子在父母可以之前返回？

Answer 1

这取决于你究竟在问什么.

如果要将所有函数保留为具有相同签名的函数(无可变状态),则不.最明显的例子是quicksort,其中两个调用都不能是尾调用.

如果你能以各种方式修改功能,那么是的.有时局部修改就足够了 - 通常你可以添加一个"累加器"来构建一些返回的表达式,但是,如果结果涉及非交换操作,那么你需要小心(例如,当天真地构建链表时,订单相反)或者您可以添加堆栈.

或者,您可以对整个程序进行全局修改,其中每个函数都将包含未来操作的函数作为额外参数.这是Pete所说的延续传递.

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

Answer 2

是的,不是.

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

不,除非你用其他控制流机制补充尾递归,否则不可能将所有递归表示为尾递归.