当我开始学习口齿不清时,我遇到了“尾部递归”这个词。这到底是什么意思?


当前回答

在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)。

与普通递归相比,尾部递归非常快。它很快,因为祖先调用的输出不会写入堆栈以保持跟踪。但在正常递归中,所有祖先调用堆栈中的输出以保持跟踪。