54

尾递归是函数式语言中重要的性能优化策略，因为它允许递归调用消耗常量堆栈（而不是 O(n)）。

是否有任何问题根本无法以尾递归风格编写，或者是否总是可以将天真递归函数转换为尾递归函数？

如果是这样，有朝一日，函数式编译器和解释器可能会变得足够智能以自动执行转换吗？

4

5 回答 5

51

是的，实际上您可以获取一些代码并将每个函数调用（以及每个返回）转换为尾调用。你最终得到的东西被称为延续传递风格，或 CPS。

例如，这是一个包含两个递归调用的函数：

(define (count-tree t)
  (if (pair? t)
    (+ (count-tree (car t)) (count-tree (cdr t)))
    1))

如果将此函数转换为连续传递样式，它的外观如下：

(define (count-tree-cps t ctn)
  (if (pair? t)
    (count-tree-cps (car t)
                    (lambda (L) (count-tree-cps (cdr t)
                                                (lambda (R) (ctn (+ L R))))))
    (ctn 1)))

额外的参数 ,ctn是一个count-tree-cps尾调用而不是返回的过程。（sdcvvc 的回答说你不能在 O(1) 空间中做所有事情，这是正确的；这里每个延续都是一个占用一些内存的闭包。）

我没有将呼叫转换为car或cdr或+转换为尾呼叫。也可以这样做，但我认为这些叶子调用实际上是内联的。

现在是有趣的部分。Chicken Scheme实际上对它编译的所有代码都进行了这种转换。Chicken 编译的程序永远不会返回。有一篇经典论文解释了为什么 Chicken Scheme 会这样做，写于 1994 年 Chicken 实施之前：CONS 不应该反对它的论点，第二部分：Cheney on the MTA

令人惊讶的是，持续传递风格在 JavaScript 中相当普遍。你可以用它来做长时间运行的计算，避免浏览器的“慢脚本”弹出。它对异步 API 很有吸引力。jQuery.get（XMLHttpRequest 的一个简单包装器）显然是延续传递风格；最后一个参数是一个函数。

于 2009-12-11T16:07:11.100 回答
27

观察到任何相互递归函数的集合都可以转换为尾递归函数是正确的但没有用。这种观察与 1960 年代的老栗子相提并论，即可以消除控制流结构，因为每个程序都可以写成一个循环，其中嵌套了一个 case 语句。

需要知道的是，许多不明显尾递归的函数可以通过添加累加参数转换为尾递归形式。（这种转换的一个极端版本是转换为连续传递样式 (CPS)，但大多数程序员发现 CPS 转换的输出难以阅读。）

这是一个“递归”（实际上它只是迭代）但不是尾递归的函数的示例：

factorial n = if n == 0 then 1 else n * factorial (n-1)

在这种情况下，乘法发生在递归调用之后。我们可以通过将乘积放入一个累加参数中来创建一个尾递归的版本：

factorial n = f n 1
   where f n product = if n == 0 then product else f (n-1) (n * product)

内部函数f是尾递归的，并编译成一个紧密的循环。

我发现以下区别很有用：

  • 在迭代或递归程序中，您n通过首先解决size 的一个子问题来解决 size 问题n-1。计算阶乘函数属于这一类，它可以迭代或递归完成。（这个想法可以推广到，例如，斐波那契函数，你需要n-1和n-2求解n。）

  • 在递归程序中，您n通过首先解决两个 大小子问题来解决大小问题n/2。或者，更一般地，您n 通过首先解决 size 的子问题和 size 的一个子问题来解决k大小问题n-k，其中1 < k < n。快速排序和归并排序是这类问题的两个例子，它们可以很容易地递归编程，但不那么容易迭代编程或仅使用尾递归。（您基本上必须使用显式堆栈来模拟递归。）

  • 在动态规划中，您n通过首先解决所有大小 的所有 子问题来解决大小问题k，其中k<n. 在伦敦地铁上寻找从一个点到另一个点的最短路线就是这类问题的一个例子。（伦敦地铁是一个多重连通图，您可以通过首先找到最短路径为 1 站，然后最短路径为 2 站等的所有点来解决问题。）

只有第一种程序可以简单地转换为尾递归形式。

于 2009-12-12T01:07:14.887 回答
11

任何递归算法都可以重写为迭代算法（可能需要堆栈或列表）并且迭代算法总是可以重写为尾递归算法，所以我认为任何递归解决方案都可以以某种方式转换为尾递归解决方案是真的.

（在评论中，Pascal Cuoq 指出任何算法都可以转换为continuation-passing style。）

请注意，仅仅因为某些东西是尾递归的，并不意味着它的内存使用量是恒定的。这只是意味着调用返回堆栈不会增长。

于 2009-12-11T15:18:05.543 回答
10

你不能在 O(1) 空间中做所有事情（空间层次定理）。如果您坚持使用尾递归，那么您可以将调用堆栈存储为参数之一。显然这并没有改变任何东西。在内部某处，有一个调用堆栈，您只是使其显式可见。

如果是这样，有朝一日，函数式编译器和解释器可能会变得足够智能以自动执行转换吗？

这种转换不会降低空间复杂度。

正如 Pascal Cuoq 评论的那样，另一种方法是使用CPS；那么所有的调用都是尾递归的。

于 2009-12-11T15:24:58.637 回答
1

我不认为只使用尾调用就可以实现像tak这样的东西。（不允许继续）

于 2009-12-11T15:41:28.203 回答