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


当前回答

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

其他回答

尾部递归函数是一个递归函数,它在返回之前执行的最后一个操作是调用递归函数。也就是说,递归函数调用的返回值将立即返回。例如,您的代码如下所示:

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个自然数相加的简单函数。(例如,和(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解释器不支持它。

这意味着不需要将指令指针推到堆栈上,只需跳到递归函数的顶部并继续执行即可。这允许函数无限递归而不会溢出堆栈。

我写了一篇关于这个主题的博客文章,里面有堆栈框架的图形示例。

递归意味着函数调用自身。例如:

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

我不是Lisp程序员,但我认为这会有所帮助。

基本上,这是一种编程风格,递归调用是最后一件事。