什么是尾巴呼叫优化？

很简单，什么是尾部呼叫优化？ 更具体地说，任何人都可以在可以应用的地方显示一些小代码片段，哪里可以不显示，并解释为什么？

---

尾巴呼叫优化是您可以避免为函数分配新的堆栈帧的地方，因为调用函数将简单地返回它从被调用函数获得的值。 最常见的用法是tail-recursion，其中为了利用tail-call优化而编写的递归函数可以使用恒定的堆栈空间。

Scheme是少数几种在规范中保证任何实现都必须提供此优化的编程语言之一（一旦ES6完成，JavaScript也将提供），因此以下是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);
}

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

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

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只是运行，并返回任何值，它将被称为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)

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

链接地址: http://www.djcxy.com/p/2277.html

上一篇: What Is Tail Call Optimization?

下一篇: What is a stack and why is malloc prevent it from overflowing?