当我开始学习口齿不清时,我遇到了“尾部递归”这个词。这到底是什么意思?
当前回答
下面是比较两个函数的快速代码片段。第一种是传统的递归,用于求给定数的阶乘。第二种使用尾部递归。
理解起来非常简单直观。
判断递归函数是否为尾部递归函数的一种简单方法是,它是否在基本情况下返回具体值。这意味着它不会返回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);
}
}
其他回答
这本摘自《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)。如果输入的数字很高,可能会导致堆栈溢出。
尾部递归函数是一个递归函数,它在返回之前执行的最后一个操作是调用递归函数。也就是说,递归函数调用的返回值将立即返回。例如,您的代码如下所示:
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个帧对象。)这会导致堆栈溢出错误。(嘿,这就是这个网站的名字来源!)
但是,如果递归函数做的最后一件事是进行递归调用并返回其返回值,那么它就没有理由保持当前帧对象需要停留在调用堆栈上。毕竟,如果递归函数调用后没有代码,就没有理由挂起当前帧对象的局部变量。因此,我们可以立即删除当前帧对象,而不是将其保留在调用堆栈中。这样做的最终结果是,调用堆栈的大小不会增加,因此不会出现堆栈溢出。
编译器或解释器必须具有尾部调用优化功能,以便能够识别何时可以应用尾部调用优化。即使如此,您可能已经重新排列了递归函数中的代码,以利用尾部调用优化,这取决于您是否值得优化可读性的潜在降低。
重要的一点是尾部递归本质上等同于循环。这不仅仅是一个编译器优化的问题,而是一个关于表现力的基本事实。这是双向的:你可以采取任何形式的循环
while(E) { S }; return Q
其中E和Q是表达式,S是语句序列,并将其转换为尾部递归函数
f() = if E then { S; return f() } else { return Q }
当然,必须定义E、S和Q来计算一些变量的有趣值。例如,循环函数
sum(n) {
int i = 1, k = 0;
while( i <= n ) {
k += i;
++i;
}
return k;
}
等效于尾部递归函数
sum_aux(n,i,k) {
if( i <= n ) {
return sum_aux(n,i+1,k+i);
} else {
return k;
}
}
sum(n) {
return sum_aux(n,1,0);
}
(用参数较少的函数“包装”尾部递归函数是一种常见的函数习惯用法。)
尾部递归是函数调用的递归函数自身位于函数的末尾(“尾部”),其中没有计算在递归调用返回后完成。许多编译器优化以将递归调用更改为尾部递归调用或迭代调用。
考虑计算一个数的阶乘的问题。
一种简单的方法是:
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),但没有一个调用向堆栈添加任何额外变量。因此编译器可以取消堆栈。
我不是Lisp程序员,但我认为这会有所帮助。
基本上,这是一种编程风格,递归调用是最后一件事。