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


当前回答

尾部递归是你现在的生活。您不断重复使用相同的堆栈帧,因为没有理由或方法返回到“先前”帧。过去已经结束,可以抛弃。你得到一帧,永远走向未来,直到你的过程不可避免地消亡。

当您考虑到某些进程可能会使用额外的帧,但如果堆栈没有无限增长,则仍然被认为是尾部递归时,这种类比就失败了。

其他回答

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

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

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

下面是比较两个函数的快速代码片段。第一种是传统的递归,用于求给定数的阶乘。第二种使用尾部递归。

理解起来非常简单直观。

判断递归函数是否为尾部递归函数的一种简单方法是,它是否在基本情况下返回具体值。这意味着它不会返回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);
    }
}

许多人已经在这里解释了递归。我想引用Riccardo Terrell的《.NET中的并发性,并发和并行编程的现代模式》一书中关于递归的一些优点的一些想法:

“函数递归是FP中迭代的自然方式,因为它避免状态突变。在每次迭代期间,都会传递一个新值而不是被更新(变异)。在里面此外,可以编写递归函数,使您的程序更加模块化,并引入了开发机会并行化。"

以下是同一本书中关于尾部递归的一些有趣注释:

尾部调用递归是一种转换规则递归的技术函数转换为可处理大型输入的优化版本没有任何风险和副作用。注:尾部调用作为优化的主要原因是提高数据位置、内存使用率和缓存使用率。通过做尾巴调用时,被调用者使用与调用者相同的堆栈空间。这减少了记忆压力。它略微改善了缓存,因为存储器被后续调用方重用,并且可以留在缓存中,而不是驱逐旧的缓存线,为新的缓存腾出空间线

在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);
}