Appearance
栈在递归中的应用
核心思想
什么是递归
一个函数/过程/数据结构的定义中又直接或间接地引用了自身，就称为递归。递归需要满足两个条件：
- 递归表达式（递归体）：问题可以分解为规模更小的同类子问题
- 边界条件（递归出口）：存在不需要递归就能直接求解的最小规模
c
// 典型例子：阶乘
int Factorial(int n) {
if (n == 0 || n == 1) // 边界条件
return 1;
return n * Factorial(n - 1); // 递归表达式
}递归的工作原理：系统栈
递归调用的执行依赖于系统内部的递归工作栈。每次发生函数调用时，系统会在栈中分配一个栈帧（也叫活动记录），用于保存：
- 返回地址：调用结束后回到哪里继续执行
- 局部变量：本次调用的局部数据
- 参数值：本次调用传入的实参
调用 Factorial(4) 时的栈变化：
调用过程（入栈）： 返回过程（出栈）：
┌─────────────┐ ┌─────────────┐
│ Factorial(1) │ ← 栈顶 │ return 1 │ → 弹出
├─────────────┤ ├─────────────┤
│ Factorial(2) │ │ return 2*1 │ → 弹出
├─────────────┤ ├─────────────┤
│ Factorial(3) │ │ return 3*2 │ → 弹出
├─────────────┤ ├─────────────┤
│ Factorial(4) │ ← 栈底 │ return 4*6 │ → 弹出
└─────────────┘ └─────────────┘
最终结果：24递归的效率问题
递归简洁但不一定高效：
| 问题 | 原因 | 示例 |
|---|---|---|
| 栈溢出 | 递归深度过大，栈空间耗尽 | 递归求 Fibonacci(10000) |
| 重复计算 | 子问题被反复求解 | Fibonacci 的树形递归 |
Fibonacci(5) 的递归调用树——F(2) 被计算了 3 次，F(3) 被计算了 2 次：
F(5)
/ \
F(4) F(3)
/ \ / \
F(3) F(2) F(2) F(1)
/ \
F(2) F(1)递归转非递归
消除递归有两种方式：
方式一：用栈模拟递归过程
适合无法用简单迭代替代的递归（如树的遍历）。用一个显式栈保存"待处理的状态"，手动模拟系统栈的入栈/出栈过程。
c
// 用显式栈模拟递归实现阶乘（示意）
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;
}方式二：直接用迭代（循环）替代
适合尾递归或有明确迭代模式的递归。Fibonacci 就适合用循环：
c
// 迭代替代递归
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;
a = b;
b = c;
}
return b;
}考研高频考点
- ⭐ 递归的执行过程依赖系统栈（选择题/概念题）
- ⭐ 递归调用时栈中保存的内容：返回地址、局部变量、参数（选择题）
- ⭐ 递归算法的空间复杂度 = 递归调用的最大深度（分析题）
- 递归的两个要素：递归表达式 + 边界条件
- Fibonacci 递归的重复计算问题（选择题/简答题）
- 递归转非递归的两种方式
易错：递归算法的空间复杂度不是调用总次数，而是同时存在的最大栈帧数（即递归深度）。Fibonacci(n) 的调用总次数是指数级，但递归深度只有 O(n)，所以空间复杂度是 O(n)。
易错：不是所有递归都能简单地用循环替代。树的遍历、图的 DFS 等递归，转非递归时必须用显式栈模拟调用过程，不能只用简单循环。