栈在递归中的应用

2026 大纲 三（六）栈、队列和数组的应用（另见《括号匹配》《表达式求值》《双端队列》）。

递归为什么天然配栈

递归就是函数直接或间接调用自身。写对一个递归只需要两件东西：

• 递归表达式：把原问题转化为同类型、但规模更小的子问题；
• 边界条件（递归出口）：小到不需要再递归就能直接求解的那一档。

⚠️ 缺边界等于无限递归，边界写错也一样。 比如写 if (n == 1) 却传进来 $n=0$，就会一路递归下去直到耗尽栈空间。

真正要理解的是它为什么必须靠栈执行。在一个函数里调用另一个函数，系统在执行被调函数之前必须先做三件事：保存返回地址（记住回到哪条指令）、保存调用方的现场（寄存器、局部变量）、传递实参并为被调函数分配它自己的局部变量空间。返回时再反过来恢复。

这一套"后调用的先返回"的次序，恰好就是 LIFO——所以承载它的数据结构只能是栈，即递归工作栈。每进入一层递归压入一条工作记录，每退出一层弹出一条，当前正在执行的那层位于栈顶。

// 典型例子：阶乘
int Factorial(int n) {
    if (n == 0 || n == 1)          // 边界条件：递归出口
        return 1;
    return n * Factorial(n - 1);   // 递归表达式：规模减 1
}

空间复杂度 = 最大递归深度

递归工作栈就是递归算法的辅助空间：

$$S(n)=O(f(n)),f(n)=\text{递归工作栈中工作记录个数的最大值}$$

🔴 "工作记录个数的最大值"就是最大递归深度（同时存在的栈帧数），不是调用的总次数。 根本原因是调用树按深度优先展开——任何时刻只有从根到当前结点这一条路径上的栈帧同时存在，兄弟子树的栈帧早已弹出。

这条差别可以大到指数级：Fibonacci 的朴素递归调用了 $O(2^n)$ 次，深度却只有 $n-1$，空间是 $O(n)$；汉诺塔调用 $2^n-1$ 次，深度同样只有 $n$。这一条是本篇迁移到树、图、排序各章时用得最多的结论：

递归	调用总次数	最大递归深度	空间复杂度
阶乘 Fact(n)	$n$	$n$	$O(n)$
Fibonacci 朴素递归	$O(2^n)$	$n-1$	$O(n)$
汉诺塔 Hanoi(n)	$2^n-1$	$n$	$O(n)$
二叉树的递归遍历	—	树高 $h$	$O(h)$；最坏单支树 $O(n)$，平衡时 $O(\log n)$
图的 DFS	—	搜索路径最大长度	最坏 $O(|V|)$
快速排序	—	平均 $O(\log n)$、最坏 $O(n)$	同左
归并排序	—	恒为 $O(\log n)$	$O(n)$——还要 $O(n)$ 的辅助数组

看到"某递归算法空间复杂度是多少"，先问递归深度，再问有没有额外的辅助数组。归并排序那一行就是被辅助数组顶上去的。

栈里每一层存的那条工作记录（教材也叫"活动记录"）含三样东西，而且每层必须各存一份：返回地址（本层执行完回到哪里）、局部变量（各层的同名变量是互相独立的副本）、实参副本（每层的 $n$ 不同，共用一份就全乱了）。理解了这三样，就能解释为什么递归的空间开销与深度成正比——每深一层，就多压一整份。

活动记录的图示与一次完整调用的跟踪（想弄清机制就展开）

图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图3.11 函数递归调用时的活动记录，p105

图的左半边说明"调用—返回"是一对成对出现的跳转：控制流从调用点跳进被调函数， 返回时必须回到调用点的下一条指令——这个地址不记下来就回不去。 右半边是一条活动记录（严蔚敏教材称"工作记录"）的三个组成部分：

组成	作用	为什么必须每层一份
返回地址	本层执行完回到哪里	不同层的调用点不同（可能同一处，但返回后要继续的上下文不同）
局部变量	本层自己的临时数据	各层的同名局部变量是互相独立的副本，改一层不影响另一层
实参副本	本次调用传入的参数值	每层的 $n$ 不同，共用一份就全乱了

系统为整个递归函数的运行期设立一个递归工作栈： 每进入一层递归就产生一个新的工作记录压入栈顶，每退出一层就从栈顶弹出一个。 当前正在执行的那一层，其工作记录必定位于栈顶，称为活动记录。

