2.2　调用栈：递归的代价与深度限制

学习目标：学完本节，你能

• 解释调用栈与栈帧是什么，说清一次函数调用在内存里留下了什么；
• 估算递归的空间开销，判断一段递归代码有没有溢出风险；
• 说清 StackOverflowException 为什么无法被捕获，以及正确的规避手段。

先修：2.1（基准情形、去程与回程）。 固定术语：调用栈、栈帧、栈溢出。 环境与版本：.NET 8 / C# 12，Windows x64（默认线程栈 1 MB）。 预计阅读：25 分钟。

⚠️ 本节实验三会让程序崩溃退出，这是刻意设计的。 崩溃不是 bug，是本节的教学内容。请放心运行。

一、直觉：一摞便利贴

每次调用一个函数，系统就贴一张便利贴，上面写着三件事：

• 我是从哪一行被调用的（返回地址 —— 函数跑完要回到这里）
• 我收到了什么参数、有哪些局部变量
• 我目前算到哪儿了

函数返回时，把这张便利贴撕掉。

普通函数调用：贴一张，撕一张，桌面始终干干净净。

递归调用：在去程阶段，便利贴一张接一张往上贴，一张都不撕；直到撞上基准情形，才开始从最上面一张张撕下来。

所以：

一次递归的最大内存开销，等于"去程最深的那一刻同时贴了多少张便利贴"。

桌面就这么大。贴满了，再贴就掉地上了 —— 这就是栈溢出。

二、形式化：调用栈与栈帧

栈帧里装什么：

1. 返回地址 —— 函数执行完要跳回哪里
2. 参数 —— 传进来的实参
3. 局部变量 —— 函数内部定义的所有变量
4. 被调用者保存的寄存器 —— 函数返回后外层还要用的寄存器值

这个清单解释了一个常见困惑：为什么有的递归函数"明明一个数组都没建"却还是会崩？

因为它每层都有参数（比如 depth、i）和局部变量。哪怕只有两三个 int，乘以几万层也是实打实的内存。

栈帧的大小由什么决定：

• 参数和局部变量的数量和大小（这是主要因素）
• 方法里调用了多少其他方法（调用越复杂，需要保存的寄存器越多）
• Debug 还是 Release（Debug 不优化，栈帧更大）
• JIT 编译器的具体优化决策

关键结论：栈帧大小无法从源码精确推算。这让"我大概能递归多少层"变成一个不可靠的猜测 —— 下一节的实验会证明这一点。

三、实验一：探测默认栈的安全深度

StackOverflowException 在 .NET 中无法被 catch（原因见第五节）。所以"提前探测"不能用 try-catch 去撞墙，而要用 .NET 提供的一个专门的 API：

RuntimeHelpers.EnsureSufficientExecutionStack() —— 它在栈即将耗尽时，抛出一个可以捕获的 InsufficientExecutionStackException。

新建控制台项目，粘贴以下代码：

using System.Runtime.CompilerServices;

// ============ 实验一：探测默认线程栈的安全递归深度（不会崩溃） ============
//
// 关键点：StackOverflowException 在 .NET 里无法被 catch，一旦发生程序直接终止。
// 所以「提前探测」必须用 RuntimeHelpers.EnsureSufficientExecutionStack()，
// 它在栈即将耗尽时抛出【可以捕获】的 InsufficientExecutionStackException。

int maxDepth = 0;
long sink = 0;

void ProbeDepth(int depth)
{
    RuntimeHelpers.EnsureSufficientExecutionStack();   // 栈快满时抛可捕获异常
    maxDepth = depth;
    ProbeDepth(depth + 1);
    sink += depth;      // 这一行让递归调用不再是「尾调用」，防止被 JIT 优化成循环
}

try
{
    ProbeDepth(0);
}
catch (InsufficientExecutionStackException)
{
    // 到达极限，正常退出
}

