递归 DFS 爆栈：一条 10 万个点的链，g++ 下多 5000 个点就段错误

树上的题十有八九从一个递归 DFS 开始：从根出发，先算完所有孩子，再把结果合到自己身上。代码短，也好证明。问题出在树的形状上。题目说「n 不超过 10⁵，保证是一棵树」，并没有说这棵树是平衡的。出题人只要给一条 1-2-3-…-n 的链，递归就有 n 层深。

这篇用「求每个点的子树大小」这一个任务，量出递归在默认栈上能走多深，再把它改成显式栈。改写不是换一种算法，而是把编译器替你保存的东西自己保存一遍。

栈溢出在 Linux 上通常表现为 Segmentation fault，和空指针、数组越界的报错一模一样，单看报错分不出是哪一种。区分的办法有两个：用 -fsanitize=address 重新编译，AddressSanitizer 会直接报告 stack-overflow；或者逐步缩短链的长度，如果存在一个明确的分界，超过就崩、不到就正常，基本可以确定是递归深度的问题。

一个刚好卡在边上的数字

递归版是这样的，图用邻接表存，parent 用来避免走回头路：

void dfs(int u, int parent) {
    sz[u] = 1;
    for (int v : g[u])
        if (v != parent) { dfs(v, u); sz[u] += sz[v]; }
}

输入是一条链：点 0 连点 1，点 1 连点 2，一直到 n-1。在 x86-64 Linux、默认 8 MB 栈（ulimit -s 为 8192）下，对 n 取了几个值：

再用二分法找最大能跑通的 n，g++ 两档都在 10.46 万附近，clang -O0 约 13.06 万，clang -O2 约 17.42 万。8 MB 除以这些深度，每层分别约占 80、64、48 字节。

n = 10⁵ 的数据在 g++ 下能过，只剩 4% 的余量。这就是这类 bug 难缠的地方：本地用题目上限造一条链测过，没事；评测机的栈小一点、编译选项多一个调试开关、或者函数里多了一个局部变量，就越界。g++ 在 -O0 和 -O2 下深度相同，说明这里的栈帧主要不是局部变量撑起来的，优化帮不上忙。

每一层栈里放了什么

一层 dfs 的栈帧大致包含：返回地址（8 字节），被调用者要保存的寄存器，参数 u、parent，以及 range-for 循环用的迭代器（指向 g[u] 当前位置和末尾的两个指针，各 8 字节）。最后还要按 16 字节对齐。

真正决定「递归回来以后从哪继续」的，只有三样东西：

1. 当前在处理哪个点 u；
2. 它的父亲是谁（用来跳过回头的边）；
3. 它的邻接表已经看到第几条边。

第 3 样平时看不见，它藏在 range-for 的迭代器里。递归调用 dfs(v, u) 返回时，循环从迭代器的下一个位置继续，这就是「回到父亲身上接着看下一个孩子」。

把这三样搬进 vector

显式栈的一帧就存这三样：

struct Frame {
    int u, parent;
    size_t next_edge;
};

主循环每次看栈顶：

• 如果栈顶的点还有没看过的边，取出下一条，next_edge 加一。是父亲就跳过；否则把孩子压栈。这对应递归里的「调用」。
• 如果栈顶的点边都看完了，弹出，把自己的子树大小加到父亲上。这对应递归里的「返回」以及返回后那句 sz[u] += sz[v]。

这样写出来的是后序遍历：一个点在所有孩子都弹出之后才弹出，弹出时它的子树大小正好算完。

有一个只在 C++ 里会踩的坑。循环开头取了 Frame& f = st.back()，压栈之后 vector 可能扩容，f 就成了悬空引用。程序里压栈后立刻进入下一轮循环，不再碰 f，弹栈的分支则先把 u、parent 复制出来再 pop_back。如果你把引用换成下标，比如 st[top]，这个问题就不存在，代价是多写几个字。

逐步状态：6 个点的树

