什么是尾端递回最佳化（Tail Call Optimization）？

摘要

尾端呼叫最佳化（Tail Call Optimization，TCO）是一种编译器最佳化技术，旨在减少函式于尾端位置进行呼叫时所需的执行状态与堆叠空间。在符合语义及应用程式二进位介面（Application Binary Interface，ABI）要求的情况下，编译器可以重用或移除目前函式的堆叠框架，将控制权直接转移至被呼叫函式，避免不必要的呼叫层级。

当函式在尾端位置呼叫自身时，称为尾端递回（Tail Recursion）。编译器可以将这类递回转换为回圈，此技术称为尾端递回消除（Tail Recursion Elimination，TRE）。

本文介绍递回与堆叠框架的基本原理、尾端位置的判定方式、尾端呼叫最佳化的实作机制及其限制，并分析 x86-64 与 ARM64 架构下的机器指令、LLVM 中介表示法与 GCC 编译器的相关最佳化功能。此外，本文亦探讨尾端呼叫最佳化对记忆体复杂度、执行效能、侦错及程式语义的影响。

关键词： 尾端呼叫最佳化、尾端递回、编译器、堆叠框架、尾端递回消除、LLVM、GCC、呼叫惯例、机器码。

---

一、递回与函式呼叫机制

1.1. 什么是递回？

递回（Recursion）是指函式直接或间接呼叫自身，以处理可分解为较小子问题的计算过程。

递回演算法通常包含两个部分：

1. 终止条件（Base Case）： 决定何时停止递回呼叫。
2. 递回步骤（Recursive Case）： 透过新的函式呼叫继续处理规模较小的问题。

以阶乘为例，非负整数 $n$ 的阶乘定义为：

可使用 C 语言表示：

unsigned long long factorial(unsigned int n) {
    if n==0 {
        return 1;
    }

    return n * factorial(n - 1);
}

这是一个直接递回函式，因为 factorial 会呼叫自身。

当 n = 4 时，逻辑上的计算过程如下：

factorial(4)
    4 * factorial(3)
        3 * factorial(2)
            2 * factorial(1)
                1 * factorial(0)
                    1

抵达终止条件后，各层函式依序完成剩余运算：

factorial(0) = 1
factorial(1) = 1 * 1 = 1
factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6
factorial(4) = 4 * 6 = 24

此例的关键在于，每次递回呼叫返回后，原本的函式仍须执行乘法。

因此，尚未完成的计算状态必须被保留。

1.2. 堆叠框架（Stack Frame）

当程式呼叫函式时，执行环境通常需要保存与该次呼叫相关的状态。

这些资讯可能包括：

• 返回位址（Return Address）。
• 必须存放于记忆体中的区域变数。
• 需要保存与还原的暂存器。
• 无法完全透过暂存器传递的参数。
• 计算过程使用的暂存空间。
• 与例外处理或侦错相关的资讯。

用于维持一次函式执行状态的堆叠区域，通常称为堆叠框架。

但并非所有函式呼叫都必然建立独立的实体堆叠框架。实际配置取决于处理器架构、呼叫惯例、编译器及最佳化设定。

在未进行适当最佳化的情况下，递回呼叫可能使多个函式执行状态同时存在。

例如：

递回呼叫期间的逻辑堆叠

┌──────────────────────────┐
│ factorial(0)             │
├──────────────────────────┤
│ factorial(1)             │
├──────────────────────────┤
│ factorial(2)             │
├──────────────────────────┤
│ factorial(3)             │
├──────────────────────────┤
│ factorial(4)             │
├──────────────────────────┤
│ 呼叫 factorial(4) 的函式 │
└──────────────────────────┘

上述为概念示意，并不代表特定 ABI 的实际记忆体配置。

假设每层递回皆需保留固定大小的堆叠框架，其堆叠使用量可近似表示为：

其中：

• $S(n)$：递回过程所需的堆叠空间。
• $S_0$：原有堆叠使用量。
• $n$：同时存在的递回呼叫层数。
• $F$：每层呼叫平均需要的堆叠空间。

在上述假设下，堆叠空间需求随递回深度线性增加。

---