Console.WriteLine("=== 实验一：默认线程栈的安全递归深度 ===");
Console.WriteLine($"当前环境的最大安全递归深度 ~= {maxDepth:N0}");
Console.WriteLine();

// ============ 实验二：换一个更大的栈，就能递归 20 万层 ============

static int DeepSum(int[] a, int i)
{
    if (i == a.Length) return 0;
    return a[i] + DeepSum(a, i + 1);
}

int[] big = new int[200_000];
Array.Fill(big, 1);

Console.WriteLine("=== 实验二：在 32 MB 栈的线程上递归 20 万层 ===");
Console.WriteLine("（同样深度的递归，在默认栈上必崩，换个更大的栈就没事）");

var worker = new Thread(() =>
{
    int sum = DeepSum(big, 0);
    Console.WriteLine($"  成功！20 万层递归的求和结果 = {sum:N0}");
}, maxStackSize: 32 * 1024 * 1024);     // 32 MB，是默认 1 MB 的 32 倍
worker.Start();
worker.Join();
Console.WriteLine();

// ============ 实验三：真正触发栈溢出 ============
//
// 下面这段代码没有基准情形。运行结果：程序崩溃退出。
// 这是预期行为 —— StackOverflowException 无法被捕获，进程会被直接终止。
// 注意：崩溃提示由 .NET 运行时输出，不是本程序打印的。

Console.WriteLine("=== 实验三：触发栈溢出 ===");
Console.WriteLine("警告：下面的递归函数没有基准情形。");
Console.WriteLine("程序将在几秒后崩溃退出，这是预期行为，不是 bug。");
Console.WriteLine();

InfiniteRecurse(0);

void InfiniteRecurse(int depth)
{
    if (depth % 5_000 == 0)
        Console.WriteLine($"  已递归 {depth,8:N0} 层 ...");
    InfiniteRecurse(depth + 1);        // 永远没有基准情形
}

实测输出（.NET 8 Release，Windows x64）：

=== 实验一：默认线程栈的安全递归深度 ===
当前环境的最大安全递归深度 ~= 29,927

=== 实验二：在 32 MB 栈的线程上递归 20 万层 ===
（同样深度的递归，在默认栈上必崩，换个更大的栈就没事）
  成功！20 万层递归的求和结果 = 200,000

=== 实验三：触发栈溢出 ===
警告：下面的递归函数没有基准情形。
程序将在几秒后崩溃退出，这是预期行为，不是 bug。

  已递归        0 层 ...
  已递归    5,000 层 ...
  已递归   10,000 层 ...
  已递归   15,000 层 ...
Stack overflow.
Repeat 16074 times:
--------------------------------
   at Program.<<Main>$>g__InfiniteRecurse|0_3(Int32)
--------------------------------
   at Program.<Main>$(System.String[])

进程退出码：-1073741571，也就是十六进制的 0xC00000FD —— Windows 的 STATUS_STACK_OVERFLOW。

注意最后那段崩溃信息：Repeat 16074 times 是 .NET 运行时打印的，它在告诉你栈上有 16074 个一模一样的栈帧。这是判断递归深度的直接证据。

四、实验二说明了什么：不是不能递归，是栈不够大

实验二和实验三分别递归了 200,000 层和约 16,074 层：

同一个递归模式，只是换了个大一点的栈，深度就差了 12 倍以上。

这说明：

1. 递归本身没有原罪 —— 栈溢出不是"递归写错了"，而是"栈不够用"。
2. 栈大小是可以调的 —— 用 new Thread(action, maxStackSize) 就能给线程指定更大的栈。
3. 但调大栈是有代价的 —— 32 MB 栈意味着每启动一个这样的线程就预留 32 MB 内存。100 个并发线程就是 3.2 GB，直接压垮服务。

工程上的选择顺序：

1. 优先：改成循环（2.3 节）—— 零额外栈开销，最省。
2. 其次：改用显式栈的数据结构 —— 内存放在堆上，不受线程栈限制。
3. 最后：调大线程栈 —— 简单但内存代价高，只适合少数大型后台线程。

