当我开始学习口齿不清时,我遇到了“尾部递归”这个词。这到底是什么意思?
当前回答
尾部递归函数是一个递归函数,它在返回之前执行的最后一个操作是调用递归函数。也就是说,递归函数调用的返回值将立即返回。例如,您的代码如下所示:
def recursiveFunction(some_params):
# some code here
return recursiveFunction(some_args)
# no code after the return statement
实现尾部调用优化或尾部调用消除的编译器和解释器可以优化递归代码以防止堆栈溢出。如果您的编译器或解释器没有实现尾部调用优化(例如CPython解释器),那么用这种方式编写代码不会有额外的好处。
例如,这是Python中的标准递归阶乘函数:
def factorial(number):
if number == 1:
# BASE CASE
return 1
else:
# RECURSIVE CASE
# Note that `number *` happens *after* the recursive call.
# This means that this is *not* tail call recursion.
return number * factorial(number - 1)
这是阶乘函数的尾调用递归版本:
def factorial(number, accumulator=1):
if number == 0:
# BASE CASE
return accumulator
else:
# RECURSIVE CASE
# There's no code after the recursive call.
# This is tail call recursion:
return factorial(number - 1, number * accumulator)
print(factorial(5))
(请注意,即使这是Python代码,CPython解释器也不会进行尾部调用优化,因此这样安排代码不会带来运行时的好处。)
您可能需要使代码更不可读,才能利用尾部调用优化,如阶乘示例所示。(例如,基本情况现在有点不直观,累加器参数被有效地用作一种全局变量。)
但尾部调用优化的好处是它可以防止堆栈溢出错误。(我会注意到,通过使用迭代算法而不是递归算法,您可以获得同样的好处。)
当调用堆栈推送了太多帧对象时,会导致堆栈溢出。当调用函数时,框架对象被推到调用堆栈上,当函数返回时,框架将从调用堆栈中弹出。框架对象包含诸如局部变量以及函数返回时要返回的代码行之类的信息。
如果递归函数进行了太多递归调用而没有返回,则调用堆栈可能会超出其帧对象限制。(数量因平台而异;在Python中默认为1000个帧对象。)这会导致堆栈溢出错误。(嘿,这就是这个网站的名字来源!)
但是,如果递归函数做的最后一件事是进行递归调用并返回其返回值,那么它就没有理由保持当前帧对象需要停留在调用堆栈上。毕竟,如果递归函数调用后没有代码,就没有理由挂起当前帧对象的局部变量。因此,我们可以立即删除当前帧对象,而不是将其保留在调用堆栈中。这样做的最终结果是,调用堆栈的大小不会增加,因此不会出现堆栈溢出。
编译器或解释器必须具有尾部调用优化功能,以便能够识别何时可以应用尾部调用优化。即使如此,您可能已经重新排列了递归函数中的代码,以利用尾部调用优化,这取决于您是否值得优化可读性的潜在降低。
其他回答
术语文件对尾部递归的定义有这样的说法:
尾部递归/n/
如果您还没有厌倦它,请参阅尾部递归。
这本摘自《Lua编程》一书的摘录展示了如何进行正确的尾部递归(在Lua中,但也应适用于Lisp)以及为什么它更好。
尾部调用[尾部递归]是一种goto-dressed作为呼叫。当函数调用另一个作为其最后一个行动,所以它没有其他事情可做。例如在以下代码中,对g的调用是尾调用:函数f(x)返回g(x)终止在f调用g之后,它没有其他内容在这种情况下,程序不需要返回调用函数时调用的函数末端。因此在尾呼之后,程序不需要保留任何有关调用函数的信息在堆栈中。。。因为正确的尾呼使用no堆栈空间一个程序可以生成。例如,我们可以使用任意数字作为自变量;它永远不会溢出堆栈:函数foo(n)如果n>0,则返回foo(n-1)end终止…正如我前面所说的,尾呼是有点后顾之忧。因此,一个非常有用的正确的尾部调用在Lua用于编程状态机。此类应用程序可以代表功能状态;更改状态是去(或打电话)一个特定的作用例如,让我们考虑一个简单的迷宫游戏。迷宫有几个房间,每个房间最多四个门:北、南、东和西在每个步骤中,用户输入移动方向。如果有门在该方向上,用户将相应的房间;否则程序打印警告。目标是从最初的房间到最后的房间房间该游戏是典型的状态机,其中当前房间是状态。我们可以用一个每个房间的功能。我们用尾巴从一个房间移动到另一个有四个房间的小迷宫可能看起来像这样:功能室1()本地移动=io.read()如果移动==“南”,则返回房间3()elseif move==“east”然后返回room2()否则打印(“无效移动”)返回房间1()--呆在同一个房间终止终止功能室2()本地移动=io.read()如果move==“south”,则返回room4()elseif move==“west”然后返回房间1()否则打印(“无效移动”)返回室2()终止终止功能室3()本地移动=io.read()如果move==“north”,则返回room1()elseif move==“east”然后返回room4()否则打印(“无效移动”)返回室3()终止终止功能室4()打印(“恭喜!”)终止
因此,当您进行如下递归调用时:
function x(n)
if n==0 then return 0
n= n-2
return x(n) + 1
end
这不是尾部递归的,因为在进行递归调用之后,您仍然需要在该函数中做一些事情(添加1)。如果输入的数字很高,可能会导致堆栈溢出。
递归函数是一个自己调用的函数
它允许程序员用最少的代码编写高效的程序。
缺点是,如果编写不当,它们可能会导致无限循环和其他意外结果。
我将解释简单递归函数和尾部递归函数
为了编写简单的递归函数
首先要考虑的一点是你应该什么时候决定出来是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
递归意味着函数调用自身。例如:
(define (un-ended name)
(un-ended 'me)
(print "How can I get here?"))
尾部递归是指结束函数的递归:
(define (un-ended name)
(print "hello")
(un-ended 'me))
看,非终结函数(Scheme术语中的过程)做的最后一件事就是调用自己。另一个(更有用的)例子是:
(define (map lst op)
(define (helper done left)
(if (nil? left)
done
(helper (cons (op (car left))
done)
(cdr left))))
(reverse (helper '() lst)))
在helper过程中,如果左边不是nil,最后一件事就是调用自己(AFTER cons something和cdr something)。这基本上就是如何映射列表的。
尾部递归有一个很大的优点,即解释器(或编译器,取决于语言和供应商)可以对其进行优化,并将其转换为相当于while循环的东西。事实上,在Scheme传统中,大多数“for”和“while”循环都是以尾部递归的方式完成的(据我所知,没有for和while)。
考虑一个将前N个自然数相加的简单函数。(例如,和(5)=0+1+2+3+4+5=15)。
下面是一个使用递归的简单JavaScript实现:
function recsum(x) {
if (x === 0) {
return 0;
} else {
return x + recsum(x - 1);
}
}
如果调用recsum(5),JavaScript解释器将评估以下内容:
recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + (1 + recsum(0)))))
5 + (4 + (3 + (2 + (1 + 0))))
5 + (4 + (3 + (2 + 1)))
5 + (4 + (3 + 3))
5 + (4 + 6)
5 + 10
15
请注意,在JavaScript解释器开始实际计算和之前,每个递归调用都必须完成。
下面是同一函数的尾部递归版本:
function tailrecsum(x, running_total = 0) {
if (x === 0) {
return running_total;
} else {
return tailrecsum(x - 1, running_total + x);
}
}
以下是调用tailrecsum(5)时发生的事件序列(由于默认的第二个参数,它实际上是tailrecsum(5,0))。
tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15
在尾部递归情况下,每次对递归调用求值时,running_total都会更新。
注:原始答案使用了Python中的示例。由于Python解释器不支持尾部调用优化,这些代码已更改为JavaScript。然而,虽然尾部调用优化是ECMAScript 2015规范的一部分,但大多数JavaScript解释器不支持它。