用一棵小树看栈的变化：1 的孩子是 2 和 3，2 的孩子是 4 和 5，3 的孩子是 6。

        1
       / \
      2   3
     / \   \
    4   5   6

Playground 程序对这棵树的实际输出整理如下，栈从左到右是栈底到栈顶：

最大栈深是 3，等于树高。这和递归版的调用深度完全一致，差别在于这个「栈」是堆上的一个 vector，每帧 16 字节（int、int、size_t），想放多深取决于内存，不取决于 ulimit。

在这里跑

程序读点数 n 和 n-1 条边，以 1 为根求每个点的子树大小。点数不超过 12 时打印每一步的栈；同时检查输入是否真的是一棵连通的树。

g++ 14.2 和 clang++ 19.1 加 -O2 -Wall -Wextra 编译无警告，默认 stdin 下输出相同，前 12 行就是上面那张表，最后是：

max stack depth=3
size[1]=6
size[2]=3
size[3]=2
size[4]=1
size[5]=1
size[6]=1

本机另外喂了一条 20 万个点的链（1-2、2-3……），这在递归版上必然越界。迭代版输出 max stack depth=200000、size[1]=200000 size[200000]=1，g++ 版本总耗时约 0.08 秒。这份输入有 20 万行，不适合贴进浏览器的 stdin 框，可以在本地用脚本生成。

输入不是树时程序会拒绝：4 个点配 1 2、2 3、3 1 三条边（有环），stderr 是 Not a tree: node 1 reached twice.，退出码 1。

不改代码的几种办法，各有代价

调大栈。 在 shell 里 ulimit -s 131072 把主线程栈调到 128 MB 后，同一份递归版在 g++ -O2 下跑通了 100 万个点的链；调到 64 MB 时，100 万仍然段错误，因为 64 MB 除以每层 80 字节约 84 万层。这个办法在本机有效，在评测机上通常无效，你改不了它的 ulimit。

开一个大栈的线程。 用 pthread_attr_setstacksize 给新线程 256 MB 栈，在线程里调递归 DFS，本机 g++ 和 clang++ 都跑通了 100 万个点的链。它不依赖外部设置，比赛里有人这么用。缺点是多了平台相关的代码，浏览器的 WASM 环境里也没有 pthread 可用。

换一种遍历顺序。 有些问题不需要后序：只求每个点的深度，BFS 一层层推就行，队列在堆上。求子树大小也可以先 BFS 得到一个顺序，再倒序把每个点加到父亲上，因为倒序时孩子一定先于父亲被处理。这比显式栈更短，但只适用于「每个点只依赖孩子的结果」这种简单的后序。需要在进入和离开一个点时各做一件事（比如欧拉序、Tarjan 求割点），还是显式栈更直接。

什么时候不用改

递归深度如果有保证，就不必改。平衡结构上的递归深度是 log n：线段树 在 10⁶ 个元素上也只有 20 层左右，没有人会把它改成迭代来防爆栈。分治排序在随机基准下也是期望 log n 层，但 快排在已排序数组上取 a[lo] 当基准 那篇演示过，基准一选错，深度就变成 n，和这里的链是同一种形状。

判断标准只有一个：递归深度由输入的什么决定？如果答案是「由输入数据的形状决定，而形状不受控制」，就该用显式栈，或者至少在本地用最坏形状的数据测一次。所有代码都能贴进 Playground 运行；浏览器里的 WASM 运行时自有一套栈大小，和 Linux 的 8 MB 不是一回事——那边的上限未在本页标定，用小一些的链去试就能看到它在哪里停下。

改成显式栈之后，最容易出错的是后序处理：一个点第一次出栈时，它的孩子还没有算完，不能马上把它的子树大小加到父亲身上。本文的写法用一个记录「下一条要处理的边」的下标，来区分第一次访问和最后一次离开。改完以后，先用若干棵小规模的随机树把递归版和迭代版的输出逐个比较，结果一致再换到大数据上。