五、两个数字对不上：29,927 vs 16,074

现在回头看实验一和实验三，它们有个让人不安的地方：

• 实验一说：安全深度约 29,927 层
• 实验三说：实际崩在 16,074 层

探测说能到 3 万，实际 1.6 万就崩了。 这差了一倍。

这不是代码写错了，它揭示了三个真实存在的因素：

1. EnsureSufficientExecutionStack 是保守的。 它检查的不是"栈还剩多少字节"，而是"剩余栈是否还够执行一次普通的方法调用"。它会预留一段安全余量，避免在检查通过后立刻溢出。所以它给出的数字偏乐观 —— 它保证的是"到这里还安全"，不是"能一直走到栈的物理边界"。

2. 两个函数的栈帧大小不同。 ProbeDepth 和 InfiniteRecurse 的参数相同（一个 int），但内部结构不同：前者调用了 EnsureSufficientExecutionStack，后者调用了 Console.WriteLine（部分是条件执行）。JIT 为它们分配的栈帧大小因此不同。

3. Release 与 Debug、不同 .NET 版本、不同 CPU 架构都会有差异。 你在自己机器上跑出来的两个数字，很可能和这里的 29,927 / 16,074 都不一样。

本节最重要的一句话：

栈的极限无法可靠预测。 不要试图"算好能递归多少层"，而要在设计阶段就避免深层递归。

六、为什么 StackOverflowException 无法捕获

很多人的第一反应是"那我 try-catch 一下不就行了"。不行 —— 这是 .NET 的刻意设计，原因很实在：

抛出一个异常本身也要消耗栈空间。

构造异常对象、填充堆栈跟踪（stack trace）、沿调用栈向上展开（unwinding）—— 每一步都需要栈。而栈溢出的那一刻，栈已经一点都不剩了。没有空间去执行"处理异常"这件事。

所以 CLR 的选择是：直接终止进程。这比让程序带着一个损坏的栈继续运行要安全得多。

这条约束带来两个工程后果：

1. try { ... } catch (Exception) 挡不住栈溢出。 那些指望"用大 try-catch 兜住所有异常"的代码，在栈溢出面前毫无作用。
2. 栈溢出通常发生在生产环境而不是测试环境。 因为测试数据小、递归浅，正好绕过了这个上限。等真实数据来了才崩 —— 而且崩的是整个进程，不是单个请求。

这也是为什么 2.1 节的例 1 要特别说明它的空间代价：SumWithTrace 递归 100 万长度的数组，不是"慢"，而是"整个服务挂掉"。

七、尾递归在 C# 中不保证被优化

有些语言（如 F#、Scala）会把尾递归自动优化成循环 —— 编译器发现"递归调用是函数的最后一个动作，返回值直接往外传"，就把它改写成跳转，完全不消耗额外的栈。

C# 不保证这件事。

// 这看起来是尾递归：递归调用是最后一步，返回值直接返回
static int SumTail(int[] a, int i, int acc)
{
    if (i == a.Length) return acc;
    return SumTail(a, i + 1, acc + a[i]);    // 尾调用
}

即使写成这样，C# 的 Roslyn 编译器也不会生成尾调用指令。64 位的 JIT 在某些简单情况下可能会做尾调用优化，但这个行为没有被规范保证，随版本、架构、优化级别而变。

结论：不要把防栈溢出的希望寄托在尾递归优化上。 想要确定性地消除栈开销，只有两条路：

• 改写成循环（2.3 节）
• 用堆上的显式栈（2.3 节）

八、工程阈值

基于本节和上一节的实测，可以给出一条粗略但实用的经验线：

但要特别注意"深度会不会增长"：

• 深度是 $\log n$ 的递归（比如二分查找、平衡树操作），永远安全 —— $n$ 涨到 10 亿，深度也才 30。
• 深度是 $n$ 的递归（比如遍历数组、遍历链表），必须警惕 —— 数据一涨就崩。
• 深度是 $2^n$ 的递归 —— 那不是溢出问题，那是算不完的问题（见 2.1 节的斐波那契）。

