数据结构：递归（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 用
+---------------------------+ ← 高地址