当我开始学习口齿不清时,我遇到了“尾部递归”这个词。这到底是什么意思?
当前回答
对我来说,理解尾调用递归的最好方法是递归的一种特殊情况,其中最后一个调用(或尾调用)是函数本身。
比较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
其他回答
尾部递归是指递归算法中最后一条逻辑指令中的最后一个递归调用。
通常在递归中,您有一个基本情况,即停止递归调用并开始弹出调用堆栈。使用一个经典的例子,尽管比Lisp更具C语言,阶乘函数说明了尾部递归。递归调用在检查基本情况条件后发生。
factorial(x, fac=1) {
if (x == 1)
return fac;
else
return factorial(x-1, x*fac);
}
对阶乘的初始调用将是阶乘(n),其中fac=1(默认值),n是要计算阶乘的数字。
递归函数是一个自己调用的函数
它允许程序员用最少的代码编写高效的程序。
缺点是,如果编写不当,它们可能会导致无限循环和其他意外结果。
我将解释简单递归函数和尾部递归函数
为了编写简单的递归函数
首先要考虑的一点是你应该什么时候决定出来是if循环的第二个问题是,如果我们是自己的职能部门,我们应该做什么
从给定的示例中:
public static int fact(int n){
if(n <=1)
return 1;
else
return n * fact(n-1);
}
从上面的例子中
if(n <=1)
return 1;
是何时退出循环的决定因素
else
return n * fact(n-1);
是否要进行实际处理
为了便于理解,让我逐一完成任务。
让我们看看如果我运行事实(4),内部会发生什么
替换n=4
public static int fact(4){
if(4 <=1)
return 1;
else
return 4 * fact(4-1);
}
如果循环失败,则转到else循环因此它返回4*事实(3)
在堆栈内存中,我们有4*事实(3)替换n=3
public static int fact(3){
if(3 <=1)
return 1;
else
return 3 * fact(3-1);
}
如果循环失败,则转到else循环
因此它返回3*事实(2)
记住我们称之为“4*事实”(3)``
事实(3)的输出=3*事实(2)
到目前为止,堆栈具有4*事实(3)=4*3*事实(2)
在堆栈内存中,我们有4*3*事实(2)替换n=2
public static int fact(2){
if(2 <=1)
return 1;
else
return 2 * fact(2-1);
}
如果循环失败,则转到else循环
因此它返回2*事实(1)
记住我们称之为4*3*事实(2)
事实(2)的输出=2*事实(1)
到目前为止,堆栈具有4*3*事实(2)=4*3*2*事实(1)
在堆栈内存中,我们有4*3*2*事实(1)替换n=1
public static int fact(1){
if(1 <=1)
return 1;
else
return 1 * fact(1-1);
}
如果循环为真
所以它返回1
记住我们称之为4*3*2*事实(1)
事实(1)的输出=1
到目前为止,堆栈具有4*3*2*事实(1)=4*3*2*1
最后,事实(4)的结果=4*3*2*1=24
尾部递归将是
public static int fact(x, running_total=1) {
if (x==1) {
return running_total;
} else {
return fact(x-1, running_total*x);
}
}
替换n=4
public static int fact(4, running_total=1) {
if (x==1) {
return running_total;
} else {
return fact(4-1, running_total*4);
}
}
如果循环失败,则转到else循环因此它返回事实(3,4)
在堆栈内存中,我们有事实(3,4)替换n=3
public static int fact(3, running_total=4) {
if (x==1) {
return running_total;
} else {
return fact(3-1, 4*3);
}
}
如果循环失败,则转到else循环
因此它返回事实(2,12)
在堆栈内存中,我们有事实(2,12)替换n=2
public static int fact(2, running_total=12) {
if (x==1) {
return running_total;
} else {
return fact(2-1, 12*2);
}
}
如果循环失败,则转到else循环
因此它返回事实(1,24)
在堆栈内存中,我们有事实(1,24)替换n=1
public static int fact(1, running_total=24) {
if (x==1) {
return running_total;
} else {
return fact(1-1, 24*1);
}
}
如果循环为真
因此它返回running_total
running_total=24的输出
最后,事实(4,1)的结果=24
这意味着不需要将指令指针推到堆栈上,只需跳到递归函数的顶部并继续执行即可。这允许函数无限递归而不会溢出堆栈。
我写了一篇关于这个主题的博客文章,里面有堆栈框架的图形示例。
使用常规递归,每个递归调用将另一个条目推送到调用堆栈中。递归完成后,应用程序必须将每个条目向下弹出。
使用尾部递归,根据语言的不同,编译器可以将堆栈折叠为一个条目,这样可以节省堆栈空间。。。大型递归查询实际上会导致堆栈溢出。
基本上,尾部递归可以优化到迭代中。
与普通递归相比,尾部递归非常快。它很快,因为祖先调用的输出不会写入堆栈以保持跟踪。但在正常递归中,所有祖先调用堆栈中的输出以保持跟踪。