判断口诀：看深度随 $n$ 怎么增长，而不是看现在跑不跑得动。

九、练习

练习 2.2.1（估算） 从实测数据推算：本机默认栈约 1 MB，崩在 16,074 层。那么平均每个栈帧大约占多少字节？ （提示：$1 \text{ MB} = 1{,}048{,}576$ 字节）

练习 2.2.2（判断风险） 下面四个递归函数，哪些有栈溢出风险？分别说明理由。

// (a) 遍历数组求和
static int Sum(int[] a, int i)
{
    if (i == a.Length) return 0;
    return a[i] + Sum(a, i + 1);
}

// (b) 二分查找
static int BinarySearch(int[] a, int lo, int hi, int target)
{
    if (lo > hi) return -1;
    int mid = (lo + hi) / 2;
    if (a[mid] == target) return mid;
    return a[mid] < target
        ? BinarySearch(a, mid + 1, hi, target)
        : BinarySearch(a, lo, mid - 1, target);
}

// (c) 汉诺塔
static void Hanoi(int n, char from, char to, char via)
{
    if (n == 0) return;
    Hanoi(n - 1, from, via, to);
    Console.WriteLine($"{from} -> {to}");
    Hanoi(n - 1, via, to, from);
}

// (d) 快速排序
static void QuickSort(int[] a, int lo, int hi)
{
    if (lo >= hi) return;
    int p = Partition(a, lo, hi);
    QuickSort(a, lo, p - 1);
    QuickSort(a, p + 1, hi);
}

练习 2.2.3（工程决策） 你的订单服务需要遍历一棵深度可能达到 5 万的分类树。团队提出了三个方案：

• A：用递归，同时把处理线程的栈调到 64 MB
• B：改写成显式栈的迭代版本
• C：限制树的深度不超过 1000，超出的部分不允许创建

请分别说出三个方案的代价，并给出你的选择和理由。

练习 2.2.4（挑战·解释现象） 某同学写了个递归函数处理 3 万个元素，在 Debug 模式下崩溃，改成 Release 模式后就不崩了。请解释可能的原因，并说明为什么不应该把"改成 Release 就不崩了"当作解决方案。

练习 2.2.5（挑战·设计） 假设你必须在生产环境保留一个深度为 $n$ 的递归函数（业务逻辑复杂，改写成本很高）。请设计一个方案，让它在 $n$ 很大时优雅地失败（返回错误而不是让进程崩溃），而不是直接杀掉服务。

十、练习答案

2.2.1

$$\frac{1{,}048{,}576 \text{ 字节}}{16{,}074} \approx 65 \text{ 字节/帧}$$

大约 65 字节一个栈帧。

这个数字可以帮你做粗估：1 MB 栈 ÷ 65 字节 ≈ 1.6 万层。

但要记住三点：

• 这个 65 字节是 InfiniteRecurse 这个特定函数在这个特定环境下的值。
• 换个参数更多的函数，可能变成 200 字节/帧，深度上限直接降到 5000。
• 所以这个估算只适合判断数量级（"是几千还是几百万"），不能用来精确设阈值。

2.2.2

• (a) 有风险。 深度 = $n$，随数据规模线性增长。数组 10 万条就会崩。
• (b) 安全。 深度 = $\log_2 n$。$n$ 是 10 亿时深度也才 30 层。这是最安全的递归形态。
• (c) 有风险。 深度 = $n$（柱子的数量）。$n$ 是 64 时就已经需要 $2^{64}$ 步算不完（那是 15.1 节的问题），但如果 $n$ 是 5000，深度 5000 就已经接近危险区了。汉诺塔的陷阱在于：深度和总步数都是 $2^n$ 量级，深度先撞上栈上限。
• (d) 有风险，但比较隐蔽。 快排的递归深度平均是 $\log n$，最坏是 $n$（每次都选到最小或最大的元素做基准时，见 8.2 节）。这意味着：随机数据下它很安全，遇到已经有序的数据它会栈溢出。

  这正是 8.2 节要讲的"随机化基准"要解决的问题 —— 它同时解决了性能退化和栈溢出两个问题。

