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


当前回答

与普通递归相比,尾部递归非常快。它很快,因为祖先调用的输出不会写入堆栈以保持跟踪。但在正常递归中,所有祖先调用堆栈中的输出以保持跟踪。

其他回答

下面是比较两个函数的快速代码片段。第一种是传统的递归,用于求给定数的阶乘。第二种使用尾部递归。

理解起来非常简单直观。

判断递归函数是否为尾部递归函数的一种简单方法是,它是否在基本情况下返回具体值。这意味着它不会返回1或true或类似的值。它很可能会返回某个方法参数的变体。

另一种方法是判断递归调用是否没有任何加法、算术、修改等。这意味着它只是一个纯递归调用。

public static int factorial(int mynumber) {
    if (mynumber == 1) {
        return 1;
    } else {            
        return mynumber * factorial(--mynumber);
    }
}

public static int tail_factorial(int mynumber, int sofar) {
    if (mynumber == 1) {
        return sofar;
    } else {
        return tail_factorial(--mynumber, sofar * mynumber);
    }
}

递归有两种基本类型:头部递归和尾部递归。

在头部递归中,函数进行递归调用,然后执行更多计算,可能使用例如递归调用。在尾部递归函数中,所有计算首先发生递归调用是最后发生的事情。

摘自这篇超棒的帖子。请考虑阅读它。

为了理解尾部调用递归和非尾部调用递归之间的一些核心区别,我们可以探索这些技术的.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尾部调用条件。

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

比较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

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

所以这是一个尾部递归,即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++——汇编视图”的长文