番外篇 5 - 尾调用与尾递归

递归写起来顺手，可一旦层级深了就撞上栈溢出。有些语言承诺这种情况不会发生，C 不承诺。这篇番外说明尾调用是什么、编译器通常会做些什么、以及为什么在 C 里没法把它当成保证。

本篇不属于正文任何一部分。第一部分讲语言规则，而这件事标准根本没规定；第二部分讲工具链与工程，它又不属于构建、链接、测试、调试任何一环的知识主干。所以放在番外。

1. 什么是尾调用

一个函数调用如果满足：它的返回值直接就是另一次函数调用的结果，中间没有任何后续计算，那么这个调用就是尾调用（tail call）。

int f(int n);

/* 尾调用：返回值就是 f(n - 1) 的结果 */
int g(int n) {
    return f(n - 1);
}

/* 不是尾调用：返回值还要加 1 */
int h(int n) {
    return 1 + f(n - 1);
}

/* 不是尾调用：调用结果只是中间值 */
int k(int n) {
    int r = f(n - 1);
    return r * 2;
}

关键在于"调用之后还有没有事情要做"。g 调完 f 就可以直接把它返回的值交给自己的调用方，中间不需要再动任何东西；h 拿到结果之后还得做一次加法，k 拿到结果之后还得乘 2。

这个区别看起来琐碎，但它决定了当前这个栈帧在调用发生之后还有没有用。g 的栈帧调完就没用了，h 的栈帧还要留着算加法。

2. 为什么尾调用可以省掉栈帧

普通的函数调用大致是这样的：调用方把自己的状态压在栈上，把参数放进约定好的寄存器，执行 call 跳到被调函数；被调函数结束后把返回值放进寄存器，执行 ret 跳回调用方。中间这整段栈上状态就是一个栈帧（stack frame）。

尾调用的情况下，当前栈帧在调用之后不会被用到——返回值已经注定是调用结果，没有任何本地对象需要读回。因此被调函数完全可以直接复用当前栈帧：参数改一改，然后跳过去，等它返回时直接返回到当前函数的调用方那里。

在汇编层面，这个优化的标志是 call 变成 jmp。下面这段是 GCC 13.2 在 x86-64 上编译 is_even/is_odd 这对互相尾调用的函数的结果：

asm

is_even:
	testq	%rcx, %rcx
	jne	.L7
	movl	$1, %eax
	ret
.L7:
	subq	$1, %rcx
	jmp	is_odd          # 不是 call

jmp 不压栈、不留返回地址，所以无论递归多深，栈上永远只有最初那一帧。这就是"尾递归写成循环"在机器层面实际发生的事。

3. C 标准没有规定这件事

这是本篇最要紧的一点，也是它不能写进第一部分的原因。

C 标准在函数调用一节只规定了两件事：递归调用必须被允许（直接递归或间接递归都可以）；以及调用的语义。它对栈帧怎么管理没有任何要求，既没说要保留每一层，也没说可以复用。

换句话说：

标准不保证尾调用一定被优化。
标准也不禁止编译器优化掉它。
标准不保证不优化，所以你不能写一段依赖"每一层栈帧都存在"的代码。

三条合起来的意思就是：这里什么也没有承诺。同一个程序，换编译器、换版本、换优化选项，可能跑得完，也可能栈溢出，两种行为都符合标准。

我在这台机器上把 is_even/is_odd 用不同优化选项各编了一遍，看 is_even 里还有没有 call is_odd：

选项	`call is_odd` 出现次数
`-O0`	1
`-O1`	1
`-Og`	1
`-O2`	0
`-Os`	0
`-O2 -fno-optimize-sibling-calls`	1

递归一千万层时的实际表现也随之不同：-O2 编出来的版本正常退出，-O0 与 -O1 都因栈溢出崩溃。注意 -O1 不优化而 -O2 优化——这不是一条可以推广的规则，只是这个 GCC 版本在 x86-64 上的行为。

控制这个优化遍的开关是 -foptimize-sibling-calls，在 -O2、-Os、-O3 下默认打开。名字叫"兄弟调用"（sibling call），指的就是同一个函数里的尾调用。用 -fno-optimize-sibling-calls 可以单独关掉它：

bash

gcc -std=c17 -O2 -fno-optimize-sibling-calls tco.c -o tco

4. 各实现的做法

因为标准不管，各实现的态度也不一样：

GCC：在 -O2 及以上（含 -Os）默认打开 -foptimize-sibling-calls，做尾调用消除。-O0、-O1、-Og 不做（这是 13.2 的实测结果，别的版本可能不同）。
Clang：同样在优化构建下做。Clang 13 起提供了 musttail 属性，C++ 中写作 [[clang::musttail]]，C 中写作 __attribute__((musttail))，写在 return 语句前面，强制要求这个调用必须是尾调用，做不到就编译报错。
MSVC：x64 构建下的优化器会做尾调用，但微软的文档没有把它列为可依赖的保证；32 位构建下更没有承诺。MSVC 也没有对应的强制语法。

