💡 打个比方
排队问"你是从后数第几个？"：每个人只会一句话——"去问前面那位，他说是第 k 个，那我就第 k+1 个。"最后一名直接说"我是第 1 个"。答案一层层传回来，每个人只负责加 1。
递归就是这样：大问题拆成"更小的同一个问题"，小到不能再拆时（基本情况）直接给答案，然后一层层把结果合并回去。
递归两要素：① 基本情况（base case）——最小的问题直接答，不再调用自己；② 问题变小——每次调用都让问题缩小一点，保证最终走到基本情况。两个条件缺一个，就会无限套娃（栈溢出）。
🖼️ 大图看明白
📏 怎么写递归：只要 3 步
第 1 步：想清楚基本情况——最小的问题长什么样，直接给答案，不再调用自己。比如算"从后数第几个"时，排在最前面的人不用问，直接说 1。
第 2 步：假装小问题的答案已经有了，用它算当前问题。比如"我是第几个" = "我后面那位的答案" + 1。你不用管他怎么算的，他负责。
第 3 步：把两步合起来写代码，并确认问题每层都变小（n 变成 n-1、n-2……），保证一路走到底一定碰到基本情况，不会无限套娃。
口诀：先问"最小的怎么答"，再问"假设小的答了，我怎么算"，最后检查"问题有没有变小"。三问齐了，递归就能写。
💻 C++ 怎么写
// 阶乘：fact(3) = 3 × 2 × 1
int fact(int n) {
if (n == 1) return 1; // 第 1 步：基本情况
return n * fact(n - 1); // 第 2 步：用小问题的答案
}
// 斐波那契：每个数 = 前两个数之和
int fib(int n) {
if (n <= 2) return 1; // 基本情况：fib(1)=fib(2)=1
return fib(n - 1) + fib(n - 2);
}
int main() {
cout << "fact(3) = " << fact(3) << endl; // 输出 6
cout << "fib(5) = " << fib(5) << endl; // 输出 5
return 0;
}
为什么朴素 fib 慢？看上面那棵递归树：fib(3) 被问了 2 遍，fib(2) 被问了 3 遍……每多一层，重复翻倍，总次数约 O(2ⁿ)，n=40 就要几十亿步。记忆化：用一个数组把算过的答案存下来，再遇到直接查表。每个 fib(i) 只算 1 次，总时间降为 O(n)。
✋ 你来试试
题 1：写递归时忘了写基本情况会怎样？程序会"卡住"还是"崩溃"？
会崩溃，而且崩溃得很有规律：f(n) 调 f(n-1)，f(n-1) 又调 f(n-2)……问题虽然一直变小，但永远不会"直接给答案"，于是调用一层叠一层，把系统的"调用栈"（可以想象成一摞盘子）叠爆——这叫栈溢出（stack overflow）。每写一个递归函数，先问自己：最小的问题长什么样？
题 2：fib(5) 只有一棵小树，为什么 fib(40) 要等好几分钟？怎么救？
因为重复子问题随层数指数级爆炸：每多一层，树大约翻倍，朴素 fib 的总调用次数约 O(2ⁿ)——fib(40) 要算几十亿次 fib(1)、fib(2)。救法：记忆化。开一个数组 memo，算出 fib(i) 就存进 memo[i]，下次再遇到 fib(i) 直接查表返回。这样每个 fib(i) 只认真算 1 次，总共 O(n) 步，fib(40) 瞬间出结果。
🎯 一句话记住：递归 = 基本情况 + 问题变小；调用栈"下去问、回来合"；朴素 fib O(2ⁿ) 因为重复子问题，记忆化查表 O(n)。