本讲定位：五级客观题的第二失分点（第一是链表）。2026 年 3 月五级判断题第 4 题就是”给出递推式 $T(n)=\dots$，问时间复杂度”。官方大纲还专门点名了**“递归的优化策略”**——这在整个 GESP 体系里是第一次出现”优化”二字，说明要求已经从”会写”上升到”会改进”。
对应官方大纲：五级知识块 6「递归算法」——递归算法的相关概念、递归算法的时间复杂度和空间复杂度、递归的优化策略。
前置知识：四级第 04 讲（递推）、四级第 05 讲（复杂度估算）、五级第 05 讲（二分）。
代码说明：本讲代码均已用 g++ 11.5 编译运行验证，递归调用次数、耗时对比均为本机实测。
递归（recursion）：函数直接或间接调用自己。
| 要素 | 说明 | 缺了会怎样 |
|---|---|---|
| ① 递归边界（出口） | 最简单的情形，直接返回 | 无限递归 → 栈溢出崩溃 |
| ② 递归关系式 | 把大问题拆成同类的小问题 | 不成其为递归 |
| ③ 递归方向 | 每次调用必须向边界靠近 | 永远到不了出口 |
int fact(int n) {
if (n <= 1) return 1; // ① 边界
return n * fact(n - 1); // ② 关系式，③ n 递减，朝边界走
}
⚠️ 教学第一课：让学生把
if (n <= 1) return 1;删掉运行一次，亲眼看到程序崩溃（Segmentation fault）。这比说十遍”别忘边界”管用。
每次函数调用，系统都在”栈”上开一块空间存放局部变量和返回地址。
fact(4) 的执行过程：
调用阶段（往下压栈）： 回溯阶段（往上弹栈）：
fact(4) → 需要 fact(3) fact(1) 返回 1
fact(3) → 需要 fact(2) fact(2) 返回 2*1 = 2
fact(2) → 需要 fact(1) fact(3) 返回 3*2 = 6
fact(1) → 返回 1 ✅ fact(4) 返回 4*6 = 24
关键认识：递归调用时，上层函数并没有结束，它在”等”下层的结果。 所有等待中的函数都占着栈空间——这就是递归空间复杂度的来源。
$$ \boxed{\text{递归的空间复杂度} = O(\text{递归深度}) \times \text{每层占用}} $$
栈空间通常只有 1~8 MB，递归太深就会崩溃。
实测（本机，每层一个 int 参数）：递归深度约 10 万层时开始有风险，100 万层必崩。
📌 考场经验：
这也是四级第 04 讲说”递推比递归安全”的原因之一。