20

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

据我了解，尾递归是一种优化，当递归调用不需要来自递归调用的信息时，您可以使用它会发送垃圾邮件。

那么是否可以使用尾递归来实现所有递归函数？像 DFS 这样的东西，你需要最里面的孩子在父母之前返回？

4

7 回答 7

14

这完全取决于您要问什么。

如果您想将所有函数保留为具有相同签名的函数（无可变状态），那么不。最明显的例子是快速排序，其中两个调用都不能是尾调用。

如果您可以通过各种方式修改功能，那么可以。有时本地修改就足够了——通常你可以添加一个“累加器”来构建一些返回的表达式，但是，如果结果涉及非交换操作，那么你需要小心（例如，当天真地构造链表时，顺序相反）或者您可以添加一个堆栈。

或者，您可以对整个程序进行全局修改，其中每个函数将包含未来操作的函数作为额外参数。这就是皮特所说的续传。

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

于 2012-08-01T22:07:22.713 回答
5

是和不是。

是的，与其他控制流机制（例如，继续传递）结合使用，您可以将任意控制流表示为尾递归。

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

于 2012-07-30T03:58:54.443 回答
3

是的你可以。转换通常涉及显式维护必要的信息，否则这些信息将为我们在运行时隐式地分布在执行堆栈的调用帧中进行维护。

就如此容易。无论运行时系统在执行期间隐式地做什么，我们都可以自己显式地做。这里没有什么大秘密。个人电脑由硅、铜和钢制成。

将 DFS 实现为具有要处理的状态/位置/节点的显式队列的循环是微不足道的。它实际上是这样定义的——DFS 用来自它的所有弧替换队列中弹出的第一个条目；BFS 将这些弧添加到队列的末尾。

继续传递样式转换在完成后将程序中的所有函数调用作为尾调用。这是一个简单的生活事实。使用的延续会增长和缩小，但调用都将是尾调用。

我们可以进一步具体化进程在延续中传播的状态，作为在堆上显式维护的数据。最终实现的是解释和具体化，将堆栈上的隐式内容移动到堆中的显式内容，简化和揭开控制流的神秘面纱。

于 2012-08-05T23:07:26.693 回答
3

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

任何 Turning 完整语言都执行与延续传递提供的相同的转换——为程序创建一个哥德尔数并输入非尾调用返回的参数，并将其作为参数传递给尾调用——尽管显然这是在环境中使用延续、协同程序或其他一流的结构为您完成工作会更容易。

CPS 用作编译器优化，我之前使用延续传递编写了解释器。方案编程语言被设计成允许它以这样的方式实现，符合尾调用优化和第一类延续标准中的要求。

于 2012-08-01T12:42:48.763 回答
2

递归算法是一种按照分治策略实现的算法，其中解决每个中间子问题会产生 0、1 或更多新的较小子问题。如果这些子问题以 LIFO 顺序解决，您将获得经典的递归算法。

现在，如果已知您的算法在每一步仅产生 0 或 1 个子问题，那么该算法可以通过尾递归轻松实现。事实上，这种算法可以很容易地重写为迭代算法，并通过一个简单的循环来实现。（不用说，尾递归只是实现迭代的另一种不太明确的方式。）

这种递归算法的教科书示例将是阶乘计算的递归方法：要计算n!，您需要先计算(n-1)!，即在每个递归步骤中，您只会发现一个较小的子问题。这一特性使得将阶乘计算算法转换为真正的迭代算法（或尾递归算法）变得如此容易。

但是，如果您知道在一般情况下，算法的每一步生成的子问题的数量大于 1，那么您的算法基本上是递归的。它不能重写为迭代算法，不能通过尾递归来实现。任何以迭代或尾递归方式实现此类算法的尝试都需要额外的非常量大小的 LIFO 存储来存储“未决”子问题。这种实现尝试只会通过手动实现递归来混淆算法不可避免的递归性质。

例如，像遍历具有父->子链接（并且没有子->父链接）的二叉树这样的简单问题是一个实质上递归的问题。它不能用尾递归算法完成，也不能用迭代算法完成。

于 2012-08-01T22:22:15.183 回答
2

我不知道是否所有递归函数都可以重写为尾递归，但其中许多都可以。这样做的一种标准方法是使用累加器。例如，阶乘函数可以这样写（在 Common Lisp 中）：

(defun factorial (n)
   (if (<= n 1)
       1
       (* n (factorial (1- n)))))

这是递归的，但不是尾递归的。它可以通过添加一个累加器参数来实现尾递归：

(defun factorial-accum (accum n)
   (if (<= n 1)
       accum
       (factorial-accum (* n accum) (1- n))))

可以通过将累加器设置为 1 来计算阶乘。例如，3 的阶乘为：

(factorial-accum 1 3)

不过，我不清楚是否可以使用这样的方法将所有递归函数重写为尾递归函数。但肯定很多功能都可以。

于 2012-08-01T21:47:20.060 回答
-1

不，它只能“自然”地完成一次递归调用。对于两个或多个递归调用，您当然可以自己模拟堆栈帧。但在优化内存的意义上，它会非常难看，并且实际上不会是尾递归的。

尾递归的要点是您不想回到父堆栈。因此，只需将该信息传递给可以完全替换父堆栈的子堆栈，而不是堆栈增长。

于 2012-07-30T10:31:00.640 回答