是否存在无法使用尾递归写入的问题?

是的,实际上你 可以 使用一些代码,将每个函数调用和每个返回都转换为尾部调用。您最终得到的是称为连续传递样式(ContinuationPassingStyle)或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 或 + 变成尾声。这也可以做到,但我假设这些leaf调用实际上是内联的。

现在是有趣的部分。 Chicken Scheme 实际上,在它编译的所有代码上进行这种转换。鸡编程序 永不回头 .有一篇经典的文章解释了为什么鸡计划会这样做,这篇文章写于1994年,在鸡被实施之前: CONS should not cons its arguments, Part II: Cheney on the M.T.A.

令人惊讶的是,延续传递样式在JavaScript中相当常见。你可以用它 to do long-running computation 避免浏览器的“慢脚本”弹出。它对异步API很有吸引力。 jQuery.get (围绕xmlhttpRequest的简单包装)显然是连续传递样式;最后一个参数是函数。

观察到任何相互递归函数的集合都可以转换为尾部递归函数,这是正确的,但并不有用。这种观察与20世纪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 通过 首先解决 一 大小子问题 n-1 . 计算阶乘函数 属于这个类别,可以迭代或 递归地。(这个概念概括了斐波那契函数,其中 你需要两者 N-1 和 n-2 解决 n 。)

• 在递归程序中,可以解决大小问题 N号 先解决 二 大小子问题 n/2 . 或者,更一般地说,你解决了一个尺寸问题 N号 首先求解大小的子问题 k 大小之一 n-k 在哪里 1 < k < n . quicksort和mergesort是这类问题的两个例子,它们是 可以很容易地进行递归编程,但不容易编程 迭代或只使用尾部递归。(您必须使用显式 堆栈)

• 在动态编程中,您可以解决大小问题 n 先解决 全部的 所有大小的子问题 K 在哪里 k<n . 找到最短的路线 指向伦敦地铁上的另一个就是这样一个例子 问题。(伦敦地铁是一个多重连接图,而你 通过首先找到最短路径的所有点来解决问题 是1站,那么最短路径是2站,等等。)

只有第一种程序有 简单的 转换为尾部递归形式。

任何递归算法都可以重写为迭代算法(可能需要一个堆栈或列表),并且迭代算法总是可以重写为尾部递归算法,所以我认为任何递归解决方案都可以以某种方式转换为尾部递归解决方案是正确的。

(在评论中,PascalCuoq指出任何算法都可以转换为 continuation-passing style 。)

注意,仅仅因为尾部递归并不意味着它的内存使用是常量。这只意味着调用返回堆栈不会增长。

在O(1)空间(空间层次定理)中不能做任何事情。如果坚持使用尾部递归,那么可以将调用堆栈存储为参数之一。显然,这不会改变任何东西;在内部的某个地方,存在一个调用堆栈,您只需使其显式可见即可。

如果是这样,有一天功能编译器和解释程序是否足够智能,能够自动执行转换?

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

正如PascalCuoq所评论的,另一种方法是使用 CPS ;那么所有调用都是尾部递归的。

我不认为 tak 只能使用尾调用实现。(不允许继续)