C 递归入门
更新时间：2026-08-26。本文是
languages/c/主题入门层第 23 篇，函数主题的最后一篇。递归——函数调用自己——第一次见到的人都会觉得"这也能行？"。它其实一点也不神秘：不过是"新开一个栈帧，执行同一段代码"而已。
本文要回答的问题
- 递归靠什么停下来？写递归第一步做什么？
- 为什么递归太深会"栈溢出"？
- 递归和循环怎么选？
一、递归的结构
递归函数调用自己，但每次调用处理的是更小的同一类问题。两个要素缺一不可：
int factorial(int n) {
if (n <= 1) return 1; // 基准情形：不再递归，直接返回
return n * factorial(n - 1); // 递归情形：规模变小
}| 要素 | 作用 | 缺了会怎样 |
|---|---|---|
| 基准情形（base case） | 终止条件 | 无限递归 → 栈溢出 |
| 递归情形 | 规模缩小、逼近基准 | 停不下来 |
写递归的流程：
- 先想清楚基准情形（最小的问题，答案已知）；
- 再想"如何把大问题拆成小问题"；
- 假设"小问题的递归调用会正确返回"，组合出大问题的解。
factorial(4) 的执行过程：
factorial(4) = 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * (3 * (2 * 1))
= 24二、递归与栈：深度是硬限制
每次递归调用都压一个新栈帧（返回地址 + 局部变量）。默认栈大小约 8MB（Linux），每个栈帧几十~上百字节，所以递归深度是有限的：
int recurse(int n) {
char buffer[100]; // 每个栈帧 100+ 字节
printf("深度 %d\n", n);
return recurse(n + 1); // 深度到几万时 → 栈溢出
}跑起来会 Segmentation fault 或 stack overflow。递归深度上万就要警惕——二叉树的深度通常几十上百没事，但"递归处理超长链表"就会爆栈。
用工具看真实栈大小：
ulimit -s # 输出栈大小（KB），Linux 默认 8192三、经典例子：斐波那契（和它的教训）
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}能跑，但 fib(40) 就要数亿次调用——因为重复计算：fib(n-1) 和 fib(n-2) 会反复算同样的子问题。这暴露了递归的代价：不记忆化的话，指数级爆炸。
| 场景 | 递归 | 循环 |
|---|---|---|
| 树/图遍历 | 自然，代码清晰 | 需要手写栈，繁琐 |
| 深度未知/可能很深 | 有栈溢出风险 | 安全 |
| 简单线性计算（求和） | 不必要 | 清晰高效 |
| 复杂度 | 可能重复计算 | 通常可控 |
选择标准：问题的结构本身就是递归的（树、目录、分治），用递归；否则用循环。斐波那契这种，用循环或"动态规划"更好。
四、分治与递归的黄金组合
递归最强的场景是分治：把问题一分为二，分别解决，再合并。经典例子——用递归打印目录树（文件系统本身是树）：
// 伪代码：遍历目录
void list_dir(const char *path, int depth) {
for (每个条目 item in path) {
if (item 是目录) {
list_dir(item, depth + 1); // 递归进子目录
} else {
printf("%*s%s\n", depth, "", item);
}
}
}树的遍历、快速排序、二分查找，全是这个套路。看到"一层套一层的结构"，第一反应就应该是递归。
五、尾递归：理论美好，C 编译器的现实
"尾递归"（递归调用是函数最后一个操作）理论上可以被优化成循环（不增长栈）。但 GCC/Clang 默认不开启尾调用优化（-foptimize-sibling-calls 才行，且环境限制多）。所以：
别依赖尾递归防爆栈。需要大深度就用循环，或用 -O2 试验但不打包票。
六、常见坑对照
| 坑 | 现象 | 对策 |
|---|---|---|
| 没有基准情形 | 栈溢出崩溃 | 先写基准情形 |
| 递归不收敛 | 死循环递归 | 确认规模递减 |
| 深度过大 | 段错误 | 用循环或迭代 |
| 重复计算 | 慢到爆 | 记忆化 / 改循环 |
| 尾递归当优化 | 仍可能爆栈 | 别依赖 |
七、与本站主线衔接
- 栈帧、调用深度与栈溢出的底层机制，见专家层内存布局与 ABI；
- 栈溢出崩溃的排查（
ulimit -s、gdb backtrace），见 crash 排查线； - 递归的工程应用（遍历树、算法），见链表与二叉树实现。
一句话总结
递归 = 基准情形（停）+ 递归情形（缩小），本质是每次调用新开栈帧跑同一段代码；深度受栈大小限制，别依赖尾递归；结构天然递归（树/目录）用递归，线性计算用循环，斐波那契记得别裸写递归。