什么是尾巴呼叫优化？

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

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

Scheme是在规范中保证任何实现都必须提供这种优化的less数几种编程语言之一（在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))

第一个函数不是尾recursion，因为recursion调用时，函数需要跟踪在调用返回后需要对结果进行乘法运算。 因此，堆栈如下所示： 

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

相反，尾recursion阶乘的堆栈轨迹如下所示： 

 (fact 3) (fact-tail 3 1) (fact-tail 2 3) (fact-tail 1 6) (fact-tail 0 6) 6

正如您所看到的，我们只需要跟踪每个调用事实尾巴的相同数量的数据，因为我们只是将我们获得的值返回到顶端。 这意味着，即使我打电话（事实1000000），我只需要（事实3）相同数量的空间。 非尾recursion事实并非如此，因为这样大的值可能导致堆栈溢出。

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

我们从明显的recursion定义开始 

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

如果函数返回前的最后一个操作是另一个函数调用，则函数以尾调用结束。 如果这个调用调用相同的函数，它是尾recursion的。

尽pipefac()乍看之下看起来是尾recursion的，但事实并非如此 

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

即最后的操作是乘法而不是函数调用。

但是，可以通过将累加值作为附加parameter passing给调用链，并将最终结果作为返回值再次传递，从而重写fac()为tail-recursive： 

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

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

尾部调用优化将我们的recursion代码转换成 

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

正如我们在这里可以看到的，一个足够先进的优化器可以用迭代replace尾recursion，这样可以避免函数调用的开销，并且只使用恒定数量的堆栈空间，效率更高。

TCO（尾部调用优化）是智能编译器可以调用函数并且不占用额外堆栈空间的过程。 发生这种情况的唯一情况是，如果在函数f中执行的最后一条指令是对函数g的调用 （注意： g可以是f ）。 这里的关键是f不再需要堆栈空间 – 它只是调用g然后返回g将返回的任何东西。 在这种情况下，可以进行优化，g只是运行，并返回任何值的东西，所谓的f。

这种优化可以使recursion调用采取恒定的堆栈空间，而不是爆炸。

例如：这个阶乘函数不是TCOptimizable： 

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

这个函数除了在return语句中调用另一个函数之外，

这下面的function是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)

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

博客文章可能是我已经find的最好的高级描述，即尾部调用，recursion尾部调用和尾部调用优化

“到底是什么：尾巴叫”

由丹Sugalski。 在尾巴呼叫优化他写道：

考虑一下，这个简单的function： 

 sub foo (int a) { a += 15; return bar(a); }

那么，你能做什么，或者说你的语言编译器呢？ 那么，它可以做的是转换forms的代码return somefunc(); 进入低级序列pop stack frame; goto somefunc(); pop stack frame; goto somefunc(); 。 在我们的例子中，这意味着在我们调用bar之前， foo清理自己，然后，而不是将bar作为子例程调用，我们对bar的开始做一个低级的goto操作。 Foo已经把自己从堆栈中清理出来了，所以当bar开始的时候，看起来像所谓的foo真的叫bar ，当bar返回它的值的时候，它直接返回给所有叫做foo ，而不是返回给foo ，然后将其返回给调用者。

而在尾recursion上：

如果函数作为最后一个操作返callback用自身的结果 ， 则会发生尾recursion。 尾recursion更容易处理，因为不必跳到某个随机函数的开始，而只是回到自己的开始，这是一个简单的事情。

所以这个： 

 sub foo (int a, int b) { if (b == 1) { return a; } else { return foo(a*a + a, b - 1); }

悄然变成： 

 sub foo (int a, int b) { label: if (b == 1) { return a; } else { a = a*a + a; b = b - 1; goto label; }

我喜欢这个描述的是，如何把握来自命令式语言背景（C，C ++，Java）的简洁和容易，

首先请注意，并非所有的语言都支持它。

TCO适用于recursion的特殊情况。 它的要点是，如果你在函数中做的最后一件事情是调用自己（例如，它正在从“尾部”位置调用它自己），编译器可以将其优化，以代替标准recursion来进行迭代。

通常在recursion过程中，运行时需要跟踪所有recursion调用，以便在返回时可以在前一个调用中恢复，等等。 （尝试手动写出recursion调用的结果，以获得这种工作方式的可视化思路。）跟踪所有调用占用空间，当函数调用很多时会占用很大的空间。 但是对于TCO，只能说“回到起点，只有这个时候把参数值改成这个新的”。 它可以做到这一点，因为在recursion调用之后什么都没有引用这些值。

看这里：

http://tratt.net/laurie/tech_articles/articles/tail_call_optimization

正如你可能知道的那样，recursion函数调用可能会对栈造成严重破坏; 快速用完堆栈空间很容易。 尾部调用优化是您可以创build使用常量堆栈空间的recursion样式algorithm的方式，因此它不会增长和增长，并会出现堆栈错误。

  1. 我们应该确保函数本身没有goto语句。函数调用是被调用函数中的最后一项。

  2. 大规模的recursion可以用于优化，但是在小规模的情况下，使函数调用成为尾调用的指令开销减less了实际的目的。

  3. TCO可能会导致永久运行function： 

     void eternity() { eternity(); }
Interesting Posts