跟踪一次完整的递归（调用 Factorial(4)，约定主函数为第 0 层）：

调用过程（逐层压栈）              返回过程（逐层弹栈）
┌───────────────┐                ┌───────────────────┐
│ Fact(1) 第4层 │ ← 栈顶         │ return 1          │ → 弹出
├───────────────┤                ├───────────────────┤
│ Fact(2) 第3层 │                │ return 2*1  = 2   │ → 弹出
├───────────────┤                ├───────────────────┤
│ Fact(3) 第2层 │                │ return 3*2  = 6   │ → 弹出
├───────────────┤                ├───────────────────┤
│ Fact(4) 第1层 │ ← 栈底         │ return 4*6  = 24  │ → 弹出
└───────────────┘                └───────────────────┘
                                  最终结果：24

最大栈深是 4（$n$ 层），任意时刻栈中最多同时存在 4 条工作记录。

严蔚敏教材把可用"分治法"递归求解的问题条件写成三条：（1） 能把问题转变成一个新问题， 新问题与原问题解法相同或类同，只是处理对象更小且变化有规律；（2） 通过这种转化能使问题简化； （3） 必须有一个明确的递归出口（递归的边界）。

时间复杂度：列方程，展开到边界

递归的时间复杂度没有现成公式可背，做法固定三步：列递归方程 → 逐层展开到边界 → 数一共展开了几层。

递归	递归方程	展开后	时间复杂度
阶乘 Fact(n)	$T(n)=T(n-1)+C$	展开 $n$ 层，每层 $O(1)$	$O(n)$
Fibonacci 朴素递归	$T(n)=T(n-1)+T(n-2)+C$	调用树每层结点数约翻倍，共 $n$ 层	$O(2^n)$
汉诺塔 Hanoi(n)	$T(n)=2T(n-1)+C$	$T(n)=2^{n}C-C$，移动次数 $2^n-1$	$O(2^n)$

中间那一行值得单独说明：Fibonacci 递归慢，原因是"重复的子问题"，不是"函数调用"本身。 同一个 $F(3)$ 在调用树里被算了两次、$F(2)$ 被算了三次，结点总数才涨成指数级。把中间结果存下来（记忆化），或者干脆自底向上迭代，都能降到 $O(n)$——这说明开销来自重复计算，与递归这个形式无关。

三个递归方程的完整展开过程（想会推不想背就展开）

把"一次调用自身以外的工作量"记作常数 $C$，就能列出递归方程并逐层展开。以阶乘为例：

$$T(n)=C+T(n-1)$$

用 $n-1$ 代入自身：$T(n-1)=C+T(n-2)$，回代得 $T(n)=2C+T(n-2)$； 继续得 $T(n)=3C+T(n-3)$；一般地 $T(n)=iC+T(n-i)$。取 $i=n$：

$$T(n)=nC+T(0)=nC+D⟹T(n)=O(n)$$

这就是递归时间复杂度的标准做法：列方程 → 展开到边界 → 数一共展开了几层。

递归	递归方程	展开后	时间复杂度
阶乘 Fact(n)	$T(n)=T(n-1)+C$	展开 $n$ 层，每层 $O(1)$	$O(n)$
Fibonacci 朴素递归	$T(n)=T(n-1)+T(n-2)+C$	调用树每层结点数约翻倍，共 $n$ 层	$O(2^n)$
汉诺塔 Hanoi(n)	$T(n)=2T(n-1)+C$	$T(n)=2^{n}C-C$，移动次数 $2^n-1$	$O(2^n)$

汉诺塔的递归结构值得单独看一眼，因为它是"一次调用里有两处递归"的最小例子：

// 把塔座 A 上的 n 个圆盘按规则搬到 C 上，B 做辅助塔
void Hanoi(int n, char A, char B, char C) {
    if (n == 1) {
        move(A, 1, C);              // 边界：直接把 1 号盘从 A 移到 C
    } else {
        Hanoi(n - 1, A, C, B);      // ① 把上面 n-1 个从 A 搬到 B，C 做辅助
        move(A, n, C);              // ② 把最大的第 n 个从 A 搬到 C
        Hanoi(n - 1, B, A, C);      // ③ 把那 n-1 个从 B 搬到 C，A 做辅助
    }
}

