什么是尾调用优化？

很简单，什么是尾部调用优化？

更具体地说，有哪些小代码片段可以应用，哪些不能应用，并解释为什么？

259754 次浏览
小开

看这里：

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

你可能知道，递归函数调用会对堆栈造成严重破坏；很容易很快用完堆栈空间。尾调用优化是一种方法，你可以通过它创建一个使用恒定堆栈空间的递归样式算法，因此它不会增长和增长，你会得到堆栈错误。

小开
最佳答案

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

模式是为数不多的在规范中保证任何实现都必须提供这种优化的编程语言之一，所以这里有两个模式中阶乘函数的例子：

(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

正如你所看到的，我们只需要在每次调用face-ails时跟踪相同数量的数据，因为我们只是将直接通过的值返回到顶部。这意味着即使我要调用（事实1000000），我只需要与（事实3）相同数量的空间。非尾部递归事实并非如此，因此如此大的值可能会导致堆栈溢出。

小开

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

TCO适用于递归的特殊情况。它的要点是，如果你在函数中做的最后一件事是调用自己（例如，它从“尾”位置调用自己），编译器可以优化这一点，使其像迭代一样而不是标准递归。

你看，通常在递归过程中，运行时需要跟踪所有的递归调用，这样当一个返回时，它可以在前一个调用中恢复。（试着手动写出递归调用的结果，以直观地了解它是如何工作的。）跟踪所有调用会占用空间，当函数大量调用自己时，这会变得很重要。但是对于TCO，它可以只说“回到开始，只有这次将参数值更改为这些新值。”它可以这样做，因为递归调用之后没有任何内容引用这些值。

小开

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

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

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

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

dis(fact)2           0 LOAD_FAST                0 (n)2 LOAD_CONST               1 (0)4 COMPARE_OP               2 (==)6 POP_JUMP_IF_FALSE       12
3           8 LOAD_CONST               2 (1)10 RETURN_VALUE
4     >>   12 LOAD_FAST                0 (n)14 LOAD_GLOBAL              0 (fact)16 LOAD_FAST                0 (n)18 LOAD_CONST               2 (1)20 BINARY_SUBTRACT22 CALL_FUNCTION            124 BINARY_MULTIPLY26 RETURN_VALUE

这个函数除了在其返回语句中调用另一个函数之外还做其他事情。

下面的函数是TCOptimizable：

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

dis(fact)2           0 LOAD_GLOBAL              0 (fact_h)2 LOAD_FAST                0 (n)4 LOAD_CONST               1 (1)6 CALL_FUNCTION            28 RETURN_VALUE

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

小开

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

正如我们在这里看到的，足够先进的优化器可以用迭代替换尾递归，这要有效得多，因为您可以避免函数调用开销并且只使用恒定的堆栈空间。

小开

  1. 我们应该确保函数本身没有goto语句…由函数调用作为被调用函数的最后一件事来照顾。

  2. 大规模递归可以使用它进行优化，但在小规模中，使函数调用成为尾调用的指令开销会降低实际目的。

  3. TCO可能会导致永远运行的函数：

    void eternity(){eternity();}
小开

可能我找到的关于尾调用、递归尾调用和尾调用优化的最好的高级描述是博客文章

“见鬼的是什么：尾巴呼叫”

作者Dan Sugalski。关于尾部调用优化，他写道：

考虑一下这个简单的函数：

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

那么，你，或者更确切地说，你的语言编译器能做什么呢？它能做的就是将return somefunc();形式的代码转换为低级序列pop stack frame; goto somefunc();。在我们的例子中，这意味着在我们调用bar之前，foo清理自己，然后，而不是调用bar作为子例程，我们在bar的开头做了一个低级goto操作。Foo已经将自己清理出堆栈，所以当bar启动时，看起来调用foo的人真的调用了bar，当bar返回其值时，它直接将其返回给调用foo的人，而不是将其返回给foo，然后再将其返回给调用者。

关于尾巴递归：

如果函数作为其最后一次操作，返回，则会发生尾递归自称为的结果。尾递归更容易处理因为我们不必跳到某个随机事件的开头在某个地方运行，你只要做一个goto回到开头这是一件非常简单的事情

所以这个：

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）的人来说，它是多么简洁和容易掌握

小开

递归函数方法有一个问题。它构建了一个大小为O（n）的调用堆栈，这使得我们的总内存成本为O（n）。这使得它容易受到堆栈溢出错误的攻击，其中调用堆栈变得太大并耗尽空间。

尾调用优化（TCO）方案。它可以优化递归函数，避免建立高大的调用堆栈，从而节省内存成本。

有很多语言都在做TCO（JavaScript，ruby和一些C），而Python和Java不做TCO。

JavaScript语言已确认使用：）http://2ality.com/2015/06/tail-call-optimization.html

小开

带有x86反汇编分析的GCC C最小可运行示例

让我们看看GCC如何通过查看生成的程序集为我们自动执行尾调用优化。

这将作为一个非常具体的例子，说明在其他答案（例如https://stackoverflow.com/a/9814654/895245）中提到的优化可以将递归函数调用转换为循环。

这反过来节省内存并提高性能，因为内存访问通常是现在使程序变慢的主要原因。

作为输入，我们给GCC一个基于非优化朴素堆栈的阶乘：

tail_callc

#include <stdio.h>#include <stdlib.h>
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上游

编译和反汇编：

gcc -O1 -foptimize-sibling-calls -ggdb3 -std=c99 -Wall -Wextra -Wpedantic \-o tail_call.out tail_call.cobjdump -d tail_call.out

其中-foptimize-sibling-calls是根据man gcc泛化的尾调用的名称：

   -foptimize-sibling-callsOptimize sibling and tail recursive calls.
Enabled at levels -O2, -O3, -Os.

如上所述：如何检查gcc是否正在执行尾部递归优化？

我选择-O1是因为：

  • 优化不是用-O0完成的。我怀疑这是因为缺少所需的中间转换。
  • -O3产生的代码效率不高，不会很有教育意义，尽管它也是尾部调用优化的。

拆解-fno-optimize-sibling-calls：

0000000000001145 <factorial>:1145:       89 f8                   mov    %edi,%eax1147:       83 ff 01                cmp    $0x1,%edi114a:       74 10                   je     115c <factorial+0x17>114c:       53                      push   %rbx114d:       89 fb                   mov    %edi,%ebx114f:       8d 7f ff                lea    -0x1(%rdi),%edi1152:       e8 ee ff ff ff          callq  1145 <factorial>1157:       0f af c3                imul   %ebx,%eax115a:       5b                      pop    %rbx115b:       c3                      retq115c:       c3                      retq

使用-foptimize-sibling-calls：

0000000000001145 <factorial>:1145:       b8 01 00 00 00          mov    $0x1,%eax114a:       83 ff 01                cmp    $0x1,%edi114d:       74 0e                   je     115d <factorial+0x18>114f:       8d 57 ff                lea    -0x1(%rdi),%edx1152:       0f af c7                imul   %edi,%eax1155:       89 d7                   mov    %edx,%edi1157:       83 fa 01                cmp    $0x1,%edx115a:       75 f3                   jne    114f <factorial+0xa>115c:       c3                      retq115d:       89 f8                   mov    %edi,%eax115f:       c3                      retq

两者之间的主要区别在于：

  • -fno-optimize-sibling-calls使用callq，这是典型的非优化函数调用。

    该指令将返回地址推送到堆栈，因此增加了它。

    此外，这个版本也做了push %rbx，其中将#1推到堆栈。

    GCC这样做是因为它将edi（第一个函数参数（n））存储到ebx中，然后调用factorial。

    GCC需要这样做，因为它正在准备对factorial的另一次调用，这将使用新的edi == n-1。

    它选择ebx，因为这个寄存器是被调用保存的：通过linux x86-64函数调用保留哪些寄存器，所以对factorial的子调用不会改变它并丢失n。

  • -foptimize-sibling-calls不使用任何推送到堆栈的指令：它只使用指令je和jne在factorial中跳转goto。

    因此，这个版本相当于一个这时循环，没有任何函数调用。堆栈使用是恒定的。

在Ubuntu 18.10、GCC 8.2中测试。

小开

在函数式语言中，尾调用优化就像函数调用可以返回一个部分评估的表达式作为结果，然后由调用者评估。

f x = g x

f 6减少到g 6。因此，如果实现可以返回g 6作为结果，然后调用该表达式，它将保存一个堆栈帧。

还

f x = if c x then g x else h x.

将f 6减少到g 6或h 6。因此，如果实现评估c 6并发现它为真，那么它可以减少，

if true then g x else h x ---> g x
f x ---> h x

一个简单的非尾调用优化解释器可能看起来像这样，

class simple_expresion{...public:virtual ximple_value *DoEvaluate() const = 0;};
class simple_value{...};
class simple_function : public simple_expresion{...private:simple_expresion *m_Function;simple_expresion *m_Parameter;
public:virtual simple_value *DoEvaluate() const{vector<simple_expresion *> parameterList;parameterList->push_back(m_Parameter);return m_Function->Call(parameterList);}};
class simple_if : public simple_function{private:simple_expresion *m_Condition;simple_expresion *m_Positive;simple_expresion *m_Negative;
public:simple_value *DoEvaluate() const{if (m_Condition.DoEvaluate()->IsTrue()){return m_Positive.DoEvaluate();}else{return m_Negative.DoEvaluate();}}}

尾部调用优化解释器可能看起来像这样，

class tco_expresion{...public:virtual tco_expresion *DoEvaluate() const = 0;virtual bool IsValue(){return false;}};
class tco_value{...public:virtual bool IsValue(){return true;}};
class tco_function : public tco_expresion{...private:tco_expresion *m_Function;tco_expresion *m_Parameter;
public:virtual tco_expression *DoEvaluate() const{vector< tco_expression *> parameterList;tco_expression *function = const_cast<SNI_Function *>(this);while (!function->IsValue()){function = function->DoCall(parameterList);}return function;}
tco_expresion *DoCall(vector<tco_expresion *> &p_ParameterList){p_ParameterList.push_back(m_Parameter);return m_Function;}};
class tco_if : public tco_function{private:tco_expresion *m_Condition;tco_expresion *m_Positive;tco_expresion *m_Negative;
tco_expresion *DoEvaluate() const{if (m_Condition.DoEvaluate()->IsTrue()){return m_Positive;}else{return m_Negative;}}}

提交答案