极客教程

Appearance

共 786 字预计阅读约 3 分钟

C 语言尾调用优化 ​

更新时间：2026-08-26。本文是 languages/c/ 主题专家层文档。递归优雅但危险——100 万层递归就能撑爆栈。但如果你把递归写成"尾递归"，编译器能把它优化成循环，既保留递归的清晰、又拿到循环的性能。本文用实测的"栈溢出 vs 安全跑完"讲透这个优化。

本文要回答的问题 ​

  • 什么是尾调用？尾递归和普通递归差在哪？
  • 编译器在什么条件下能做尾调用优化？
  • 怎么写递归才能让编译器优化成循环？

一、尾调用是什么 ​

尾调用（tail call）：函数做的最后一个操作是调用另一个函数。

c
// 尾调用：调用是最后一个操作，之后直接返回
int f(int x) {
    return g(x);   // g(x) 的返回值直接作为 f 的返回值
}

// 非尾调用：调用后还有操作
int f2(int x) {
    return g(x) + 1;   // 调完 g 还要 +1
}

尾递归是尾调用的特例——递归调用自己是尾调用。

二、实测：尾递归 vs 普通递归 ​

尾递归（递归调用是最后一个操作）：

c
int tail_recursive(int n, int acc) {
    if (n == 0) return acc;
    return tail_recursive(n - 1, acc + n);   // 尾调用
}

普通递归（递归后还有 + n）：

c
int normal_recursive(int n) {
    if (n == 0) return 0;
    return n + normal_recursive(n - 1);       // 非尾调用
}

调用 tail_recursive(1000000, 0)，实测：

text
=== -O0（无优化）===
Segmentation fault      ← 100 万层递归，栈溢出崩溃！

=== -O2（尾调用优化）===
tail_recursive(1000000, 0) = 1784293664   ← 优化成循环，正常跑完

同样的代码，-O0 栈溢出崩溃，-O2 优化成循环安全跑完。 这就是尾调用优化的威力。

三、优化后的反汇编（铁证） ​

-O2 下 tail_recursive 的反汇编：

asm
0000000000400560 <tail_recursive>:
  400560:  test   %edi,%edi        ; n == 0 ?
  400562:  mov    %esi,%eax        ; eax = acc
  400564:  je     400577           ; 是则返回
  400570:  add    %edi,%eax        ; acc += n
  400572:  sub    $0x1,%edi        ; n--
  400575:  jne    400570           ; 循环
  400577:  retq

整个函数里没有一条 call 指令！编译器把递归彻底改写成了 add/sub/jne 的循环——不产生任何栈帧，栈占用恒定，100 万次也安全。

四、尾调用优化的条件 ​

编译器能消除尾调用的条件：

  1. 调用是最后一个操作（返回值直接透传，调用后无其他计算）
  2. 递归调用自身（尾递归），或编译器知道目标函数
  3. 无需要销毁的局部对象（C 里满足，C++ 有析构函数则受限）

为什么普通递归不能优化：n + normal_recursive(n-1) 里，递归调用后还要 + n，编译器必须保留当前栈帧（存 n）才能完成后续计算，所以每层都要压栈。

五、尾递归改写技巧 ​

把"递归后还有操作"的递归，改成"用累加器传状态"的尾递归：

c
// 普通递归（非尾调用）
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

// 尾递归（用 acc 累积结果）
int factorial_tail(int n, int acc) {
    if (n <= 1) return acc;
    return factorial_tail(n - 1, n * acc);
}
// 调用：factorial_tail(5, 1)

核心技巧：把"递归回来再计算"改成"递归前把中间结果传进去"。

六、与本站主线衔接 ​

一句话总结 ​

尾递归是"递归调用是最后操作"的写法，编译器 -O2 能把它优化成循环（反汇编里 call 消失），100 万层不栈溢出；普通递归因"调用后还有计算"必须保留栈帧无法优化——写递归时尽量用累加器改成尾递归。