当我开始学习口齿不清时,我遇到了“尾部递归”这个词。这到底是什么意思?
当前回答
与普通递归相比,尾部递归非常快。它很快,因为祖先调用的输出不会写入堆栈以保持跟踪。但在正常递归中,所有祖先调用堆栈中的输出以保持跟踪。
其他回答
下面是比较两个函数的快速代码片段。第一种是传统的递归,用于求给定数的阶乘。第二种使用尾部递归。
理解起来非常简单直观。
判断递归函数是否为尾部递归函数的一种简单方法是,它是否在基本情况下返回具体值。这意味着它不会返回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++——汇编视图”的长文