永远是两个部分
递归是用自身来定义的函数。每个正确的递归函数都恰好有两个部分。基准情形是一个你能立刻回答、无需再次调用的小输入——它让过程停下来。递归情形做一点点工作，然后在更小的输入上调用同一个函数，相信它会带回正确答案。
最经典的第一个例子是阶乘：n! = n × (n−1)!，而 0! = 1。这个定义本身就是递归——基准情形是 0，每一步剥下一个因子，把其余的推迟下去。
long long fact(int n) {
if (n == 0) return 1; // base case
return n * fact(n - 1); // recursive case: smaller input
}
// fact(4) = 4 * fact(3) = 4 * 3 * fact(2) = ... = 24调用栈替你记账
计算机怎么记得 fact(4) 在 fact(3) 返回后还欠着一个 `4 *`？它用调用栈——正是你在线性结构那一级见过的后进先出结构。每次调用都压入一个栈帧，保存它的局部变量和恢复执行的位置。调用返回时，它的栈帧弹出，控制权交回调用者。
Calling fact(3): frames pushed downward, then popped (return).
push fact(3) waits for fact(2)
push fact(2) waits for fact(1)
push fact(1) waits for fact(0)
push fact(0) = 1 <-- base case, returns now
fact(1) = 1*1 = 1 pop
fact(2) = 2*1 = 2 pop
fact(3) = 3*2 = 6 pop --> answer这就是为什么递归像一种信任：你写 fact(n) 时就当作 fact(n−1) 已经能用了。栈默默替你记下没做完的工作，你自己永远不必去管。
当递归重复劳动：斐波那契
递归很优雅，但并不天生高效。斐波那契数——fib(n) = fib(n−1) + fib(n−2)，其中 fib(0)=0、fib(1)=1——每次会发起两次递归调用。画出递归树就能看到同样的子问题被一遍遍重算。
fib(5)
____________ fib(5) ____________
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) f1 f1 f0 f1 f0
/ \
f1 f0
fib(3) is computed twice, fib(2) three times ... work explodes.解决办法是记忆化：第一次算出每个 fib(k) 时就把它记下来，之后直接复用。这能把树压成一条线，把 O(2^n) 变成 O(n)。在动态规划那一级，你会再次遇到这个思想，并大展身手。
递归出错的两种方式
由于每次调用都吃掉一个栈帧，递归有两种著名的失败方式。无限递归是忘了基准情形（或根本没朝它靠近），于是函数永远调用自己。栈溢出是递归太深——即便完全正确的递归，如果嵌套上百万层，也会崩溃，因为栈的大小是有限的。
// BUG: no base case is ever reached -> infinite recursion -> stack overflow
int bad(int n) {
return bad(n - 1); // never stops; n races past 0 into negatives
}
// FIX: a base case that the recursion actually reaches
int good(int n) {
if (n <= 0) return 0;
return good(n - 1);
}