专题12 · 递归

🔁 概念与栈　0–8′

"递"下去、"归"回来两个阶段；调用栈如何实现；三要素：终止条件、递归调用、返回结果。

🧩 四道题型　8–20′

放苹果（分类递归）、小球摆放（错位分球）、上台阶（记忆化）、十进制转二进制（回溯输出）。

⚡ 优化　20–23′

普通递归 vs 尾递归；重复计算的识别；递归 → 递推 的改写时机。

"递"阶段发生了什么

每层把自己的现场（参数、局部变量、返回地址）压进调用栈，然后带着更小的参数往下走。 此时谁都没有算出答案。

"归"阶段发生了什么

碰到终止条件后，最深层先算出答案，逐层弹栈，每层拿到下层的返回值再算自己的、再返回。 答案是从最深处往外长出来的。

要素① 终止条件

没有它 → 无限递归 → 栈溢出 RE。
if (n == 0) return 0;

要素② 递归调用

规模必须严格变小，否则永远到不了底。
return n + sum(n-1);

要素③ 返回结果

每层要把结果交回去；忘了 return 就丢答案。
return ...;

尾递归为什么省

本层的局部变量已经用完了（答案全在 acc 里）， 编译器可以复用同一个栈帧（尾调用优化），栈深度保持 O(1)。

但要注意

C++ 不保证做尾调用优化（取决于编译器与 -O2）。 竞赛里更稳的做法是直接写成循环，别依赖优化。

分类的依据

支①（有空盘）：至少一个盘子空着 → 等价于把 m 个苹果放进 n−1 个盘子。
支②（无空盘）：每个盘子至少 1 个 → 每盘各拿走 1 个，变成 m−n 个苹果放 n 个盘子。

为什么不会漏、不会重

"至少有一个空盘"与"一个空盘都没有"互斥且穷尽， 所以两支相加不重不漏 —— 这就是递归分类题的核心检查点。

为什么会重复

f(6) = f(5) + f(4)，而 f(5) 里又要算 f(4)、 f(3)……不同分支撞到了同一个子问题，却各自从头算一遍。

重复到什么程度

纯递归算 f(n) 的复杂度是 O(2ⁿ)（实际约 1.618ⁿ）。 n = 40 就要算上万亿次 —— 必须优化。

记忆化三行改动

long long memo[105];   // 0 表示没算过
long long f(int n){
  if(n <= 2) return n;
  if(memo[n]) return memo[n];  // ① 查
  return memo[n] = f(n-1) + f(n-2);  // ② 记
}

效果与代价

复杂度从 O(2ⁿ) 降到 O(n)：每个子问题只算一次。
代价：多一个数组的空间；且递归深度仍是 n，n 到 1e5 仍会爆栈。

① 纯递归（超时）

int ways(int i){
  if(i == 0) return 1;
  if(i < 0) return 0;
  int s = 0;
  for(int j=1;j<=k;j++)
    s = (s + ways(i-j)) % MOD;
  return s;
}

思路最清楚，但 O(Kⁿ)，N 稍大就跑不出。

② 记忆化（会爆栈）

int memo[100005];
int ways(int i){
  if(i == 0) return 1;
  if(i < 0) return 0;
  if(memo[i] != -1) return memo[i];
  int s = 0;
  for(int j=1;j<=k;j++)
    s = (s + ways(i-j)) % MOD;
  return memo[i] = s;
}

复杂度 O(NK)，但 N=1e5 时递归 10 万层 → RE。

③ 递推 + 滑动窗口（正解）

f[0] = 1;
long long win = 1;
for(int i=1;i<=n;i++){
  f[i] = win % MOD;
  win += f[i];
  if(i-k >= 0) win -= f[i-k];
}
cout << f[n];

没有栈的问题，窗口和把 O(NK) 再降到 O(N)。

代码

void toBin(int n){
  if(n == 0) return;        // 终止
  toBin(n / 2);               // ★ 先递下去
  cout << (n % 2);            // ★ 回来才输出
}

把 cout 放在递归调用之后，就自动实现了"倒序输出"。

改成正序会怎样

void toBin(int n){
  if(n == 0) return;
  cout << (n % 2);            // 先输出
  toBin(n / 2);               // 再递归
}

输出会完全反过来（13 会输出 1011 的反序 1101）。 体会"语句位置"如何决定结果 —— 这是递归最妙的地方。

① 定状态

函数参数代表什么？
f(m,n) = m 个球放 n 个盒。

② 找终止

什么情况下不用再拆？
m==0 || n==1。

③ 找分类

按什么互斥且穷尽地分成几支？
有空盒 / 无空盒。

④ 写返回

各支结果怎么合并？
return 支① + 支②;

保持递归

放苹果、树的遍历、DFS 回溯、分治（归并/快排）—— 结构本身就是树。

改成递推

上台阶、斐波那契、阶乘——只是一条链，而且深度可能很大。

改写方法

把"从 n 往下拆"反过来写成"从 0 往上填表"； 递归式里的 f(n-1) 就是数组的前一项。

① 特判档：先别想算法，看数据范围表

题目给的数据范围表就是出题人给你的送分清单。看到「n = 1」「只有一组数据」这类一行， 就先写个 if 直接输出答案。2 分钟换 5~10 分，全场最划算。

② 暴力档：按题意最直白地写一遍

多重循环、DFS 全枚举、朴素 O(n³)……不要优化，只要保证最小那档全对。 它既是保底分，又是后面对拍的标尺——没有它你无法证明正解是对的。

③ 特殊性质档：题目里那句「若……」

常见的送分性质：数据已经有序、所有值完全相同、规模小到可以 O(n²)、 只出现一种类型。题目写出来就是让你拿的，专门写一份即可。

④ 正解档：思路定了，就赢了八成

考场上的时间几乎都花在想思路上，不是写代码。写完先跑样例， 再用第 ② 档的暴力版造小数据对拍——这是唯一能证明你思路对的办法。

放苹果 · APPLE

第1档 · 2 分钟
m == 0 或 n == 1 → 1

第2档 · 8 分钟
枚举每件苹果放哪个盘子，m,n ≤ 10 稳过

第3档 · 10 分钟
只做 n ≤ 2 的情形（答案就是 m/2 + 1）

第4档 · 15 分钟
f(m,n) = f(m,n−1) + (m>=n ? f(m−n,n) : 0)（空一盘 / 每盘先放一个）

台阶问题 · STAIR

第1档 · 2 分钟
N == 0 或 N == 1 → 1；K == 1 → 1

第2档 · 8 分钟
递归枚举下一步走几级，N ≤ 20 稳过

第3档 · 10 分钟
K ≥ N → 答案 = 2^(N−1)

第4档 · 15 分钟
记忆化 f(n) = Σ f(n−i), i=1..K，或递推 + 前缀和优化