数据结构：递归（Recursion）
目录
示例1：先打印，再递归
示例2：先递归，再打印
递归的两个阶段
递归是如何使用栈内存
复杂度分析
递归中的静态变量
内存结构图解
递归：函数调用自己 + 必须有判断条件来使递归继续或停止
我们现在通过这两个示例代码，用“递归调用树”的方式，一步步直观分析，并进行对比。
示例1：先打印，再递归
void fun(int x)
{if(x > 0){printf("%d", x);fun(x - 1);}
}int main()
{int x = 3;fun(x);
}
执行流程（调用栈顺序）
main -> fun(3)|--> print 3--> fun(2)|--> print 2--> fun(1)|--> print 1--> fun(0) -> 终止
调用树结构
fun(3)└── print 3└── fun(2)└── print 2└── fun(1)└── print 1└── fun(0) [结束]
输出结果
321
示例2：先递归，再打印
void fun(int x)
{if(x > 0){fun(x - 1);printf("%d", x);}
}int main()
{int x = 3;fun(x);
}
执行流程（调用栈顺序）
main -> fun(3)|--> fun(2)|--> fun(1)|--> fun(0) [终止]<-- print 1<-- print 2<-- print 3
调用树结构
fun(3)└── fun(2)└── fun(1)└── fun(0) [结束]└── print 1└── print 2└── print 3
输出结果
123
递归的两个阶段
递归包含两个阶段：calling（上升阶段 / Ascending）和returning（下降阶段 / Descending）
void fun(int x)
{if(x > 0){// calling，又叫 Ascendingfun(x - 1); // 如果这里有其他操作（例如 fun(x-1)*2），则属于 returning// returning，又叫 Descending}
}
我们假设执行 fun(3)：
🌿 调用过程（Calling / Ascending）：
fun(3)
└── fun(2)└── fun(1)└── fun(0) // 到这里终止（因为 x > 0 不成立）
这部分就是不断往下递归调用自己的过程，称为“上升阶段”，因为递归在“深入栈底”，一层一层地压入调用栈中。
在这个阶段，“程序在挖坑”，但并没有开始“填坑”。
🌀 返回过程（Returning / Descending）：
当 fun(0) 终止后，每一层函数从栈中返回：
fun(0) 返回到 fun(1)
→ fun(1) 返回到 fun(2)
→ fun(2) 返回到 fun(3)
→ fun(3) 返回到 main
这个阶段称为“下降阶段”，也可以叫returning，因为每一次递归调用返回时都会执行“fun(x - 1)”后面的语句（如果有的话）。
递归是如何使用栈内存
在 C 语言中，每一次函数调用都会在内存中开辟一个栈帧（Stack Frame），用来保存该函数的局部变量、参数、返回地址等。
当你调用递归函数 fun(x) 时，每次调用都会压入（push）一个新的栈帧，等函数返回后再弹出（pop）这个栈帧。
我们以下面的代码为例：
void fun(int x)
{if(x > 0){printf("%d", x);fun(x - 1);}
}
✅ 第一步：main() 调用 fun(3)
+------------------------+ ← 栈顶（最新压栈）
| fun(x=3) 的栈帧 | ← 保存参数 x=3，返回地址
+------------------------+
| main() 的栈帧 |
+------------------------+
✅ 第二步：进入 fun(2)（x=2）
+------------------------+
| fun(x=2) 的栈帧 |
+------------------------+
| fun(x=3) 的栈帧 |
+------------------------+
| main() 的栈帧 |
+------------------------+
✅ 第三步：进入 fun(1)（x=1）
+------------------------+
| fun(x=1) 的栈帧 |
+------------------------+
| fun(x=2) 的栈帧 |
+------------------------+
| fun(x=3) 的栈帧 |
+------------------------+
| main() 的栈帧 |
+------------------------+
✅ 第四步：进入 fun(0)（不执行递归）
+------------------------+
| fun(x=0) 的栈帧 | ← 条件不成立，直接返回
+------------------------+
| fun(x=1) 的栈帧 |
| fun(x=2) 的栈帧 |
| fun(x=3) 的栈帧 |
| main() 的栈帧 |
+------------------------+
⬅️ 之后依次弹栈回到 main()，释放这些栈帧。
复杂度分析
✅ 时间复杂度：O(n)
我们要分析的是：fun(n) 一共要花费多少单位时间？
-
执行一次
if (x > 0)：1 单位时间 -
执行一次
printf("%d", x)：1 单位时间 -
执行一次
fun(x - 1)：记作 T(n-1) 单位时间（递归调用自身的耗时）
所以，每次调用 fun(x) 的总时间 T(n) 是：
T(n) = 1（if 判断）+ 1（打印）+ T(n - 1)
T(n) = 1 + 1 + T(n-1)= 2 + T(n-1)T(n-1) = 2 + T(n-2)
T(n-2) = 2 + T(n-3)
...
T(1) = 2 + T(0)
T(0) = 1（只执行一次 if，条件不成立直接返回）
所以：
T(n) = 2n + 1| 名称 | 表达式 | 说明 |
|---|---|---|
| 总时间函数 | T(n) = 2n + 1 | 包括每次调用的 if 和 printf，共 2n 次操作 + 1 次 base case |
| 时间复杂度 | O(n) | 取最高阶忽略常数，线性复杂度 |
✅ 空间复杂度（栈空间）：O(n)
-
每次递归调用会创建一个新的栈帧。
-
所以最多有
n+1层递归（从 x = n 到 x = 0） -
所以空间复杂度也是：O(n)
递归中的静态变量
int fun(int n)
{static int x = 0; // 静态变量，只初始化一次，保存在**静态区（数据段）**if(n > 0){x++;return fun(n - 1) + x;}return 0;
}
普通局部变量：
-
每次函数调用都会新建一个副本，存在栈区
-
调用结束后销毁，不会“记住”上一次的值
静态局部变量 static：
-
生命周期为整个程序运行期间
-
只初始化一次
-
存储在静态存储区（Data Segment），不在栈区
-
所以每次递归调用都共享同一个 x
递归过程树
fun(5)|vfun(4) + x=1 → return ?|vfun(3) + x=2 → return ?|vfun(2) + x=3 → return ?|vfun(1) + x=4 → return ?|vfun(0) → return 0开始回溯：
fun(1): return 0 + x=5 = 5
fun(2): return 5 + x=5 = 10
fun(3): return 10 + x=5 = 15
fun(4): return 15 + x=5 = 20
fun(5): return 20 + x=5 = 25
❗ 注意：x 在每次递归调用时都自增，最终值是 x=5
而因为每次回溯时都加的是 当前 x=5，所以：
最终返回值 = 5 + 5 + 5 + 5 + 5 = 25
内存结构图解
+---------------------------+ ← 低地址
| 代码区（Text） | ← 编译后的 fun() / main() 指令
+---------------------------+
| 数据段（Static / Global） |
| static int x = 0; | ← 所有递归共享这一个变量
+---------------------------+
| 栈区（Stack） |
| fun(n=1) 的栈帧 |
| fun(n=2) 的栈帧 |
| fun(n=3) 的栈帧 |
| fun(n=4) 的栈帧 |
| fun(n=5) 的栈帧 |
| main() 的栈帧 |
+---------------------------+
| |
| 堆区（Heap） | ← malloc / new 用
+---------------------------+ ← 高地址