二、什么是尾端递回？

2.1. 尾端位置（Tail Position）

尾端位置是指某个运算式的结果可以直接作为目前函式的结果，而无须在该运算完成后继续执行其他计算的位置。

例如：

int f(int x) {
    return gx;
}

g$x$ 位于尾端位置，因为 f 直接返回 g 的结果。

相对地：

int f(int x) {
    return gx + 1;
}

此处 g$x$ 并非尾端呼叫。

原因是 g 返回后，f 仍须执行加法运算。

因此，判定尾端位置的关键，不是函式呼叫是否出现在程式码的最后一行，而是呼叫完成后是否仍有必须执行的工作。

2.2. 尾端呼叫（Tail Call）

尾端呼叫是指位于尾端位置的函式呼叫。

例如：

int process(int x) {
    return calculatex;
}

其中 calculate$x$ 是尾端呼叫，但并非递回，因为 process 并未呼叫自身。

2.3. 尾端递回（Tail Recursion）

尾端递回是函式在尾端位置直接或间接再次呼叫自身的情况。

可将阶乘函式改写为使用累加器（Accumulator）的形式：

unsigned long long factorial_acc(
    unsigned int n,
    unsigned long long acc
) {
    if n==0 {
        return acc;
    }

    return factorial_acc(n - 1, acc * n);
}

unsigned long long factorial(unsigned int n) {
    return factorial_acc(n, 1);
}

此时，递回函式不再需要于返回后执行乘法。

所有中间结果已经透过 acc 传递至下一次呼叫。

执行 factorial(4) 时：

尾端递回呼叫为：

return factorial_acc(n - 1, acc * n);

函式不必等待下一层递回返回后再执行额外运算。

这使该函式具有转换为回圈的条件。

2.4. 尾端呼叫与尾端递回的差异

尾端呼叫最佳化的适用范围比尾端递回消除更广。

因为符合条件的尾端呼叫，也可能发生于不同函式之间。

---

三、尾端呼叫最佳化的基本原理

3.1. 定义

尾端呼叫最佳化（Tail Call Optimization，TCO）是编译器利用尾端位置的特性，避免保留不再需要的函式呼叫状态，从而减少额外堆叠空间与呼叫成本的技术。

考虑以下函式：

int f(int x) {
    return gx;
}

未经最佳化时，其控制流程可能为：

f 呼叫 g
    ↓
g 执行
    ↓
g 返回 f
    ↓
f 返回原呼叫者

若符合最佳化条件，编译器可以将其转换为：

f 准备 g 所需的参数
    ↓
释放或调整 f 不再需要的执行状态
    ↓
直接跳转至 g
    ↓
g 返回原本呼叫 f 的函式

这种处理方式可以避免维持不必要的呼叫层级。

但实际最佳化并不一定表现为单纯的跳转指令。编译器可能需要调整暂存器、堆叠位置及其他执行状态。

3.2. 堆叠使用方式的差异

未最佳化的递回呼叫：

┌────────────────────────┐
│ factorial_acc(0)       │
├────────────────────────┤
│ factorial_acc(1)       │
├────────────────────────┤
│ factorial_acc(2)       │
├────────────────────────┤
│ factorial_acc(3)       │
├────────────────────────┤
│ factorial_acc(4)       │
└────────────────────────┘

尾端递回消除后：

┌────────────────────────┐
│ factorial_acc          │
│                        │
│ n   = 当前参数         │
│ acc = 累积结果         │
│                        │
│ 透过回圈更新状态       │
└────────────────────────┘

在第二种情况下，程式不必为每次递回迭代保留新的函式呼叫状态。

3.3. 记忆体复杂度

假设每层递回需要固定大小的执行状态，且递回深度与 $n$ 成正比：

未最佳化时：

成功转换为固定状态的回圈后：

这里的 $O(1)$ 指的是执行该回圈所需的额外堆叠空间，不代表程式的所有记忆体使用量都必然为常数。

例如，演算法仍可能配置随输入增加的堆积记忆体（Heap Memory）。

---

四、尾端递回消除的实作机制

4.1. 将递回转换为回圈

考虑以下程式：

