Olverae Assets

1 一句话定义

递归（recursion）就是一个函数在解决问题时，调用"自己"去解决一个更小的同类问题，直到问题小到能直接回答为止。

把它想成俄罗斯套娃：要数清一套娃娃有几个，你不必一眼看穿全部——只要打开最外层、把"里面那套"交给同样的方法去数，再把结果 +1 就行。最小那只打不开（里面没娃娃）就是停下来的信号，叫基准情形。每打开一层就"递"下去，数到底再一层层"归"上来。

同一个例子贯穿全篇：求 4! = fact(4)。先一层层"递"下去，每层把问题缩小 1（fact(4)→fact(3)→…→fact(0)）；命中基准 fact(0)=1 后，再一层层"归"上来，把 1 → 1 → 2 → 6 → 24 乘回去。下一节你就亲手单步看这根调用栈怎么压、怎么弹。

2 模型 · 单步看调用栈怎么压、怎么弹

动手之前先认清：递归函数必须有两个零件——一个让它"停下来"、一个让它"接着拆"。少了任何一个，要么停不下来（栈溢出），要么根本没在缩小问题。

递归函数的两个零件（缺一不可）

下面这段就是交互区演示的 fact。两行红/蓝注释指出的，就是每个递归函数都必须有的两个零件。

int fact(int n) {
    if (n == 0) return 1;       //  ① 基准情形：小到能直接回答，立刻返回、不再递归
    return n * fact(n - 1);    //  ② 递归情形：调用更小的自己（n-1），向基准靠近
}

关键直觉叫 "相信递归"（leap of faith）：写第 3 行时，不要在脑子里把 fact(n−1) 一层层展开。你只需假设 fact(n−1) 已经算对了，那 fact(n) 就只剩"乘一次 n"这点活。把"更小的同类问题"放心交给自己的副本——这正是递归代码能短到 3 行的原因。下面点 ▶ 看这份信任如何被调用栈一层层兑现。

递归调用栈 · 演示 fact(4)

调用栈（最上面一帧 = 此刻正在执行的那一层；越往下越深）

递归代码 · int fact(int n)

0

当前栈深

0

最大栈深

—

最终结果

提示

点 ▶ 演示 fact(4)：看每次调用如何在栈顶压入一帧；命中基准 fact(0)=1 后，再一层层把结果乘着返回、弹出。

3 核心要点 · 4 句人话吃透递归

每张卡片先用一句大白话点破，再配最小例子。第①条是写对递归的命根子，第②条是它为什么"会爆"的原因。

① 两个零件：基准 + 递归

一句话：基准情形负责"刹车"，递归情形负责"前进"。没刹车会停不下来（栈溢出），不前进就原地打转。

基准情形 base case：问题小到能直接给答案，立刻 return，不再调用自己。递归情形 recursive case：把问题缩小一点，交给自己的副本，再用它的结果拼出答案。检查清单：每次递归调用都必须比现在"更接近基准"。

if (n == 0) return 1; // 刹车

return n * fact(n - 1); // 前进(n→n-1)

② 调用栈：递归不是免费的

一句话：每进入一层递归，就在"调用栈"上多占一帧，存着这一层的局部变量和"算完回哪儿"。递归多深，栈就多高。

fact(4) 最深时栈上同时有 5 帧（fact(4)…fact(0)）。帧不会立刻消失——它要等更深的调用返回才能算完、弹出。栈空间有限，递归太深（或没基准）会把它撑爆 → stack overflow / 段错误。

fact(4) ⏳等

fact(3) ⏳等

fact(2) ⏳等

fact(1) ⏳等

fact(0)=1 ← 到底，开始往回弹

③ 相信递归（leap of faith）

一句话：写当前这一层时，假设"更小的自己"已经算对了。别在脑子里把每一层都展开——那是栈替你做的事。

写 fact(n) = n * fact(n-1) 时，你只需保证：(a) 基准对；(b) 假设 fact(n-1) 对，则 fact(n) 也对。这两点成立，整个递归就对——这其实就是数学归纳法。

所以读递归别"钻到底"，只看一层：它如何用"小一号的答案"拼出"自己的答案"。

④ 递归 vs 循环

一句话：凡是递归能做的，循环也能做；递归胜在"代码贴着问题的结构"（树、分治），代价是每层都占栈空间。

fact 这种"线性递归"改成 for 循环又快又省栈。但树/图的遍历、分治排序（归并/快排）、汉诺塔用递归写出来短而清楚，硬改循环反而要自己手动维护一个栈。

// 同一个 4! 用循环：

int r = 1;

for (int i = 2; i <= n; i++) r *= i;

4 错误实验室 · 点一下亲眼看 bug

下面 4 个是初学者写递归最常翻车的坑——前 3 个都让递归"停不下来"而栈溢出（这正是和二叉树"漏空子树基准"同源的错误），最后 1 个是"递归结构对、合并方式错"。点击卡片，控制台会模拟真实运行结果。

① 漏写基准情形

没有 if(n==0) → 永远递归下去 → 栈溢出

② 基准够不到

基准设成 n==1，fact(0) 一路冲过头 → 栈溢出

③ 递归没变小

调 fact(n) 而非 fact(n-1) → n 原地不动 → 栈溢出

④ 合并方式写错

把 × 写成 + → 算成了求和，不是阶乘

// 点击上方任一卡片，查看错误代码与运行效果

$ ./a.out （等待运行...）

5 即时小测 · 5 题 + 动手例题

这 5 题都卡在初学者最常错的点上——基准的作用、栈能压多深、"相信递归"怎么用、漏基准的后果、递归 vs 循环。点错也别灰心，提示会告诉你错在哪。最后再到练习系统亲手把递归写出来、真正编译运行。

去做例题：递归 · 阶乘

去做例题

Recursion

递归