有哪些问题不能使用尾递归写出来？

Question

有哪些问题不能使用尾递归写出来？

functional-programmingrecursiontail-recursion

55

尾递归是函数式语言中一种重要的性能优化策略，因为它允许递归调用使用恒定的栈空间（而不是O(n)）。

是否存在某些问题无法以尾递归方式编写，或者总是可以将一个朴素递归函数转换成尾递归函数？

如果可以的话，未来的函数式编译器和解释器是否足够智能，可以自动执行此转换？

- ctford

12

我不同意尾递归是性能优化的说法。它与正确性有关：在一种没有此功能的语言中编程，会阻止您使用递归处理无限重复，而在具备此功能的语言中，您可以自由地使用递归（在某些约束条件下）来处理无限重复。这是一个重要的观点：尾递归（有保证的）存在会改变语言的语义。 - harms

3

它如何改变语义？两种情况下都描述了相同的抽象计算。生成的代码的时间和空间复杂度可以说是实现细节，但是如果您希望实际运行程序，则是一个重要的细节。 - C. A. McCann

2

我或许应该澄清一下，如果你有一个静态堆栈，它会改变语义，这是我理解的正常情况，例如在Java中，你可以在启动时传递一个参数给jvm，以确定堆栈的大小，但堆栈不能无限增长直到机器的内存用完。你谈到了抽象计算，从某种意义上说你是正确的，但这是一个“泄漏的抽象”的典型例子：底层实现会施加影响，没有尾调用的保证，程序员不能依赖它们。 - harms

5个回答

27

观察到任何相互递归的函数集都可以转化为尾递归函数是正确的，但并不实用。这个观察结果与上世纪60年代提出的控制流构造可以被消除，因为每个程序都可以被写成一个嵌套了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-1的一个子问题来解决大小为n的问题。计算阶乘函数就属于这一类别，它可以通过迭代或递归来完成。（这个想法可以推广到斐波那契函数，其中需要使用n-1和n-2来求解n。）
在递归程序中，您通过首先解决大小为k和n-k的两个子问题来解决大小为n的问题，其中1 < k < n。快速排序和归并排序是这种问题的两个例子，可以轻松地使用递归进行编程，但使用仅使用尾递归或迭代不太容易。（您基本上必须使用显式堆栈模拟递归。）
在动态规划中，您通过首先解决所有大小为k的子问题来解决大小为n的问题，其中k<n。找到从一个点到另一个点的最短路径是这种类型问题的一个例子。（伦敦地铁是一个多重连接图，您通过首先找到最短路程为1个站点的所有点，然后是最短路程为2个站点的所有点等等来解决问题。）

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

- Norman Ramsey

一些运行时环境的堆栈空间非常有限，而堆内存则无限制。因此，了解如何将任何代码转换为尾递归代码确实非常有用。 - Will Ness

请问您能否看一下我的问题? - refik

11

任何递归算法都可以被重写成迭代算法（可能需要一个栈或列表），而迭代算法总是可以被重写为尾递归算法，所以我认为任何递归解决方案都可以以某种方式转换为尾递归解决方案。

（在评论中，Pascal Cuoq指出任何算法都可以转换为传递风格。）

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

- Kristopher Johnson

2

-1：并非所有递归方法都可以转换为尾递归。请参考我的答案中的示例。 - Ben S

3

您可以使用栈来编写迭代的树遍历算法。 - Kristopher Johnson

我是指消耗常量栈。感谢指出我的错误。 - ctford

2

@Ben S：在 CPS 中，每个调用都是尾调用。请在上下文中查看：http://en.wikipedia.org/wiki/Continuation-passing_style - Pascal Cuoq

一个递归算法只有在递归调用后，栈值不再被写入或读取时才能使用尾调用，这意味着如果先前的值可以被丢弃，则可以使用。如果不能，则无法使用尾调用。 - Pop Catalin

2

@Ben S：抱歉，但您的答案是错误的。使用 continuation passing 编写尾递归树遍历和插入很容易。请参见以下网址：https://dev59.com/z3RA5IYBdhLWcg3wxA5N#1532265 和 http://fortysix-and-two.blogspot.com/2009/06/fun-with-data-structures-continuations.html - Juliet

10

在O(1)的空间复杂度下无法完成所有操作（空间层级定理）。如果您坚持使用尾递归，则可以将调用堆栈存储为其中一个参数。显然，这并没有改变任何事情；在内部的某个地方，有一个调用堆栈，您只是将其明确可见。

如果是这样，未来的函数编译器和解释器是否足够智能，可以自动执行转换？

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

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

- sdcvvc

1

我认为像 tak 这样的东西，仅使用尾调用（不允许使用continuations）是无法实现的。

- recursive

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jason Orendorff · Accepted Answer

实际上，您可以将一些代码转换为尾调用，并将每个函数调用和每个返回都转换为尾调用。这样得到的结果称为传递风格，或CPS。

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

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

如果将这个函数转换为 continuation-passing 风格，它会是这样的：

(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 should not cons its arguments, Part II: Cheney on the M.T.A. 令人惊讶的是，在JavaScript中，传递延续风格相当普遍。您可以使用它进行长时间运算，避免浏览器的“缓慢脚本”弹出窗口。它对于异步API也很有吸引力。jQuery.get（一个简单的XMLHttpRequest包装器）显然是采用传递延续风格；最后一个参数是一个函数。