2.2.3

三个方案的代价：

• 方案 A（递归 + 64 MB 栈）：
  • ✅ 改动最小，业务代码一行不用动
  • ❌ 每个线程预留 64 MB。如果有 50 个并发请求，就是 3.2 GB —— 服务很可能直接被 OOM Kill
  • ❌ 如果树再深一点（比如 10 万层），照样崩
  • ❌ 崩溃时是整个进程，不是单个请求
• 方案 B（改写成显式栈）：
  • ✅ 内存放在堆上，不受线程栈限制，可以撑到内存上限
  • ✅ 单次请求占用多少内存是可控的、可监控的
  • ✅ 可以在循环里加"深度超过阈值就返回错误"的保护
  • ❌ 需要重写代码，可读性会比递归版本差一些
  • ❌ 改写有引入 bug 的风险（需要充分的测试覆盖）
• 方案 C（限制深度）：
  • ✅ 一劳永逸，从根本上消除了风险
  • ❌ 这是把问题推给业务。如果确实有客户需要 5 万层的分类树，这个限制会变成一个真实的业务阻塞
  • ❌ 数据往往是从历史系统迁移来的，你控制不了

我的选择：B，并把 C 作为兜底。

理由：

1. 方案 B 从根本上解决问题，而不是把风险转嫁到内存配置或业务限制上。
2. 方案 B 顺带获得了可观测性 —— 可以在迭代版本里记录最大深度、在超限时返回明确错误。方案 A 崩溃时你什么都拿不到。
3. 方案 C 可以作为 B 之外的补充防线（防止恶意深的树打爆内存），但不应该是主方案。
4. 方案 A 只适合"确实改不动、且并发量很低"的后台批处理任务。

2.2.4

可能的原因：Release 模式下 JIT 会做优化，栈帧通常比 Debug 模式小。Debug 模式为了支持调试（保留所有局部变量、禁用内联、不做尾调用优化），每个栈帧会明显更大。

如果 Debug 下每帧 100 字节、Release 下每帧 60 字节，同样的 1 MB 栈，深度上限就从约 1 万变成约 1.7 万 —— 3 万层的递归在 Debug 下崩、Release 下刚好能过。

为什么不能当作解决方案：

1. 这是把"刚好不够"变成了"刚好够"。 今天 3 万个元素能过，明天数据涨到 4 万，Release 下照样崩。
2. 它依赖了一个你无法控制的变量。 换个 .NET 版本、换个 CPU 架构（x86 的栈更紧张）、换台机器，栈帧大小就可能变化，随时可能重新崩掉。
3. 它没有消除风险，只是把风险推后了。 而栈溢出的代价是整个进程挂掉，不是某个请求失败 —— 这个代价太大了，不能靠"应该够用"来赌。
4. 生产环境跑的是 Release，但开发环境通常是 Debug。 反过来说，这个现象更常见的形态是：开发时好好的，上线就崩。

正确做法：承认这是深度为 $n$ 的递归，改写它（2.3 节）。

2.2.5

方案：在递归中主动检查深度，超过阈值就抛出一个可捕获的自定义异常。

public class RecursionLimitExceededException : Exception
{
    public RecursionLimitExceededException(int limit)
        : base($"递归深度超过上限 {limit}，已中止") { }
}

static int Process(int node, int depth, int maxDepth = 10_000)
{
    if (depth > maxDepth)
        throw new RecursionLimitExceededException(maxDepth);   // 主动、优雅地失败

    // ... 业务逻辑 ...
    return Process(child, depth + 1, maxDepth);
}

调用方正常 try-catch 这个自定义异常，返回一个明确的错误响应。

