什么是尾调用优化？

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

Scheme 是少数在规范中保证任何实现都必须提供这种优化的编程语言之一，所以这里有两个 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

如您所见，我们只需要为每次调用 fact-tail 跟踪相同数量的数据，因为我们只是将获得的值返回到顶部。这意味着即使我要调用 (fact 1000000)，我也只需要与 (fact 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：

from dis import dis

def fact(n):
    if n == 0:
        return 1
    return 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_SUBTRACT
             22 CALL_FUNCTION            1
             24 BINARY_MULTIPLY
             26 RETURN_VALUE

这个函数除了在它的 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)


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

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

---

对于尾调用、递归尾调用和尾调用优化，我发现的最好的高级描述可能是博客文章

"What the heck is: A tail call"

丹苏加尔斯基。关于尾调用优化，他写道：

考虑一下这个简单的函数： sub foo (int a) { a += 15;返回栏（a）；那么，你，或者更确切地说是你的语言编译器，能做什么呢？好吧，它可以做的是将表单的代码变成 return somefunc();进入低级序列弹出栈帧；转到 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 { 返回 foo(a*a + a, b - 1); }

悄悄地变成：

sub foo (int a, int b) { label: if (b == 1) { return a; } 其他 { a = a*a + a; b = b - 1;转到标签； }

我喜欢这个描述的地方在于，对于那些来自命令式语言背景（C、C++、Java）的人来说，它是多么简洁和容易掌握

---

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

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

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

这反过来又节省了内存并提高了性能，因为 memory accesses are often the main thing that makes programs slow nowadays。

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

tail_call.c

#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 upstream。

编译和反汇编：

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

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

   -foptimize-sibling-calls
       Optimize sibling and tail recursive calls.

       Enabled at levels -O2, -O3, -Os.

如上所述：How do I check if gcc is performing tail-recursion optimization?

我选择 -O1 是因为：

优化不是用 -O0 完成的。我怀疑这是因为缺少所需的中间转换。

-O3 生成效率不高的代码，虽然它也进行了尾调用优化，但它的教育性并不高。

使用 -fno-optimize-sibling-calls 反汇编：

0000000000001145 <factorial>:
    1145:       89 f8                   mov    %edi,%eax
    1147:       83 ff 01                cmp    $0x1,%edi
    114a:       74 10                   je     115c <factorial+0x17>
    114c:       53                      push   %rbx
    114d:       89 fb                   mov    %edi,%ebx
    114f:       8d 7f ff                lea    -0x1(%rdi),%edi
    1152:       e8 ee ff ff ff          callq  1145 <factorial>
    1157:       0f af c3                imul   %ebx,%eax
    115a:       5b                      pop    %rbx
    115b:       c3                      retq
    115c:       c3                      retq

使用 -foptimize-sibling-calls：

0000000000001145 <factorial>:
    1145:       b8 01 00 00 00          mov    $0x1,%eax
    114a:       83 ff 01                cmp    $0x1,%edi
    114d:       74 0e                   je     115d <factorial+0x18>
    114f:       8d 57 ff                lea    -0x1(%rdi),%edx
    1152:       0f af c7                imul   %edi,%eax
    1155:       89 d7                   mov    %edx,%edi
    1157:       83 fa 01                cmp    $0x1,%edx
    115a:       75 f3                   jne    114f <factorial+0xa>
    115c:       c3                      retq
    115d:       89 f8                   mov    %edi,%eax
    115f:       c3                      retq

两者的主要区别在于：

-fno-optimize-sibling-calls 使用 callq，这是典型的非优化函数调用。该指令将返回地址推入堆栈，从而增加它。此外，此版本还推送 %rbx，它将 %rbx 推送到堆栈。 GCC 这样做是因为它存储了 edi，这是 ebx 中的第一个函数参数 (n)，然后调用阶乘。 GCC 需要这样做，因为它正在准备再次调用阶乘，这将使用新的 edi == n-1。它选择 ebx 是因为该寄存器是被调用者保存的：哪些寄存器是通过 linux x86-64 函数调用保留的，因此对阶乘的子调用不会更改它并丢失 n。

-foptimize-sibling-calls 不使用任何推入堆栈的指令：它只使用指令 je 和 jne 在阶乘内跳转。因此，这个版本相当于一个while循环，没有任何函数调用。堆栈使用是恒定的。

在 Ubuntu 18.10、GCC 8.2 中测试。

---

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

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

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

---

看这里：

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

您可能知道，递归函数调用会对堆栈造成严重破坏。很容易快速耗尽堆栈空间。尾调用优化是您可以创建使用恒定堆栈空间的递归样式算法的方式，因此它不会增长和增长并且您会遇到堆栈错误。

---

递归函数方法有问题。它建立了一个大小为 O(n) 的调用堆栈，这使得我们的总内存成本为 O(n)。这使得它容易受到堆栈溢出错误的影响，即调用堆栈变得太大并且空间不足。

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

有许多语言在做 TCO，比如（JavaScript、Ruby 和少数 C），而 Python 和 Java 不做 TCO。

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

---

我们应该确保函数本身没有 goto 语句。函数调用是被调用函数中的最后一件事。大规模递归可以使用它进行优化，但在小规模下，使函数调用尾调用的指令开销降低了实际目的。 TCO 可能会导致函数永远运行： void eternity() { eternity(); }

---

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

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

---