unsigned int sum_tail(
    unsigned int n,
    unsigned int acc
) {
    if n==0 {
        return acc;
    }

    return sum_tail(n - 1, acc + n);
}

可以在不改变此范例结果的前提下，将其转换为：

unsigned int sum_loop(
    unsigned int n,
    unsigned int acc
) {
    while n!=0 {
        acc += n;
        n -= 1;
    }

    return acc;
}

在第二种形式中，原本的递回呼叫变成回圈中的状态更新。

因此，不再需要每次建立新的呼叫层级。

这是尾端递回消除最典型的实作方式之一。

4.2. 中介表示法（Intermediate Representation）

现代编译器通常会先将原始码转换为中介表示法（IR），再透过最佳化阶段进行分析与转换。

在此阶段中，编译器可以辨识：

1. 函式是否呼叫自身。
2. 递回呼叫是否位于尾端位置。
3. 呼叫返回后是否仍需执行其他运算。
4. 是否能安全地将呼叫转换为控制流程跳转。
5. 参数及区域状态是否可以直接更新。

LLVM 的 tailcallelim 最佳化阶段便是相关实作之一。

LLVM 文件说明：

This file transforms calls of the current function (self recursion) followed by a return instruction with a branch to the entry of the function, creating a loop.

（中文译文：此最佳化将目前函式的自我递回呼叫及其后的返回指令，转换为跳转至函式入口的分支指令，从而形成回圈。）

资料来源：LLVM，LLVM's Analysis and Transform Passes，tailcallelim。^[1]

除基本形式外，LLVM 亦可在特定条件下处理部分尾端呼叫前后的简单运算，或透过累加器等方式进行等效转换。

4.3. x86-64 架构中的实作

在 x86-64 架构中，常见的控制流程指令包括：

考虑：

extern int calculate(int x);

int process(int x) {
    return calculatex;
}

一般函式呼叫在概念上可表示为：

process:
    call calculate
    ret

在符合最佳化条件时，可以转换为：

process:
    jmp calculate

使用 jmp 时，处理器不会因该跳转而建立新的返回位址。

如果函式的执行状态已经按照 ABI 要求安排完成，被呼叫函式便可以直接返回原先的呼叫者。

上述组语为说明原理的简化范例，并非所有编译器与平台必然产生的机器码。

实际程式可能还需要额外指令来调整堆叠、恢复暂存器或配置参数。

4.4. ARM64 架构中的实作

在 AArch64 架构中，常见的控制流程指令包括：

AArch64 通常使用 X30 作为连结暂存器（Link Register）。

一般呼叫形式：

process:
    bl calculate
    ret

在符合条件时，可以使用：

process:
    b calculate

由于 B 不会更新连结暂存器，因此被呼叫函式可以在原有返回位址仍有效的情况下，直接返回最初的呼叫者。

但是否能进行此种转换，仍须符合平台 ABI 与呼叫惯例。

相关规范可参考 Arm 的 AAPCS64 文件。^[7]

---

五、尾端呼叫最佳化的必要条件

5.1. 呼叫必须处于尾端位置

最基本的条件是呼叫返回后，函式不再需要执行其他运算。

可以作为尾端呼叫：

int f(int x) {
    return gx;
}

不是尾端呼叫：

int f(int x) {
    return gx * 2;
}

第二个例子仍须等待 g 的返回值，并进行乘法运算。

但编译器仍可能透过其他最佳化技术改写这类程式。因此，非尾端呼叫不代表完全无法最佳化。

5.2. 必须符合呼叫惯例（Calling Convention）

呼叫惯例规定函式之间如何传递参数、返回结果及保存处理器状态。

相关要求包括：

• 用于传递参数的暂存器。
• 呼叫者与被呼叫者需要保存的暂存器。
• 返回值的表示方式。
• 透过堆叠传递参数的方法。
• 堆叠对齐要求。
• 可变参数函式的处理方式。
• 大型结构体或复合资料的返回方式。

即使函式呼叫在语义上处于尾端位置，如果无法遵守 ABI 所要求的状态配置，编译器仍可能无法直接将其转换为尾端跳转。

5.3. 区域变数的生命周期

考虑：

