是否所有的递归函数都可以重写为尾递归？ [英] Can all recursive functions be re-written as tail-recursions?
问题描述
根据我的理解，尾递归是一种优化，当递归调用不需要递归调用中的垃圾信息时，可以使用它。
From my understanding, tail recursion is an optimization you can use when a recursive call does not need information from the recursive calls that it will spam.
那么是否有可能使用尾递归来实现所有递归函数？像DFS这样的东西呢，您需要最里面的孩子在父母可以返回之前返回？
Is it possible then to implement all recursive functions using tail-recursion? What about something like DFS, where you need the innermost child to return before the parent can?
推荐答案
这取决于您的实际情况
如果要保留所有具有相同签名的函数（无可变状态），则不能。最明显的例子是快速排序，其中两个调用都不能是尾部调用。
If you want to keep all functions as functions (no mutable state) with the same signatures, then no. The most obvious example is the quicksort, where both calls can't be tail calls.
如果您可以通过各种方式修改函数，则可以。有时本地修改就足够了-通常您可以添加一个累加器来构建返回的表达式，不过，如果结果涉及非交换运算，则您需要小心（例如，在天真地构造链表时，
If you can modify the function in various ways, then yes. Sometimes a local modification is sufficient - often you can add an "accumulator" that builds some expression that is returned, although, if the result involves non-commutative operations, then you need to be careful (for example, when naively constructing linked lists, the order is reversed) or you can add a stack.
或者，您可以对整个程序进行全局修改，其中每个函数都作为一个附加参数，包含未来动作的功能。这是 Pete 在谈论的延续。
Alternatively, you can do a global modification of the entire program, in which each function takes as an extra argument the function that contains future actions. This is the continuation passing that Pete is talking about.
如果您是手工工作，那么本地修改通常很容易。但是如果您要进行自动重写（例如在编译器中），则采用全局方法会更简单（它需要更少的智能）。
if you are working by hand then the local modification is often fairly easy. but if you're doing automated rewriting (in a compiler for example) then it's simpler to take the global approach (it requires less "smarts").
这篇关于是否所有的递归函数都可以重写为尾递归？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