• 移动次数 $M(n)=2M(n-1)+1$，$M(1)=1$。逐层展开： $M(n)=2^{n-1}M(1)+(2^{n-2}+\cdots +2+1)=2^{n-1}+2^{n-1}-1=2^n-1$。 时间复杂度 $O(2^n)$；
• 递归深度：① 和 ③ 是先后执行的，不是同时——③ 开始时 ① 的所有栈帧早已弹出。 所以任意时刻栈中只有从根到当前结点这一条路径，深度为 $n$，空间复杂度 $O(n)$。

这正是"调用次数 $\ne$ 递归深度"的最佳例证：调用次数 $2^n-1$ 是指数级， 空间却只有线性。理解这一点，后面分析树与图的递归算法就不会再把两者混起来。

Fibonacci 慢的原因不是"递归本身慢"，而是同一个子问题被反复求解：

Fibonacci(5) 的递归调用树——F(3) 算了 2 次，F(2) 算了 3 次：

           F(5)
          /    \
       F(4)    F(3)
       / \     / \
    F(3) F(2) F(2) F(1)
    / \
 F(2) F(1)

调用树的结点总数是指数级，而用循环自底向上算只需 $O(n)$——差距全在重复计算上。 把中间结果存下来（记忆化）同样能降到 $O(n)$，这说明递归的开销来自"重复的子问题"， 不是来自"函数调用"本身。

递归转非递归：判据是"待返回的状态有没有界"

转的理由有三条：避免栈溢出（系统栈容量有限，深度到十万级就会崩）、消除重复计算（如 Fibonacci，改成迭代后从 $O(2^n)$ 降到 $O(n)$）、减少调用开销（每次调用都要压栈、传参、跳转）。

能不能只用循环改写，判据只有一条：待返回的状态个数是否有界。

• 尾递归 / 线性递归：每层只有一处递归调用、状态能用有限个变量携带，可以直接改成循环；
• 分支递归（一次调用里有两处以上递归，如树的遍历、图的 DFS）："回到上一层继续处理右子树"这件事要记住一条任意深度的路径，有限个变量装不下，必须用显式栈。

🔴 递归转非递归不会降低时间复杂度。 显式栈只是把系统栈搬到了手里，该做的操作一次不少——它省的是函数调用开销与栈帧空间，不是算法本身的量级。只有在顺带消除了重复子问题时（如 Fibonacci 改迭代），时间才会真的降下来。两者是分别降的，别混作一谈。

显式栈模板与迭代改写的完整代码（要写非递归实现时展开）

方式一：用显式栈模拟（通用）。 用一个显式栈保存"待处理的状态"， 手动完成系统栈本来会做的事。模板（以二叉树中序遍历为例）：

// 中序遍历的非递归实现：显式栈模拟系统栈
void InOrder(BiTree T) {
    BiTree stack[MaxSize];  int top = -1;   // 显式栈
    BiTree p = T;
    while (p != NULL || top != -1) {        // 还有结点没访问，或栈里还有待返回的结点
        if (p != NULL) {
            stack[++top] = p;               // 相当于"压入本层工作记录"
            p = p->lchild;                  // 相当于"递归进入左子树"
        } else {
            p = stack[top--];               // 相当于"左子树返回，弹出本层记录"
            visit(p);                       // 访问根
            p = p->rchild;                  // 相当于"递归进入右子树"
        }
    }
}

对应关系值得记住：显式栈里存的是"还没处理完的结点"，正对应系统栈里"还没返回的层"； stack[++top] = p 对应压入工作记录，p = stack[top--] 对应返回上一层。 手写的栈只存必要状态（这里只有一个结点指针），比系统栈的完整工作记录省得多—— 这也是显式栈版本通常更快的原因。

再看一个"用栈模拟"的最小写法（阶乘本身不需要栈，这里只为看清模拟过程）：

// 用显式栈模拟递归实现阶乘（示意用途）
int Factorial_NonRecursive(int n) {
    int stack[100], top = -1;
    int result = 1;
    while (n > 1)               // 入栈阶段：模拟逐层递归调用
        stack[++top] = n--;
    while (top >= 0)            // 出栈阶段：模拟逐层递归返回
        result *= stack[top--];
    return result;
}

代入 $n=4$：入栈 4、3、2（n 变为 1），出栈依次乘得 $2\times 3\times 4=24$ ✓； $n=1$ 或 $n=0$ 时两个循环都不执行，返回 1 ✓（与 $0!=1!=1$ 一致）。

方式二：直接改写成迭代。 适用于尾递归和线性递归——递归调用的结果不再参与后续运算， 或每层只有一处递归调用且状态可以用有限个变量携带。