extern int use_pointer(const int *p);

int fvoid {
    int value = 10;
    return use_pointer(&value);
}

此处 use_pointer 接收区域变数 value 的位址。

若编译器在 use_pointer 尚未完成之前，便释放存放 value 的堆叠空间，可能使该指标失去有效的存取对象。

因此，不能在破坏变数生命周期或改变程式语义的情况下，强制移除目前函式的堆叠框架。

5.4. 资源清理与例外处理

部分语言具有在函式结束时必须执行的清理机制。

例如：

• 物件解构函式。
• 自动资源释放。
• finally 区块。
• 例外处理状态更新。
• 堆叠安全检查。

若这些操作必须在被呼叫函式返回后执行，原始呼叫就可能不再符合直接尾端呼叫的条件。

编译器必须保证所有必要的语义行为仍然正确。

5.5. 平台及后端限制

尾端呼叫最佳化亦受到以下因素影响：

• CPU 架构。
• 作业系统 ABI。
• 编译器后端。
• 最佳化等级。
• 返回值型别。
• 函式属性。
• 呼叫惯例及堆叠配置。

因此，尾端递回的语法形式不等于编译器必然会执行尾端递回消除。

---

六、GCC 与 LLVM 的尾端呼叫最佳化

6.1. GCC

GCC 提供以下最佳化选项：

-foptimize-sibling-calls

GCC 文件说明：

Optimize sibling and tail recursive calls.

（中文译文：最佳化同层函式呼叫与尾端递回呼叫。）

在 GCC 14.3 的文件中，该选项会于 -O2、-O3 及 -Os 最佳化等级启用。^[2]

例如：

gcc -O2 -S example.c -o example.s

此指令可以输出组合语言，供研究者检查函式呼叫是否已被最佳化。

不过，启用选项只代表编译器可以尝试相关最佳化，并不保证所有尾端呼叫都能被消除。

6.2. LLVM

LLVM IR 提供多种与尾端呼叫相关的标记。

以下是 LLVM IR 的简化范例：

define i32 @f(i32 %x) {
entry:
  %result = tail call i32 @g(i32 %x)
  ret i32 %result
}

declare i32 @gi32

tail 标记本身并不保证最终机器码一定采用尾端跳转。

相较之下，musttail 具有更严格的语义要求。

LLVM Language Reference 对 musttail 规定了函式型别、呼叫惯例、参数、返回型别及呼叫位置等限制。

在符合规定的情况下，编译器必须确保尾端呼叫的正确执行语义，使此类呼叫不因额外保留不必要的呼叫框架而造成无界的堆叠增长。^[3]

6.3. 最佳化机会与语义保证

对尾端递回的支援可分为三种情况：

1. 原始码具有尾端递回形式，但语言并未要求编译器执行最佳化。
2. 编译器可以辨识尾端呼叫，并在可行时执行最佳化。
3. 语言或中介表示法明确要求在特定条件下保证尾端呼叫。

这三种情况具有不同的可靠性要求。

对于使用深度递回作为主要控制流程的程式而言，是否具有尾端呼叫保证，会直接影响演算法在有限堆叠空间中的可执行性。

6.4. Scheme 的正确尾端递回

Scheme 是研究尾端呼叫的重要语言之一。

在 Scheme 的 R5RS 报告中，正确尾端递回（Proper Tail Recursion）被明确规定为语言实作要求。

原文：

Implementations of Scheme are required to be properly tail-recursive.

（中文译文：Scheme 的实作必须支援正确的尾端递回。）

资料来源：Revised⁵ Report on the Algorithmic Language Scheme，第3.5节。^[4]

Scheme 的要求不仅是鼓励编译器提升效率，而是规定执行环境应能以适当方式处理尾端呼叫，使任意数量的有效尾端呼叫不必因累积无用的返回续体而消耗不断增加的控制空间。

这并不表示程式拥有无限记忆体，而是要求尾端呼叫本身不应造成不必要的堆叠增长。

---

七、效能与记忆体影响

7.1. 堆叠记忆体使用量

尾端呼叫最佳化最重要的效果，是减少不必要的堆叠空间消耗。

