协慌网

很简单，什么是尾叫优化？更具体地说，任何人都可以显示一些小的代码片段，在何处可以应用它，而在何处不可以，并解释其原因？

尾调用优化可以避免为函数分配新的堆栈帧，因为调用函数将简单地返回它从被调用函数获得的值。最常见的用途是尾部递归，其中利用尾部调用优化编写的递归函数可以使用恒定的堆栈空间。

Scheme 是在规范中保证任何实现都必须提供此优化的少数编程语言之一（JavaScript 也是从 ES6 开始） ，因此这是 Scheme 中的阶乘函数的两个示例：

(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）相同的空间。非尾递归事实并非如此，因为如此大的值可能会导致堆栈溢出。

让我们来看一个简单的示例：用 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);
}

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

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

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

正如我们在这里看到的那样，足够先进的优化器可以用迭代代替尾部递归，因为这样可以避免函数调用开销并且仅使用恒定数量的堆栈空间，因此效率更高。

TCO（尾部调用优化）是智能编译器可以通过该过程调用函数而无需占用额外堆栈空间的过程。 发生这种情况的唯一情况是，在函数f 中执行的最后一条指令是对函数 g 的调用 （注意： g可以是f ）。这里的关键是f不再需要堆栈空间 - 它仅调用g然后返回g所返回的值。在这种情况下，可以对 g 进行优化，使 g 正常运行并返回给 f 的所有值。

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

示例：此阶乘函数不是 TCOptimizable：

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

该函数除了在其 return 语句中调用另一个函数外，还执行其他操作。

以下功能是 TCOptimizable：

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)

这是因为在任何这些函数中发生的最后一件事情是调用另一个函数。