很简单,什么是尾部调用优化？更具体地说,任何人都可以显示一些可以应用的小代码片段,而不是在哪里,并解释为什么？
尾调用优化是您可以避免为函数分配新堆栈帧的地方,因为调用函数将只返回它从被调用函数获得的值.最常见的用法是尾递归,其中为利用尾调用优化而编写的递归函数可以使用常量堆栈空间.
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);
}
现在,为什么这有用？因为我们在尾调用之后立即返回,所以我们可以在尾部位置调用函数之前丢弃先前的堆栈帧,或者,在递归函数的情况下,按原样重用堆栈帧.
尾调用优化将我们的递归代码转换为
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)
这是因为在这些函数中发生的最后一件事是调用另一个函数.
我发现尾部调用,递归尾调用和尾调用优化的最佳高级描述可能是博客文章
"到底是什么:尾巴叫"
作者Dan Sugalski.关于尾调用优化,他写道:
暂时考虑一下这个简单的功能:
sub foo (int a) { a += 15; return bar(a); }那么,你或者你的语言编译器能做什么呢？那么,它能做的是将表单的代码
return somefunc();转换为低级序列pop stack frame; goto somefunc();.在我们的例子中,这意味着在我们调用之前bar,foo清理自己然后,而不是调用bar作为子例程,我们goto在开始时执行低级操作bar.Foo已经从堆栈中清除了自己,所以当bar启动它时,看起来好像有人foo调用了bar,当bar它返回它的值时,它会直接将它返回给任何调用者foo,而不是将其返回到foo然后将其返回给调用者.
并在尾递归:
如果函数作为其最后一个操作返回调用自身的结果,则会发生尾递归.尾部递归更容易处理,因为你不必在某个地方跳到某个随机函数的开头,而只是回到自己的开头,这是一件很容易做的事情.
这样:
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适用于递归的特殊情况.它的要点是,如果你在函数中做的最后一件事是调用它自己(例如它从"尾部"位置调用它自己),这可以由编译器优化,就像迭代而不是标准递归.
您会看到,通常在递归期间,运行时需要跟踪所有递归调用,以便在返回时它可以在上一次调用时恢复,依此类推.(尝试手动写出递归调用的结果,以便直观地了解其工作原理.)跟踪所有调用会占用空间,当函数调用自身时会占用很多空间.但是对于TCO,它可以说"回到开头,只是这次将参数值更改为这些新值." 它可以做到这一点,因为在递归调用之后没有任何内容引用那些值.
GCC minimal runnable example with x86 disassembly analysis
Let's see how GCC can automatically do tail call optimizations for us by looking at the generated assembly.
This will serve as an extremely concrete example of what was mentioned in other answers such as /sf/ask/17360801/ that the optimization can convert recursive function calls to a loop.
This in turn saves memory and improves performance, since memory accesses are often the main thing that makes programs slow nowadays.
As an input, we give GCC a non-optimized naive stack based factorial:
tail_call.c
#include#include unsigned factorial(unsigned n) { if (n == 1) { return 1; } return n * factorial(n - 1); } int main(int argc, char **argv) { int input; if (argc > 1) { input = strtoul(argv[1], NULL, 0); } else { input = 5; } printf("%u\n", factorial(input)); return EXIT_SUCCESS; }
GitHub upstream.
Compile and disassemble:
gcc -O1 -foptimize-sibling-calls -ggdb3 -std=c99 -Wall -Wextra -Wpedantic \ -o tail_call.out tail_call.c objdump -d tail_call.out
where -foptimize-sibling-calls is the name of generalization of tail calls according to man gcc:
-foptimize-sibling-calls
Optimize sibling and tail recursive calls.
Enabled at levels -O2, -O3, -Os.
as mentioned at: How do I check if gcc is performing tail-recursion optimization?
I choose -O1 because:
the optimization is not done with -O0. I suspect that this is because there are required intermediate transformations missing.
-O3 produces ungodly efficient code that would not be very educative, although it is also tail call optimized.
Disassembly with -fno-optimize-sibling-calls:
京公网安备 11010802040832号