当尾端递回被转换为回圈时，程式不再需要为每次迭代保存新的函式呼叫状态。

此技术对下列类型的程式可能特别重要：

• 长度较大的序列处理。
• 递回式资料结构演算法。
• 函数式语言。
• 直译器与虚拟机器。
• 使用函式呼叫表达控制流程的程式。

7.2. 函式呼叫成本

成功的尾端呼叫最佳化可能减少以下成本：

• 返回位址的保存。
• 堆叠框架的建立与拆除。
• 部分暂存器保存与还原。
• 额外的控制流程转移。

不过，实际效能改善程度受到 CPU 微架构、编译器、ABI 及程式特性的影响。

因此，不应假设所有尾端呼叫最佳化都会带来显著的执行速度提升。

7.3. 时间复杂度

以前述阶乘函式为例，无论是否使用尾端递回，计算过程仍须执行与 $n$ 成比例的乘法。

因此，其时间复杂度仍为：

若成功转换为固定状态的回圈，额外堆叠空间可能由：

降低为：

这表示尾端呼叫最佳化主要改变执行方式与记忆体使用效率，而不必然改变演算法本身的时间复杂度。

---

八、限制与注意事项

8.1. 并非所有递回都是尾端递回

例如：

unsigned long long factorial(unsigned int n) {
    if n==0 {
        return 1;
    }

    return n * factorial(n - 1);
}

此函式的递回呼叫返回后仍须执行乘法，因此不属于尾端递回。

某些编译器可能透过其他方法改写这类递回，但不能将其视为必然发生的最佳化。

8.2. 尾端递回不保证完全避免堆叠溢位

如果编译器没有执行最佳化，即使原始码符合尾端递回形式，也可能因呼叫层级不断增加而消耗堆叠空间。

此外，程式仍可能因其他函式呼叫、过大的区域资料或执行环境限制而发生堆叠溢位。

因此，必须区分原始码具有尾端递回结构，与执行环境保证尾端呼叫最佳化这两件事。

8.3. 对侦错的影响

尾端呼叫被转换为跳转或回圈后，侦错器中显示的呼叫堆叠可能与原始码中的函式呼叫结构不同。

部分呼叫框架可能不再出现。

这可能影响：

• 呼叫堆叠追踪。
• 函式执行顺序分析。
• 堆叠回溯。
• 效能分析及取样。

编译器与侦错工具可能利用额外资讯补充这些差异，但不保证所有经最佳化的呼叫历程都能完整还原。

8.4. 与其他最佳化技术的关系

尾端呼叫最佳化可能与其他编译器最佳化共同作用，例如：

• 函式内联（Inlining）。
• 常数传播（Constant Propagation）。
• 死码消除（Dead Code Elimination）。
• 回圈最佳化（Loop Optimization）。
• 控制流程简化（Control Flow Simplification）。

因此，若最终机器码中不再出现原本的递回呼叫，仍需进一步分析是哪些最佳化共同产生了该结果。

---

九、如何验证尾端呼叫最佳化？

9.1. 测试程式

以下使用 C 语言建立一个简单范例：

__attribute__((noinline))
unsigned long long sum_tail(
    unsigned int n,
    unsigned long long acc
) {
    if n==0 {
        return acc;
    }

    return sum_tail(n - 1, acc + n);
}

int mainvoid {
    return sum_tail(10, 0) != 55;
}

noinline 属性用于限制 GCC 或 Clang 将函式直接内联至呼叫者，使其函式本身的机器码较容易观察。

但此属性不会禁止所有其他最佳化，也不会自动阻止尾端递回消除。

9.2. 使用 GCC 测试

分别以未最佳化及较高最佳化等级编译：

gcc -O0 -S test.c -o test_O0.s
gcc -O2 -S test.c -o test_O2.s

比较两个输出的组合语言档案。

应观察：

• 是否仍存在对 sum_tail 的递回呼叫。
• 是否出现回圈结构。
• 是否使用分支指令取代呼叫指令。
• 是否减少堆叠框架的建立与拆除。

具体结果依 GCC 版本、目标架构及最佳化设定而异。

9.3. 使用 Clang 测试