// Fibonacci：迭代替代递归，O(2^n) → O(n) 时间，O(n) → O(1) 空间
int Fibonacci(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;   // c = F(i)
        a = b;       // a = F(i-1)
        b = c;       // b = F(i)
    }
    return b;
}

这次改写同时降了时间（消除重复子问题）和空间（不再需要 $O(n)$ 的栈帧， 只用 3 个变量）。注意两者是分别降的：显式栈模拟只降常数和栈溢出风险， 不降渐进时间复杂度；只有消除了重复子问题才降时间。

不是所有递归都能只用循环替代。 树的遍历、图的 DFS 这类递归中， "回到上一层继续处理右子树"这件事必须记住一个任意深度的路径， 有限个变量装不下，必须用显式栈。

考点速记

三条会被反复调用的结论：

1. 空间复杂度 = 最大递归深度，不是调用总次数——这一条在树、图、排序各章会反复用到。
2. 时间复杂度靠解递归方程得到，不靠记忆；调用树的结点数与深度可以差指数级。
3. 分支递归必须用显式栈才能消除，尾递归 / 线性递归才可以直接改成循环；而转写本身不降时间复杂度。

这一节在真题里被考过的形式（题目挂在栈的应用几篇下）：

• 给一段递归程序，问运行到某一刻栈里自栈底到栈顶依次是什么。答法是照着调用链写：主函数在最底下，然后是第一次递归调用、第二次……最后一次调用（也就是最深那层）在栈顶。留意题目问的是"自栈底到栈顶"还是反过来，两种问法的答案互为逆序，而选项里通常两个都摆着。
• 关于栈与递归的命题判断，典型错项见下面的易错。

易错："非递归重写递归程序必须使用栈"是错的。 尾递归、单向递推（阶乘、斐波那契）都能改写成纯循环；只有分支递归才必须显式用栈。

易错：把"调用次数"当成"递归深度"。 汉诺塔调用 $2^n-1$ 次，栈深只有 $n$——因为两处递归是先后执行的，第二处开始时第一处的栈帧早已弹光。

易错：把"栈溢出"和"栈空下溢"混为一谈。 前者是递归太深、系统栈空间耗尽；后者是对空栈执行 Pop 这个逻辑错误。

教材出处

• 递归的定义、阶乘与 Fibonacci 的递归程序、"分治法"求解递归问题的三个条件与一般形式： 严蔚敏《数据结构（C 语言版）》（第 2 版）p62–p63「3.4.1 采用递归算法解决的问题」
• "数据结构是递归的"（链表结点定义中又用到自身，故链表是递归的数据结构）：同书 p63
• 3.4.2 递归过程与递归工作栈：调用另一个函数前系统需先完成的三件事； "递归工作栈"的设立、工作记录包含所有实参、所有局部变量以及上一层的返回地址、 栈顶的工作记录称为"活动记录"、递归层次的定义：同书 p65–p66
• 汉诺塔递归算法 3.10：同书 p65
• 递归算法的时间复杂度分析（$T(n)=C+T(n-1)$ 的逐层展开，得 $T(n)=O(n)$； Fibonacci 与汉诺塔均为 $O(2^n)$）与空间复杂度分析 （"分析递归算法的空间复杂度需要分析工作栈的大小"，三例均为 $O(n)$）：同书 p68
• 3.4.4 利用栈将递归转换为非递归的方法：同书 p68 起
• 图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版） 图3.11 函数递归调用时的活动记录，p105

相关知识

顺序栈、链栈（显式栈模拟时的具体实现）｜ 表达式求值（递归下降解析就是"隐式用系统栈"）｜ 算法的基本概念与复杂度分析（时间/空间复杂度的定义与记号）｜ 二叉树的先序遍历、中序遍历、后序遍历（显式栈模板的直接应用）｜ 图的深度优先搜索｜快速排序、归并排序

相关文章

• 栈和队列基本概念
• 顺序栈
• 共享栈
• 链栈
• 链式队列
• 循环队列
• 双端队列
• 应用：括号匹配
• 应用：表达式求值
• 多维数组的存储
• 特殊矩阵的压缩存储

真题练习

相关真题（12题）

2026Q4210分2025Q22分2024Q22分2020Q22分2018Q12分2017Q22分2015Q12分2014Q22分2013Q22分2012Q22分2010Q12分2009Q22分