当我开始学习口齿不清时,我遇到了“尾部递归”这个词。这到底是什么意思?


当前回答

对我来说,理解尾调用递归的最好方法是递归的一种特殊情况,其中最后一个调用(或尾调用)是函数本身。

比较Python中提供的示例:

def recsum(x):
 if x == 1:
  return x
 else:
  return x + recsum(x - 1)

^递归

def tailrecsum(x, running_total=0):
  if x == 0:
    return running_total
  else:
    return tailrecsum(x - 1, running_total + x)

^尾部递归

正如您在常规递归版本中看到的,代码块中的最后一个调用是x+recsum(x-1)。所以在调用recsum方法之后,还有一个操作是x+。。。

然而,在尾部递归版本中,代码块中的最后一个调用(或尾部调用)是tailrecsum(x-1,running_total+x),这意味着最后一次调用是对方法本身进行的,之后不再进行操作。

这一点很重要,因为这里看到的尾部递归不会使内存增长,因为当底层VM看到一个函数在尾部位置(函数中要计算的最后一个表达式)调用自己时,它会消除当前堆栈帧,这就是所谓的尾部调用优化(TCO)。

EDIT

没有。请记住,上面的示例是用Python编写的,其运行时不支持TCO。这只是一个解释这一点的例子。在Scheme、Haskell等语言中支持TCO

其他回答

这个问题有很多很好的答案。。。但我忍不住提出了另一种看法,即如何定义“尾部递归”,或者至少是“正确的尾部递归”。即:是否应该将其视为程序中特定表达式的属性?还是应该将其视为编程语言实现的属性?

关于后一种观点,Will Clinger的一篇经典论文“正确的尾部递归和空间效率”(PLDI 1998)将“正确的尾递归”定义为编程语言实现的属性。该定义被构造为允许忽略实现细节(例如调用堆栈实际上是通过运行时堆栈还是通过堆分配的帧链接列表表示的)。

为了实现这一点,它使用了渐近分析:不是人们通常看到的程序执行时间,而是程序空间使用情况。这样,堆分配的链接列表与运行时调用堆栈的空间使用最终是渐近等价的;因此,人们会忽略编程语言实现的细节(这一细节在实践中当然非常重要,但当试图确定给定的实现是否满足“属性尾部递归”的要求时,可能会让事情变得一团糟)

该论文值得仔细研究,原因如下:

它给出了程序尾部表达式和尾部调用的归纳定义。(这样的定义,以及为什么这样的电话很重要,似乎是这里给出的大多数其他答案的主题。)以下是这些定义,只是为了提供文本的味道:定义1以核心方案编写的程序的尾部表达式归纳如下。lambda表达式的主体是尾部表达式如果(如果E0 E1 E2)是尾部表达式,则E1和E2都是尾部表达式。其他的都不是尾部表达式。定义2尾部调用是作为过程调用的尾部表达式。

(尾部递归调用,或者正如论文所说,“self-tail调用”是尾部调用的一种特殊情况,其中过程本身被调用。)

它为评估核心方案的六个不同“机器”提供了正式定义,其中每个机器都具有相同的可观察行为,除了每个机器所处的渐近空间复杂性类。例如,在为分别为1。基于堆栈的内存管理,2。垃圾收集,但没有尾部调用。垃圾收集和尾部调用,本文继续介绍更高级的存储管理策略,如4。“evlis尾部递归”,在尾部调用的最后一个子表达式参数求值期间不需要保存环境,5。将闭包的环境减少到该闭包的自由变量,以及6。Appel和Shao定义的所谓“空间安全”语义。为了证明这些机器实际上属于六个不同的空间复杂性类,本文针对每对被比较的机器,提供了程序的具体示例,这些程序将揭示一台机器上的渐近空间爆炸,而不是另一台机器。


(现在仔细阅读我的答案,我不确定我是否真的抓住了克林格论文的关键点。但是,唉,我现在不能花更多的时间来研究这个答案。)

我不是Lisp程序员,但我认为这会有所帮助。

基本上,这是一种编程风格,递归调用是最后一件事。

在Java中,以下是斐波那契函数的一个可能的尾部递归实现:

public int tailRecursive(final int n) {
    if (n <= 2)
        return 1;
    return tailRecursiveAux(n, 1, 1);
}

private int tailRecursiveAux(int n, int iter, int acc) {
    if (iter == n)
        return acc;
    return tailRecursiveAux(n, ++iter, acc + iter);
}

与标准递归实现形成对比:

public int recursive(final int n) {
    if (n <= 2)
        return 1;
    return recursive(n - 1) + recursive(n - 2);
}

重要的一点是尾部递归本质上等同于循环。这不仅仅是一个编译器优化的问题,而是一个关于表现力的基本事实。这是双向的:你可以采取任何形式的循环

while(E) { S }; return Q

其中E和Q是表达式,S是语句序列,并将其转换为尾部递归函数

f() = if E then { S; return f() } else { return Q }

当然,必须定义E、S和Q来计算一些变量的有趣值。例如,循环函数

sum(n) {
  int i = 1, k = 0;
  while( i <= n ) {
    k += i;
    ++i;
  }
  return k;
}

等效于尾部递归函数

sum_aux(n,i,k) {
  if( i <= n ) {
    return sum_aux(n,i+1,k+i);
  } else {
    return k;
  }
}

sum(n) {
  return sum_aux(n,1,0);
}

(用参数较少的函数“包装”尾部递归函数是一种常见的函数习惯用法。)

在传统递归中,典型的模型是首先执行递归调用,然后获取递归调用的返回值并计算结果。通过这种方式,在每次递归调用返回之前,您不会得到计算结果。

在尾部递归中,首先执行计算,然后执行递归调用,将当前步骤的结果传递给下一个递归步骤。这导致最后一条语句的形式为(return(递归函数参数))。基本上,任何给定递归步骤的返回值都与下一个递归调用的返回值相同。

这样做的结果是,一旦准备好执行下一个递归步骤,就不再需要当前堆栈帧。这允许进行一些优化。事实上,使用一个适当编写的编译器,您永远不应该有带有尾部递归调用的堆栈溢出窃笑。只需在下一个递归步骤中重用当前堆栈帧。我很确定Lisp会这么做。