递归
阶乘 n!（调用栈）
最经典的线性递归，直观展示「入栈展开 → 命中边界 → 出栈求值」的全过程。
C++阶乘 n!（调用栈） 核心代码
1int fact(int n) {2 if (n <= 1) return 1; // 递归边界：1! = 13 return n * fact(n - 1); // 递归式：n! = n × (n-1)!4}5int ans = fact(5); // 调用入口调用栈（栈顶在上，从下往上生长）
调用栈已空
栈底
递归式展开 / 逐层求值
5! = ?
已返回的结果
暂无
开始执行 int ans = fact(5)：主程序调用 fact(5)，进入递归函数。
时间复杂度O(n)
空间复杂度O(n)
递归深度n
调用次数n
已调用 · 等待返回命中边界已求值返回
💡 阶乘 n!（调用栈） 原理速记
递归就是「自己调用自己」。求 n! 时先假定 (n-1)! 已经算好，于是 n! = n × (n-1)!；一直拆到 n ≤ 1 这个能直接给出答案的边界，再一层层把结果乘回去。
- 两个必要条件：递归边界（n ≤ 1 直接返回 1）+ 递归式（规模每次减 1）。
- 「递」阶段每层调用入栈，保存现场；「归」阶段用子问题的结果算出本层答案。
- 递归深度 = n，每层都要占用栈空间，n 过大可能爆栈（栈溢出）。
- 任何线性递归都可以改写成循环（迭代），递归写法更贴近数学定义。
🧭 递归与回溯怎么学
递归 = 把大问题拆成同结构的小问题 + 一个能直接给出答案的边界； 回溯 = 在递归的基础上「做选择 → 递归 → 撤销选择」，走不通就退回上一步换条路。
- 写递归先写边界条件，再写递归式，最后检查规模是否严格变小。
- 在草稿纸上画递归树 / 决策树，是理解调用过程最快的方法。
- 回溯的三要素：路径（已做的选择）、选择列表（还能选什么）、结束条件。
- 发现「重复子问题」就想记忆化搜索 / DP，发现「明显不合法」就提前剪枝。