什么是尾部呼叫优化？

Question

什么是尾部呼叫优化？很简单，什么是尾部优化？更具体地说，有人能给我们展示一些小的代码片段，在哪里可以应用，哪些地方不能，并解释原因？

Answer 1

尾部调用优化可以避免为函数分配新的堆栈框架，因为调用函数只会返回从被调用函数获得的值。最常见的用法是尾递归，其中为利用尾调用优化而编写的递归函数可以使用常量堆栈空间。

方案是少数几种在规范中保证任何实现都必须提供这种优化的编程语言之一。(JavaScript也是这样，从ES6开始)，下面是方案中阶乘函数的两个示例：

(define (fact x)

  (if (= x 0) 1

      (* x (fact (- x 1)))))

(define (fact x)

  (define (fact-tail x accum)

    (if (= x 0) accum

        (fact-tail (- x 1) (* x accum))))

  (fact-tail x 1))

第一个函数不是尾递归函数，因为在进行递归调用时，函数需要跟踪调用返回后与结果有关的乘法。因此，堆栈看起来如下：

(fact 3)

(* 3 (fact 2))

(* 3 (* 2 (fact 1)))

(* 3 (* 2 (* 1 (fact 0))))

(* 3 (* 2 (* 1 1)))

(* 3 (* 2 1))

(* 3 2)

6

相反，尾递归阶乘的堆栈跟踪如下所示：

(fact 3)

(fact-tail 3 1)

(fact-tail 2 3)

(fact-tail 1 6)

(fact-tail 0 6)

6

正如您所看到的，我们只需要跟踪对事实尾的每一次调用的相同数据量，因为我们只是简单地将得到的值直接返回到顶部。这意味着，即使我打电话给(事实1000000)，我只需要与(事实3)相同的空间。非尾递归事实并非如此，因此较大的值可能会导致堆栈溢出。

Answer 2

让我们来看看一个简单的例子：用C实现的阶乘函数。

我们从明显的递归定义开始。

unsigned fac(unsigned n){
    if (n < 2) return 1;
    return n * fac(n - 1);}

如果函数返回之前的最后一次操作是另一个函数调用，则函数以尾调用结束。如果这个调用相同的函数，那么它是尾递归的.

即使fac()乍一看，它看起来像是尾递归，而不是实际发生的事情。

unsigned fac(unsigned n){
    if (n < 2) return 1;
    unsigned acc = fac(n - 1);
    return n * acc;}

最后一个操作是乘法，而不是函数调用。

然而，重写是可能的fac()要成为尾递归，可以将累积值作为附加参数传递到调用链中，并将最终结果作为返回值再次传递：

unsigned fac(unsigned n){
    return fac_tailrec(1, n);}unsigned fac_tailrec(unsigned acc, unsigned n){
    if (n < 2) return acc;
    return fac_tailrec(n * acc, n - 1);}

现在，为什么这是有用的？因为我们在尾调用之后立即返回，所以我们可以在以尾位置调用函数之前丢弃以前的堆栈帧，或者，在递归函数的情况下，可以按原样重用堆栈帧。

尾叫优化将我们的递归代码转换为

unsigned fac_tailrec(unsigned acc, unsigned n){TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;}

这可以内联成fac()我们到达

unsigned fac(unsigned n){
    unsigned acc = 1;TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;}

相当于

unsigned fac(unsigned n){
    unsigned acc = 1;

    for (; n > 1; --n)
        acc *= n;

    return acc;}

正如我们在这里看到的，一个足够高级的优化器可以用迭代代替尾递归，这是更有效的，因为您避免了函数调用开销，并且只使用了固定的堆栈空间。

Answer 3

TCO(尾调用优化)是智能编译器调用函数而不占用额外堆栈空间的过程。这个只有当在函数中执行最后一条指令时才会发生这种情况。f是对函数g的调用。(注：g可以f)。这里的关键是f不再需要堆栈空间-它只是调用g然后再返回任何东西g会回来的。在这种情况下，优化可以使g只运行并返回调用f的东西的任何值。

这种优化可以使递归调用占用恒定的堆栈空间，而不是爆炸。

示例：这个阶乘函数不是TCOptimable的：

def fact(n):
    if n == 0:
        return 1
    return n * fact(n-1)

该函数除了在其返回语句中调用另一个函数外，还执行其他任务。

下面的函数是TCOptimable的：

def fact_h(n, acc):
    if n == 0:
        return acc    return fact_h(n-1, acc*n)def fact(n):
    return fact_h(n, 1)

这是因为这些函数中的最后一件事是调用另一个函数。