clang -O0 -S test.c -o test_O0.s
clang -O2 -S test.c -o test_O2.s

若要检查 LLVM IR，可使用：

clang -O2 -S -emit-llvm test.c -o test.ll

在 IR 或机器码中，可以寻找下列特征：

• 原本的递回呼叫已被回圈取代。
• 呼叫具有与尾端最佳化相关的标记。
• 出现取代函式呼叫的分支控制流程。
• 堆叠配置方式发生改变。

不过，这些只是需要进一步分析的技术迹象，不能仅凭某个单一指令便确定完整的最佳化过程。

---

十、结论

尾端呼叫最佳化是编译器设计与实作中的重要技术。

它利用尾端位置不再需要保留呼叫者后续运算状态的特性，使编译器能够在适当条件下消除多余的函式呼叫层级。

对于尾端递回而言，编译器可以将递回呼叫转换为回圈，使执行过程不必随着递回深度持续增加堆叠框架。

然而，尾端呼叫最佳化并非单纯的语法转换，其正确性受到函式呼叫惯例、ABI、资料生命周期、例外处理及编译器后端等因素限制。

因此，理解尾端呼叫、尾端递回、尾端呼叫最佳化与尾端递回消除之间的差异，是正确认识此技术的基础。

对编译器研究而言，尾端呼叫最佳化亦提供了一个典型案例，展示程式语义、中介表示法、控制流程转换及机器码生成之间的关系。

---

附录一：技术术语

附录二：参考文献与延伸阅读

A. 编译器技术文件

[1] LLVM Project, LLVM's Analysis and Transform Passes.

说明 LLVM 的 tailcallelim 最佳化阶段，以及将自我尾端递回转换为回圈的原理。

https://llvm.org/docs/Passes.html

[2] GNU Compiler Collection, Optimize Options.

说明 -foptimize-sibling-calls 选项及不同最佳化等级的相关设定。

https://gcc.gnu.org/onlinedocs/gcc-14.3.0/gcc/Optimize-Options.html

[3] LLVM Project, LLVM Language Reference Manual.

LLVM IR 官方规格，包含 tail、musttail、notail 及呼叫惯例等内容。

https://llvm.org/docs/LangRef.html

[4] Clang Project, Attribute Reference.

提供 musttail 等函式呼叫相关属性的规范与限制。

https://clang.llvm.org/docs/AttributeReference.html

B. 程式语言与尾端递回研究

[5] Richard Kelsey, William Clinger, Jonathan Rees（编），Revised⁵ Report on the Algorithmic Language Scheme，1998。

第3.5节「Proper Tail Recursion」规定 Scheme 正确尾端递回的要求。

https://www.gnu.org/software/guile/manual/r5rs/Proper-tail-recursion.html

[6] Guy L. Steele Jr.、Gerald Jay Sussman，Lambda: The Ultimate Imperative，MIT Artificial Intelligence Laboratory，AI Memo 353，1976。

探讨 Scheme 语言、续体及函式呼叫执行模型的重要早期研究。

C. 处理器架构与 ABI 规范

[7] Arm Limited, Procedure Call Standard for the Arm 64-bit Architecture（AAPCS64）.

AArch64 的官方程序呼叫规范，涉及暂存器、参数传递、返回值及堆叠使用。

https://github.com/ARM-software/abi-aa/blob/main/aapcs64/aapcs64.rst

[8] System V Application Binary Interface, AMD64 Architecture Processor Supplement.

x86-64 System V ABI 规范，包含函式呼叫惯例、暂存器使用及堆叠配置。

https://gitlab.com/x86-psABIs/x86-64-ABI

[9] Intel, Intel 64 and IA-32 Architectures Software Developer's Manuals.

x86 指令集官方文件，包含 CALL、RET、JMP 等指令。

https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html

D. 建议延伸阅读主题

1. 堆叠框架（Stack Frame）的构造与生命周期。
2. 堆叠溢位（Stack Overflow）的成因与防护。
3. 呼叫惯例与应用程式二进位介面（ABI）。
4. 中介表示法（IR）与控制流程最佳化。
5. 连结器（Linker）在编译与执行流程中的角色。

---

注释