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


当前回答

这里有一个例子,而不是用文字来解释。这是阶乘函数的Scheme版本:

(define (factorial x)
  (if (= x 0) 1
      (* x (factorial (- x 1)))))

下面是一个阶乘的尾部递归版本:

(define factorial
  (letrec ((fact (lambda (x accum)
                   (if (= x 0) accum
                       (fact (- x 1) (* accum x))))))
    (lambda (x)
      (fact x 1))))

在第一个版本中,您会注意到对事实的递归调用被馈送到乘法表达式中,因此在进行递归调用时,状态必须保存在堆栈中。在尾部递归版本中,没有其他S表达式等待递归调用的值,并且由于没有进一步的工作要做,状态不必保存在堆栈上。通常,Scheme尾部递归函数使用常数堆栈空间。

其他回答

尾部递归是你现在的生活。您不断重复使用相同的堆栈帧,因为没有理由或方法返回到“先前”帧。过去已经结束,可以抛弃。你得到一帧,永远走向未来,直到你的过程不可避免地消亡。

当您考虑到某些进程可能会使用额外的帧,但如果堆栈没有无限增长,则仍然被认为是尾部递归时,这种类比就失败了。

这意味着不需要将指令指针推到堆栈上,只需跳到递归函数的顶部并继续执行即可。这允许函数无限递归而不会溢出堆栈。

我写了一篇关于这个主题的博客文章,里面有堆栈框架的图形示例。

为了理解尾部调用递归和非尾部调用递归之间的一些核心区别,我们可以探索这些技术的.NET实现。

这是一篇包含C#、F#和C++\CLI中的一些示例的文章:C#、F#和C++/CLI中的尾部递归冒险。

C#没有针对尾部调用递归进行优化,而F#进行了优化。

原理的差异涉及循环与Lambda演算。C#的设计考虑到了循环,而F#是基于Lambda演算的原理构建的。有关Lambda微积分原理的一本非常好(免费)的书,请参阅Abelson、Sussman和Sussman的《计算机程序的结构和解释》。

关于F#中的尾部调用,有关非常好的介绍性文章,请参阅F#中尾部调用的详细介绍。最后,这里有一篇文章介绍了非尾部递归和尾部调用递归(在F#中)之间的区别:尾部递归与F sharp中的非尾部递归。

如果您想了解C#和F#之间尾部调用递归的一些设计差异,请参阅在C#和F#中生成尾部调用操作码。

如果您非常想知道哪些条件阻止C#编译器执行尾部调用优化,请参阅本文:JIT CLR尾部调用条件。

尾部递归是指递归算法中最后一条逻辑指令中的最后一个递归调用。

通常在递归中,您有一个基本情况,即停止递归调用并开始弹出调用堆栈。使用一个经典的例子,尽管比Lisp更具C语言,阶乘函数说明了尾部递归。递归调用在检查基本情况条件后发生。

factorial(x, fac=1) {
  if (x == 1)
     return fac;
   else
     return factorial(x-1, x*fac);
}

对阶乘的初始调用将是阶乘(n),其中fac=1(默认值),n是要计算阶乘的数字。

简而言之,尾部递归将递归调用作为函数中的最后一条语句,这样就不必等待递归调用。

所以这是一个尾部递归,即N(x-1,p*x)是函数中的最后一个语句,编译器聪明地发现它可以优化为for循环(阶乘)。第二个参数p携带中间乘积值。

function N(x, p) {
   return x == 1 ? p : N(x - 1, p * x);
}

这是编写上述阶乘函数的非尾部递归方式(尽管某些C++编译器可能无论如何都能优化它)。

function N(x) {
   return x == 1 ? 1 : x * N(x - 1);
}

但这不是:

function F(x) {
  if (x == 1) return 0;
  if (x == 2) return 1;
  return F(x - 1) + F(x - 2);
}

我确实写了一篇题为“理解尾部递归——Visual Studio C++——汇编视图”的长文