当我开始学习口齿不清时,我遇到了“尾部递归”这个词。这到底是什么意思?
当前回答
在Java中,以下是斐波那契函数的一个可能的尾部递归实现:
public int tailRecursive(final int n) {
if (n <= 2)
return 1;
return tailRecursiveAux(n, 1, 1);
}
private int tailRecursiveAux(int n, int iter, int acc) {
if (iter == n)
return acc;
return tailRecursiveAux(n, ++iter, acc + iter);
}
与标准递归实现形成对比:
public int recursive(final int n) {
if (n <= 2)
return 1;
return recursive(n - 1) + recursive(n - 2);
}
其他回答
考虑一个将前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解释器不支持它。
这里是前面提到的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
}
如果每个递归情况仅由对函数本身的调用组成,并且可能具有不同的参数,则函数是尾部递归的。或者,尾部递归是没有待定工作的递归。注意,这是一个与编程语言无关的概念。
考虑定义如下的函数:
g(a, b, n) = a * b^n
一种可能的尾部递归公式是:
g(a, b, n) | n is zero = a
| n is odd = g(a*b, b, n-1)
| otherwise = g(a, b*b, n/2)
如果您检查g(…)的每一个涉及递归情况的RHS,您会发现整个RHS都是对g(……)的调用,仅此而已。这个定义是尾部递归的。
作为比较,非尾部递归公式可能是:
g'(a, b, n) = a * f(b, n)
f(b, n) | n is zero = 1
| n is odd = f(b, n-1) * b
| otherwise = f(b, n/2) ^ 2
f(…)中的每个递归情况都有一些需要在递归调用之后进行的未决工作。
注意,当我们从“g”到“g”时,我们充分利用了关联性(和交换性)乘法。这并不是偶然的,在大多数需要将递归转换为尾递归的情况下,都会利用这些财产:如果我们想急切地做一些工作,而不是让它等待,我们必须使用关联性之类的东西来证明答案是一样的。
尾部递归调用可以通过向后跳转来实现,而不是使用堆栈进行常规递归调用。注意,检测尾部呼叫或发出向后跳转通常很简单。然而,通常很难重新排列参数,以便向后跳转。由于此优化不是免费的,语言实现可以选择不实现此优化,或者通过使用“tailcall”指令标记递归调用和/或选择更高的优化设置来要求选择加入。
然而,某些语言(例如Scheme)确实需要所有实现来优化尾部递归函数,甚至可能需要所有尾部位置的调用。
在大多数命令式语言中,向后跳转通常被抽象为(while)循环,而尾部递归在优化为向后跳转时,与循环同构。
递归意味着函数调用自身。例如:
(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)。
与普通递归相比,尾部递归非常快。它很快,因为祖先调用的输出不会写入堆栈以保持跟踪。但在正常递归中,所有祖先调用堆栈中的输出以保持跟踪。