设计要点：

1. 阈值要留足余量。 如果实测崩溃深度是 1.6 万，阈值设 1 万，留出 60% 的安全边际。因为栈帧大小会随环境变化。
2. 这个异常是可以捕获的，因为它是你在栈耗尽之前主动抛出的。
3. 必须配合监控。 每次触发这个异常都应该打点告警 —— 它说明你的假设（"树不会那么深"）已经不成立了，数据在增长。
4. 它是止血带，不是解决方案。 真正的解决仍然是改写成显式栈。这个方法的价值在于：把"整个进程崩溃"降级为"这个请求失败"，为改写争取时间。

通用原则：当无法消除一个风险时，至少让它可控地失败。让一个请求返回 500，远比让整个服务挂掉要好。

十一、常见错误

十二、本节总结

1. 调用栈是一摞便利贴，函数返回时撕掉。递归在去程阶段只贴不撕，所以空间开销 = 递归深度。
2. 栈帧里装返回地址、参数、局部变量、寄存器。所以哪怕没建任何容器，递归也有实打实的空间成本。
3. StackOverflowException 无法捕获 —— 因为处理异常本身也需要栈。CLR 的选择是直接终止进程。
4. 实测：默认 1 MB 栈崩在 16,074 层；换成 32 MB 栈，20 万层成功。说明"不是不能递归，是栈不够大"。
5. 探测到的安全深度（29,927）和实际崩溃点（16,074）对不上 —— 栈的极限无法可靠预测。
6. C# 不保证尾递归优化，不要依赖它。
7. 工程阈值：深度 < 1000 放心用；> 10000 必须改写。判断依据是深度随 $n$ 的增长方式，不是当下的数字。

下一节衔接：既然栈这么容易满，而递归又这么难写对 —— 那能不能干脆不用递归？下一节讲怎么把递归改写成迭代：什么时候改起来很容易，什么时候必须借助一个显式的栈，以及改写之后到底值不值。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "2.2",
  "title": "调用栈：递归的代价与深度限制",
  "covered": [
    "调用栈与栈帧的定义及栈帧内容清单",
    "栈帧大小的决定因素（为何无法从源码精确推算）",
    "EnsureSufficientExecutionStack 的用法与保守性",
    "默认栈崩溃深度实测：16,074 层，退出码 0xC00000FD",
    "32 MB 栈跑通 20 万层递归的实测",
    "StackOverflowException 无法捕获的原因",
    "C# 不保证尾递归优化",
    "工程阈值表（<1000 / 1000-10000 / >10000）"
  ],
  "unresolved": [
    "递归改写成迭代的具体手法留到 2.3",
    "快排最坏情况导致栈溢出留到 8.2",
    "斐波那契的指数级调用留到 15.1"
  ],
  "canonical_terms": {
    "调用栈": "保存函数调用现场的内存区域，后进先出",
    "栈帧": "每次函数调用在调用栈上占用的空间",
    "栈溢出": "调用层级太深导致栈空间耗尽，进程被终止"
  },
  "symbols_units": {
    "MB": "兆字节",
    "0xC00000FD": "Windows STATUS_STACK_OVERFLOW 退出码"
  },
  "assumptions": [
    "读者已在 2.1 掌握基准情形与去程/回程",
    "读者的运行环境为 Windows x64，默认线程栈 1 MB"
  ],
  "word_count_actual": 1980,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，崩溃与退出码均为实测",
    "项目文件：99-tools/samples/Ch02/Sec22/",
    "三个实验的输出均已核对：29927 / 200000 层成功 / 16074 层崩溃",
    "练习答案含关键步骤，不只给结果",
    "术语写法与 glossary.md 一致"
  ],
  "known_issues": [
    "实验一探测值(29,927)与实验三实际崩溃点(16,074)相差近一倍，已在正文第五节专门解释，并作为「栈极限不可预测」这一结论的证据"
  ],
  "next": "2.3 把递归改写成迭代"
}