GCC 15 也加入了 [[gnu::musttail]] 语句属性：

#include <stddef.h>

extern int f(int);

int g(int n) {
    [[gnu::musttail]] return f(n);   /* 要求必须是尾调用 */
}

musttail 有一系列约束：返回值类型必须完全相同，实参必须在数量与类型上逐一对得上，等等。它解决的是"我确实需要这个保证"的场景，代价是牺牲了可移植性。GCC 15 之前的老版本不认识这个属性，只给出 'musttail' attribute ignored 警告然后当它不存在——这比编译报错更危险，因为程序照常编出来，却没有了那层保证。用 __has_c_attribute(gnu::musttail) 可以探测：GCC 13.2 上这个表达式为 0。

5. 在可移植的 C 里怎么保证

答案很直接：保证不了。

如果你确实需要处理任意深度，只能用这几种办法：

改写成循环。尾递归本来就能机械地转成循环：把累加量提成参数，然后 while 到终止条件。这是唯一完全可移植的做法。
显式栈。把递归要保存的状态放进自己管理的数组或链表，用循环驱动。适合状态不止一个累加量的场合。
依赖编译器扩展。musttail 或者厂商特定的选项。这就不是可移植代码了。
接受"通常够用"。很多场景下递归深度有自然上界（树的深度、表达式嵌套层数），几千层以内几乎所有实现都撑得住。这时可以不优化，但要写清这个前提。

第 4 种做法在实践中很常见，代价是：一旦输入比预期深，程序就会崩，而且不保证崩在哪里。

6. 它会留下什么可观测的痕迹

尾调用消除不是纯优化——它改变了你能观察到的东西：

调试器的调用栈变短了。 在普通递归里，bt 能看到每一层；尾调用优化之后，中间那些层在栈上根本不存在。下面是在 is_even/is_odd 里断在 is_odd 的 n == 0 处，-O0 与 -O2 的 bt 对比（MinGW-w64 GCC 13.2，gdb -batch -ex "break is_odd if n==0" -ex run -ex bt --args ./tco 3）：

text

# -O0
#0  is_odd (n=0) at tco.c:12
#1  0x... in is_even (n=1) at tco.c:8
#2  0x... in is_odd (n=2) at tco.c:13
#3  0x... in is_even (n=3) at tco.c:8
#4  0x... in main (argc=2, argv=0x781010) at tco.c:17

# -O2
#0  is_odd (n=0) at tco.c:12
#1  0x... in is_even (n=<optimized out>) at tco.c:8
#2  0x... in main (argc=<optimized out>, argv=0x7b1010) at tco.c:17

调用层级从三层递归掉到一层：is_even 用 jmp 调 is_odd，中间那些 is_odd、is_even 帧都没有机会建立。如果你指望 bt 还原完整的递归路径，这里就会失望。

崩溃现场可能断掉。 程序在深层递归里栈溢出时，转储的调用链往往只剩浅几层，因为栈本身已经用尽了。这种崩溃报告比"崩在哪儿"更难读。

性能也会变。 省掉了栈帧的分配与销毁，尾递归版本可能比循环版本还快一点点。但这属于测量的范畴，不属于本篇。

调试器那一章（12 调试器）讲过 -O2 下 <optimized out> 与内联导致的断点分裂；尾调用消除是同一类现象的另一个来源。

7. 和其他语言的对照

值得知道的一点：不是所有语言都像 C 一样不承诺。 Scheme 从 1975 年起就在标准里要求尾调用消除，所以 Scheme 程序员敢用尾递归写循环。Python 则明确不做这件事，它的递归深度上限是 1000 层左右。

C 处在两者之间：实现通常会做，标准不保证。这就是为什么它适合放进番外——它不是 C 的语言规则，而是"实现做了什么"的问题，跨了语言、跨了平台，也跨了调试、性能、可移植性几个主题。

参考资料

GCC 手册 · Options That Control Optimization（-foptimize-sibling-calls）
GCC 15 Release Notes（musttail 语句属性）
Clang 13 Release Notes（musttail 属性）
Scheme 语言标准 R7RS（尾调用消除的要求）

番外篇 5 - 尾调用与尾递归 ​

1. 什么是尾调用 ​

2. 为什么尾调用可以省掉栈帧 ​

3. C 标准没有规定这件事 ​

4. 各实现的做法 ​

5. 在可移植的 C 里怎么保证 ​

6. 它会留下什么可观测的痕迹 ​

7. 和其他语言的对照 ​

参考资料 ​