当我开始学习口齿不清时,我遇到了“尾部递归”这个词。这到底是什么意思?
当前回答
使用常规递归,每个递归调用将另一个条目推送到调用堆栈中。递归完成后,应用程序必须将每个条目向下弹出。
使用尾部递归,根据语言的不同,编译器可以将堆栈折叠为一个条目,这样可以节省堆栈空间。。。大型递归查询实际上会导致堆栈溢出。
基本上,尾部递归可以优化到迭代中。
其他回答
递归有两种基本类型:头部递归和尾部递归。
在头部递归中,函数进行递归调用,然后执行更多计算,可能使用例如递归调用。在尾部递归函数中,所有计算首先发生递归调用是最后发生的事情。
摘自这篇超棒的帖子。请考虑阅读它。
这里是前面提到的tailrecsum函数的Perl 5版本。
sub tail_rec_sum($;$){
my( $x,$running_total ) = (@_,0);
return $running_total unless $x;
@_ = ($x-1,$running_total+$x);
goto &tail_rec_sum; # throw away current stack frame
}
下面是比较两个函数的快速代码片段。第一种是传统的递归,用于求给定数的阶乘。第二种使用尾部递归。
理解起来非常简单直观。
判断递归函数是否为尾部递归函数的一种简单方法是,它是否在基本情况下返回具体值。这意味着它不会返回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);
}
}
与普通递归相比,尾部递归非常快。它很快,因为祖先调用的输出不会写入堆栈以保持跟踪。但在正常递归中,所有祖先调用堆栈中的输出以保持跟踪。
尾部递归是函数调用的递归函数自身位于函数的末尾(“尾部”),其中没有计算在递归调用返回后完成。许多编译器优化以将递归调用更改为尾部递归调用或迭代调用。
考虑计算一个数的阶乘的问题。
一种简单的方法是:
factorial(n):
if n==0 then 1
else n*factorial(n-1)
假设你调用阶乘(4)。递归树为:
factorial(4)
/ \
4 factorial(3)
/ \
3 factorial(2)
/ \
2 factorial(1)
/ \
1 factorial(0)
\
1
上述情况下的最大递归深度为O(n)。
但是,请考虑以下示例:
factAux(m,n):
if n==0 then m;
else factAux(m*n,n-1);
factTail(n):
return factAux(1,n);
factTail(4)的递归树为:
factTail(4)
|
factAux(1,4)
|
factAux(4,3)
|
factAux(12,2)
|
factAux(24,1)
|
factAux(24,0)
|
24
这里,最大递归深度是O(n),但没有一个调用向堆栈添加任何额外变量。因此编译器可以取消堆栈。