第 14 章 递归与递推 · 知识细节练习

考点：递归的定义（A1）。

解析：递归 = 函数直接（自己调自己）或间接（A 调 B、B 调 A）调用自身。✅ 正确

排除法：无（判断题）。混淆点：递归必须有出口（A2），否则无限递归。

关联 · 递归的两要素（A2）：出口 + 递归关系，缺一不可。

考点：递归的两要素（A2）。

解析：① 边界条件 = 最小情形的直接答案（如 $0! = 1$）；② 递归关系 = 把问题化归为规模更小的同类问题。✅ 正确

排除法：无（判断题）。混淆点：边界写在递归调用之前，先判断再递归（G1）。

关联 · 递归出口写在前面（G1）：出口先行，防死递归。

考点：递归的执行过程（A3）。

解析：每层调用入栈（保存现场），先层层深入直到出口，再层层返回、把结果带回。✅ 正确

排除法：无（判断题）。混淆点：递归深度 = 栈中同时存在的最大层数（J5）。

关联 · 递归深度统计（J5）：进入加一、返回减一。

考点：递归与循环的转换（A4）。

解析：递归与循环表达能力等价：递归改循环就是递推（正向填表），循环改递归就是加参数化规模。✅ 正确

排除法：无（判断题）。混淆点：等价的是"能力"，性能上递推通常更快（无栈帧开销）。

关联 · 递推与递归的方向（C2）：递归自顶向下、递推自底向上。

考点：递归深度与栈溢出（A5）。

解析：递归每层占一段栈空间，$10^6$ 层远超默认栈容量 → 栈溢出崩溃。正确答案 A。

排除法：B/C 是幻想；D 反而更慢（A6）。

关联 · 递归的调用开销（A6）：深度过大时改用递推（G4）。

考点：递归的调用开销（A6）。

解析：每次调用要保存参数、局部变量、返回地址（栈帧），常数开销大于循环。✅ 正确

排除法：无（判断题）。混淆点：开销大不代表不能用——代码清晰时仍优先递归。

关联 · 递归与递推的选择（G4）：深度可控用递归，否则递推。

考点：阶乘的递归定义（B1）。

解析：$n! = n \times (n-1)!$，$0! = 1$ 是出口——最经典的递归入门。✅ 正确

排除法：无（判断题）。混淆点：出口选 $0!$ 保证 $f(0)$ 也有定义。

关联 · 阶乘递归输出（I1）：$f(5) = 120$。

考点：斐波那契的递推式（B2）。

解析：$1, 1, 2, 3, 5, 8$——$f(6) = 8$。正确答案 A。

排除法：B（$13$）是 $f(7)$；C（$5$）是 $f(5)$；D（$21$）是 $f(8)$。

关联 · 斐波那契递归的重复计算（B3）：直接递归的代价。

考点：斐波那契递归的重复计算（B3）。

解析：$f(n)$ 的递归树里同一子问题出现多次（$f(2)$ 被反复调用），总调用次数指数级 → $O(2^n)$。✅ 正确

排除法：无（判断题）。混淆点：不是"递归慢"，是"重复计算"慢——递推（或把算过的结果存起来）都能解决。

关联 · 指数爆炸的原因（H2）：重复子问题是祸根。

考点：汉诺塔的移动次数（B4）。

解析：$n$ 个盘最少 $2^n - 1$ 次移动（$h(1)=1$，每加一个盘翻倍再加 1）。正确答案 A。

排除法：B/C 是多项式量级，与"翻倍"规律不符；D（$n!$）无依据。

关联 · 汉诺塔的递推式（B5）：$h(n) = 2h(n-1) + 1$。

考点：汉诺塔的递推式（B5）。

解析：先把上面 $n-1$ 个盘移走（$h(n-1)$ 步）→ 移最大盘（1 步）→ 再把 $n-1$ 个盘移回来（$h(n-1)$ 步）：$h(n) = 2h(n-1) + 1$。正确答案 A。

排除法：B 是等差数列；C 漏了"移最大盘"的 1 步；D 无依据。

关联 · 汉诺塔次数递推（N6）：$h(5) = 31$。

考点：辗转相除求最大公约数（B6）。

解析：gcd(a, b) = gcd(b, a % b)，b == 0 时返回 a——参数不断变小、结构相同，天然递归。✅ 正确

排除法：无（判断题）。混淆点：a % b 一定小于 b，参数严格递减，必达出口。

关联 · 递归求最大公约数（I6）：gcd(48, 36) = 12。

考点：递归求数组和（B7）。

解析：sum(l, r) = a[l] + sum(l+1, r)，l > r 返回 0——"第一个元素 + 其余部分"，规模每次减 1。✅ 正确

排除法：无（判断题）。混淆点：这类"线性递归"深度 $O(n)$，求和用循环更简洁——递归是教学示范。

关联 · 递归求 1 到 n 的和（I3）：同款结构的整数版。

考点：递推的定义（C1）。

解析：递推 = 已知初始值，按公式从前往后逐项计算（正向填表）。✅ 正确

排除法：无（判断题）。混淆点：递推不需要函数调用栈，空间常为 $O(n)$ 或滚动 $O(1)$。

关联 · 递推的循环实现（C7）：循环 + 数组填表。

考点：递推与递归的方向（C2）。

解析：递归从目标出发向下拆（自顶向下），递推从初始值出发向上算（自底向上）。✅ 正确

排除法：无（判断题）。混淆点：两者结果相同、复杂度可同可异（C4）。

关联 · 递推的滚动变量（C5）：递推常配滚动变量省空间。

考点：递推的三要素（C3）。

解析：初始值（如 $f(1) = f(2) = 1$）、递推公式（如 $f(n) = f(n-1) + f(n-2)$）、目标项（要算到哪）。正确答案 A。

排除法：B 是实现工具不是要素；C 是所有程序的通用结构；D 是其他章节的概念。

关联 · 递推初值写错（H4）：初始值是三要素中最易错的。

考点：递推与递归的复杂度对比（C4）。

解析：递推每个状态算一次，$f(50)$ 只需约 $50$ 次迭代；直接递归约 $2^{50}$ 次调用。正确答案 A。

排除法：B（$2500$）是 $n^2$ 的误解；C 是全排列量级；D 低估了线性递推（$O(n)$）。

关联 · 斐波那契递推输出（K1）：$f(10) = 55$ 的填表过程。

考点：递推的滚动变量（C5）。

解析：只保留递推需要的最近几项（斐波那契用两个变量滚动），空间从 $O(n)$ 降到 $O(1)$。✅ 正确

排除法：无（判断题）。混淆点：滚动变量只省空间、不省时间（每个状态仍要算一次）。

关联 · 递推取模（K6）：滚动 + 取模的标准写法。

考点：爬楼梯问题（C6）。

解析：$f(1)=1$、$f(2)=2$、$f(3)=3$、$f(4)=5$、$f(5)=8$——上 5 级共 $8$ 种。正确答案 A。

排除法：B（$5$）是 $f(4)$；C（$13$）是 $f(6)$；D（$3$）是 $f(3)$。

关联 · 爬楼梯递推输出（K2）：$f(6) = 13$ 的代码。

考点：递推的循环实现（C7）。

解析：循环变量从小到大，每轮用已算出的项填新项；空间可滚动优化到 $O(1)$。✅ 正确

排除法：无（判断题）。混淆点：滚动变量只保留最近两项（K6）。

关联 · 递推取模（K6）：滚动 + 取模的标准写法。

考点：回溯的定义（D1）。

大纲注：回溯在 NOI 2025 大纲中未单列条目，属 DFS 的枚举应用、初赛完善程序常考。

解析：回溯 = 尝试 → 递归 → 撤销（恢复现场）→ 试下一个选择，穷举所有可能。✅ 正确

排除法：无（判断题）。混淆点："撤销"是回溯区别于普通递归的标志（P3 忘撤销的教训）。

关联 · 回溯三部曲（D2）：选择、递归、撤销。

考点：回溯三部曲（D2）。

大纲注：回溯在 NOI 2025 大纲中未单列条目，属 DFS 的枚举应用、初赛完善程序常考。

解析：选择（打标记/记录）→ 递归（深入下一层）→ 撤销（清标记/恢复现场）。正确答案 A。

排除法：B（排序→查找→合并）与回溯无关；C 是栈的操作；D 无依据。

关联 · 全排列回溯计数（M1）：三部曲的标准应用。

考点：回溯与深度优先搜索（D3）。

大纲注：回溯在 NOI 2025 大纲中未单列条目，属 DFS 的枚举应用、初赛完善程序常考。

解析：回溯沿一条路径走到底、再退回换路——正是 DFS 的搜索方式。✅ 正确

排除法：无（判断题）。混淆点：回溯强调"状态恢复"，DFS 强调"遍历顺序"，同一枚硬币的两面。

关联 · 回溯的复杂度（D7）：DFS 树的大小决定复杂度。

考点：全排列的数量（D4）。

大纲注：回溯在 NOI 2025 大纲中未单列条目，属 DFS 的枚举应用、初赛完善程序常考。

解析：$n$ 个不同元素的全排列 = $n!$；$n=3$ 时 $3! = 6$。正确答案 A。

排除法：B 是 $n$；C 是 $n^2$；D 是 $n(n+1)$ 的误解。

关联 · 全排列的个数（M2）：$n=4$ 时 $4! = 24$。

考点：子集的数量（D5）。

大纲注：回溯在 NOI 2025 大纲中未单列条目，属 DFS 的枚举应用、初赛完善程序常考。

解析：每个元素"选/不选"两种选择，独立相乘 → $2^n$；$n=3$ 时 $2^3 = 8$。正确答案 A。

排除法：B（$6$）是排列数；C 是元素个数；D 无依据。

关联 · 子集回溯计数（M3）：选/不选两个分支的代码。

考点：回溯与枚举的关系（D6）。

解析：回溯 = 枚举所有方案的通用框架：排列、组合、子集都是"选择 → 递归 → 撤销"同一个模板。✅ 正确

排除法：无（判断题）。混淆点：与第 11 章枚举相比，回溯多了"递归深入 + 状态恢复"，适合方案数随深度增长的问题。

关联 · 回溯三部曲（D2）：模板的三步。

大纲注：回溯在 NOI 2025 大纲中未单列条目，属 DFS 的枚举应用、初赛完善程序常考。

考点：回溯的复杂度（D7）。

大纲注：回溯在 NOI 2025 大纲中未单列条目，属 DFS 的枚举应用、初赛完善程序常考。

解析：回溯要遍历解空间：排列 $n!$、子集 $2^n$——指数级，规模一大就容易超时。✅ 正确

排除法：无（判断题）。混淆点：$n$ 稍大（排列 $n \geq 10$）回溯就撑不住，此时要换思路（数学计数、递推等）。

关联 · 回溯与枚举的关系（D6）：回溯的适用边界。

大纲注：回溯在 NOI 2025 大纲中未单列条目，属 DFS 的枚举应用、初赛完善程序常考。

考点：差分的思想（E1）。

解析：$d[i] = a[i] - a[i-1]$ 记录相邻差；区间 $[l, r]$ 加 $x$ 只需 d[l] += x、d[r+1] -= x——"头尾标记、前缀和还原"。✅ 正确

排除法：无（判断题）。混淆点：标记位置错一位（$r$ 与 $r+1$）区间就错——这是差分最高频的坑。

关联 · 前缀和（第 6 章 C 组）：差分是前缀和的逆运算。

考点：差分与前缀和的关系（E2）。

解析：差分与前缀和互为逆运算：前缀和数组的差分 = 原数组，差分数组的前缀和 = 原数组。✅ 正确

排除法：无（判断题）。混淆点：两者方向相反——前缀和"累加"，差分"做差"。

关联 · 差分的思想（E1）：逆运算关系是差分的根基。

考点：差分的应用场景（E3）。

解析："多次区间加、最后统一查询"用差分：每次修改 $O(1)$、还原 $O(n)$。✅ 正确

排除法：无（判断题）。混淆点：修改与查询交替进行的场景差分不适用（F5）。

关联 · 差分适用场景（F5）：适用边界的补充。

考点：倍增的思想（E4）。

解析：每次翻倍地跳（$1, 2, 4, 8, \dots$）：$O(n)$ 的逐步推进压缩成 $O(\log_2 n)$ 步。✅ 正确

排除法：无（判断题）。混淆点：倍增要求"能一次跳过 $2^k$ 步"——跳不动就减半再试。

关联 · 翻倍需要的次数（L3）：$2^{10} = 1024 \geq 1000$。

考点：快速幂与倍增（E5）。

解析：快速幂把指数按二进制拆成 $1, 2, 4, 8$ 次方，乘法次数 $O(b) \to O(\log_2 b)$——倍增思想的典型应用。✅ 正确

排除法：无（判断题）。混淆点：拆分的依据是"任何整数都能写成 2 的幂之和"（F7 的二进制拆分）。

关联 · 快速幂（N3）：代码版输出 $2^{10} = 1024$。

考点：倍增的复杂度（E6）。

解析：翻倍次数 = 对数级：$O(\log_2 n)$。✅ 正确

排除法：无（判断题）。混淆点：倍增类算法通常每步 $O(1)$ 或 $O(n)$ 预处理，总体仍远快于逐次推进。

关联 · 倍增的思想（E4）：复杂度的来源。

考点：差分数组的构造（F1）。

解析：$d[1] = a[1]$，$d[i] = a[i] - a[i-1]$——一遍 $O(n)$ 扫描构造。✅ 正确

排除法：无（判断题）。混淆点：下标从 1 起、$d$ 比 $a$ 多开一位（$d[r+1]$ 要能存）。

关联 · 差分数组构造输出（N1）：代码版。

考点：区间加的差分标记（F2）。

解析：区间 $[l, r]$ 加 $x$ = d[l] += x + d[r+1] -= x——头加尾减、两处标记。正确答案 A。

排除法：B 漏了"区间外抵消"的尾标记；C 方向反；D 缺尾标记区间会一直加到结尾。

关联 · 差分区间加输出（L1）：标记 + 还原的完整代码。

考点：差分还原成原数组（F3）。

解析：对差分数组求前缀和 = 还原原数组；$d[r+1]$ 处的反向标记让区间外自动抵消。✅ 正确

排除法：无（判断题）。混淆点：还原后的 $a[i]$ 是"所有经过 $i$ 的标记之和"。

关联 · 差分还原输出（L2）：还原过程的代码。

考点：差分的复杂度（F4）。

解析：$m$ 次修改 $O(1)$ + 一次还原 $O(n)$ → $O(n + m)$。正确答案 A。

排除法：B 是暴力法（每次修改扫区间）；C/D 无依据。

关联 · 差分与暴力对比（F6）：$10^5$ 规模下的差距。

考点：差分适用场景（F5）。

解析：修改集中、查询靠后 → 差分；修改查询频繁交替 → 差分不适用（每次查询都要 $O(n)$ 还原）。✅ 正确

排除法：无（判断题）。混淆点：交替场景需其他数据结构（提高级内容），CSP-J 只考"先改后查"。

关联 · 差分的应用场景（E3）：适用条件的两个说法。

考点：差分与暴力对比（F6）。

解析：$n = m = 10^5$：暴力 $O(nm) \approx 10^{10}$ 超时；差分 $O(n+m) \approx 10^5$ 级别。正确答案 A。

排除法：B 是暴力量级；C/D 无依据。

关联 · 差分的复杂度（F4）：量级差的来源。

考点：差分与前缀和综合（F7）。

解析：先差分做区间修改、再前缀和还原——区间批量操作的标准套路。✅ 正确

排除法：无（判断题）。混淆点：套路顺序不能反：先改（差分标记）后查（前缀和还原）。

关联 · 差分与前缀和综合输出（L5）：综合代码版。

考点：递归出口写在前面（G1）。

解析：先判断边界、再写递归调用——顺序反了会先递归、永远到不了出口。✅ 正确

排除法：无（判断题）。混淆点：出口条件要覆盖所有"最小情形"（如 $f(1)$、$f(2)$ 都写）。

关联 · 缺少边界条件（H1）：没出口 = 死递归。

考点：递归参数的设计（G2）。

解析：参数应随递归单调变化、向出口靠近（如区间 l, r 不断收缩、n 不断减小）。✅ 正确

排除法：无（判断题）。混淆点：参数不变化（或变化不向出口靠）就是死循环式递归。

关联 · 递归反转数组（J7）：l+1, r-1 双参数收缩。

考点：递推中的取模（G3）。

解析：加法/乘法满足 $(a+b) \bmod M = (a \bmod M + b \bmod M) \bmod M$——每步取模结果一致且防溢出。✅ 正确

排除法：无（判断题）。混淆点：除法没有这个性质（要逆元），CSP-J 阶段递推取模通常只涉及加减乘。

关联 · 递推取模（K6）：滚动 + 每步 % MOD。

考点：递归与递推的选择（G4）。

解析：递归直观但耗栈；深度可达 $10^5$ 以上、或追求常数时选递推。✅ 正确

排除法：无（判断题）。混淆点：把算过的结果缓存起来是折中——保留递归结构、去掉重复计算。

关联 · 递归深度与栈溢出（A5）：深度是选择的关键依据。

考点：递推结果的增长（G5）。

解析：斐波那契第 90 项约 $2.9 \times 10^{18}$，接近 long long 上限（$\approx 9.2 \times 10^{18}$）——递推前先估算结果范围选类型。✅ 正确

排除法：无（判断题）。混淆点：需要更大范围时按题目要求取模（G3），不是硬换更大的类型。

关联 · 递推中的取模（G3）：超范围的标准处理。

考点：缺少边界条件（H1）。

解析：没有出口 → 每层调用又产生调用 → 无限递归 → 栈溢出。正确答案 A。

排除法：B/C 是幻想；D——缺少出口不会"自动停一次"。

关联 · 缺边界的递归（P1）：f(n-1) 一路减到负无穷。

考点：指数爆炸的原因（H2）。

解析：$f(n-1)$ 与 $f(n-2)$ 的递归树里子问题大量重叠（同一 $f(k)$ 被算许多遍）——重复计算是 $O(2^n)$ 的根源。正确答案 A。

排除法：B 无依据；C——递归本身不比循环慢一个量级；D 是结果不是原因。

关联 · 斐波那契递归的重复计算（B3）：概念题与本题互为表里。

考点：return 的丢失（H3）。

解析：递归结果靠 return 逐层上传，丢一层就断链——上层拿到垃圾值。正确答案 A。

排除法：B 无依据；C——编译器不会自动补；D——能编译（P2 的行为未定义）。

关联 · 丢失 return 的递归（P2）：代码实证。

考点：递推初值写错（H4）。

解析：$f(2)$ 错成 1 后：$f(3) = f(2) + f(1) = 2$、$f(4) = f(3) + f(2) = 3$——初值错一处、后面全错。正确答案 A。

排除法：B（$5$）是正确初值的答案；C/D 是中间项。

关联 · 递推初值被覆盖（P4）：循环起点写错是同一类错误。

考点：递归递推综合判断（H5）。

解析：四句全部正确：递归与循环等价（A4）；递推把斐波那契降到 $O(n)$（C4）；回溯本质是 DFS（D3）；差分与前缀和互为逆运算（E2）。✅ 正确

排除法：无（判断题）。混淆点：这套概念是本章骨架，逐条对照前几组题目。

关联 · 递归基本概念（A1）：本章各组概念的总结。

考点：阶乘递归输出（I1）。

解析：$f(5) = 5 \times f(4) = 5 \times 4 \times 3 \times 2 \times 1 = 120$。正确答案 A。

实现要点：阶乘框架 = 出口 n == 0 返回 1 + return n * f(n-1)。手算：沿递归链把乘法展开成一条链。

排除法：B（24）是 $4!$；C（5）漏了递归；D（0）是出口值。

关联 · 阶乘的递归定义（B1）：概念题的代码实现。

考点：斐波那契递归输出（I2）。

解析：$f(7) = f(6) + f(5) = 8 + 5 = 13$。正确答案 A。

实现要点：斐波那契递归 = 双出口（n==1 || n==2 返回 1）+ f(n-1) + f(n-2)。手算从小往大列：1, 1, 2, 3, 5, 8, 13。

排除法：B（8）是 $f(6)$；C（21）是 $f(8)$；D（7）是参数本身。

关联 · 斐波那契的递推式（B2）：递推式即递归关系。

考点：递归求 1 到 n 的和（I3）。

解析：$s(100) = 100 + 99 + \cdots + 1 = 100 \times 101 / 2 = 5050$。正确答案 A。

实现要点：求和框架 = 出口 n == 1 + return n + s(n-1)。手算：展开成 $100 + 99 + \cdots + 1$，或直接套高斯公式核对。

排除法：B（4950）少加 100；C（100）只返回参数；D（5000）按 $100 \times 50$ 的误解。

关联 · 递归求数组和（B7）：同款结构作用在数组上。

考点：递归正序输出（I4）。

解析：先递归后打印 → 最深层（$n=1$）先打印 → 正序 1 2 3 4 5。正确答案 A。

实现要点：打印位置决定顺序：print 在递归之后 = 返回时打印 = 正序；在递归之前 = 进入时打印 = 逆序（I5）。手算：沿递归链看 print 的执行时机。

排除法：B 是逆序（print 在前）；C 只打印奇数；D 是每次打印参数。

关联 · 返回时打印的顺序（J2）：正序输出 = 返回序。

考点：递归逆序输出（I5）。

解析：先打印后递归 → 最先进入（$n=5$）先打印 → 逆序 5 4 3 2 1。正确答案 A。

实现要点：print 在递归之前 = 进入序（与 I4 镜像）。手算：进入一层打印一次。

排除法：B 是正序；C 打印参数 5 次（没递归）；D 打印奇数。

关联 · 进入时打印的顺序（J1）：逆序输出 = 进入序。

考点：递归求最大公约数（I6）。

解析：gcd(48, 36) = gcd(36, 12) = gcd(12, 0) = 12。正确答案 A。

实现要点：辗转相除递归 = 出口 b == 0 返回 a + g(b, a % b)。手算：连续取模，直到余数为 0。

排除法：B（6）是 $48$ 和 $30$ 的 gcd；C（4）无依据；D（24）是 $48$ 的约数但不是 gcd。

关联 · 辗转相除求最大公约数（B6）：递归结构的经典。

考点：递归求奇数和（I7）。

解析：$1 + 3 + 5 + 7 + 9 = 25$。正确答案 A。

实现要点：递归框架 = 出口 n == 0 + 分支（奇数加自己、偶数跳过）+ s(n-1)。手算：$s(10) = 9 + 7 + 5 + 3 + 1 = 25$。

排除法：B（30）是偶数和的误解；C（55）是 $1\sim10$ 总和；D 无依据。

关联 · 递归求 1 到 n 的和（I3）：同框架加奇偶判断。

考点：进入时打印的顺序（J1）。

解析：进入即打印：f(3) 打 3 → f(2) 打 2 → f(1) 打 1 → f(0) 返回 → 输出 3 2 1。正确答案 A。

实现要点：递归序 = 先序（进入序）。手算：按"进入一层打一层"往下写，遇出口回退。

排除法：B 是返回序；C 无依据；D 多打了 0（f(0) 直接 return 不打印）。

关联 · 递归逆序输出（I5）：同一写法。

考点：返回时打印的顺序（J2）。

解析：返回才打印：最深层先回、先打 → 1 2 3。正确答案 A。

实现要点：递归序 = 后序（返回序）。手算：一路进到底（不打），从最深处往回逐层打印。

排除法：B 是进入序；C/D 无依据。

关联 · 递归正序输出（I4）：同一写法。

考点：递归树的输出（J3）。

解析：f(3) 打 3 → 左 f(1) 打 1 → 右 f(2) 打 2 → 其左 f(0) 返回 → 其右 f(1) 打 1 → 输出 3 1 2 1。正确答案 A。

实现要点：双分支递归 = 深度优先遍历递归树：先走完左子树再走右子树。手算：画树（3 → 左 1 / 右 2 → 左 0 / 右 1），按 DFS 先序读出。

排除法：B 漏了 f(2) 的左子返回前的打印；C 是返回序；D 多打一个 1。

关联 · 回溯与深度优先搜索（D3）：递归树遍历 = DFS。

考点：递归调用次数（J4）。

解析：f(5) → f(4) → f(3) → f(2) → f(1) → f(0)，共进入 6 次。正确答案 A。

实现要点：计数 = 在函数入口 cnt++。手算：数递归链上的节点数（含出口那层）。

排除法：B（5）漏了 f(0)；C（15）是斐波那契型重复调用；D 无依据。

关联 · 递归调用次数（P5 对照）：斐波那契型调用次数指数增长。

考点：递归深度统计（J5）。

解析：最深链 f(5) → f(4) → f(3) → f(2) → f(1) → f(0)，共 6 层。正确答案 A。

实现要点：深度 = 进入 dep++、离开 dep--，用 mx 记录峰值。手算：递归链上最长的路径长度。

排除法：B（5）漏数出口层；C 少两层；D 多一层。

关联 · 递归的执行过程（A3）：深度 = 栈的峰值高度。

考点：递归打印二进制（J6）。

解析：$13 = 1101_2$：f(13)→f(6)→f(3)→f(1)→f(0)，返回时依次打 1 1 0 1 → 1101。正确答案 A。

实现要点：进制转换 = 先递归 f(n/2)、返回时打 n % 2（先高位后低位）。手算：除 2 取余，余数倒着读。

排除法：B（1011）是余数正着读；C（111）漏了 0；D（13）没转换。

关联 · 返回时打印的顺序（J2）：后序打印实现"倒读余数"。

考点：递归反转数组（J7）。

解析：交换两端、递归中间：1↔6, 2↔5, 3↔4 → 6 5 4 3 2 1。正确答案 A。

实现要点：反转框架 = 出口 l >= r + swap(a[l], a[r]) + rev(l+1, r-1)。手算：两端指针逐步靠拢。

排除法：B 是原数组；C 只换了一次；D 交换次序错。

关联 · 递归参数的设计（G2）：双参数收缩的示范。

考点：斐波那契递推输出（K1）。

解析：正向填表：1, 1, 2, 3, 5, 8, 13, 21, 34, 55 → $f(10) = 55$。正确答案 A。

实现要点：递推框架 = 初始值 + for 填表。手算：一行行写出数组，直到目标项。

排除法：B（34）是 $f(9)$；C（89）是 $f(11)$；D（21）是 $f(8)$。

关联 · 递推的循环实现（C7）：填表法的范本。

考点：爬楼梯递推输出（K2）。

解析：$f(3)=3, f(4)=5, f(5)=8, f(6)=13$。正确答案 A。

实现要点：爬楼梯 = 斐波那契的初值变体（$f(1)=1, f(2)=2$）。手算：递推填表。

排除法：B（8）是 $f(5)$；C（21）是 $f(7)$；D（5）是 $f(4)$。

关联 · 爬楼梯问题（C6）：概念题代码化。

考点：循环求阶乘（K3）。

解析：$1 \times 2 \times \cdots \times 6 = 720$。正确答案 A。

实现要点：循环版阶乘 = 累乘器 s *= i。手算：从 1 乘到 6。

排除法：B（120）是 $5!$；C（5040）是 $7!$；D（6）没乘。

关联 · 递归与循环的转换（A4）：阶乘的循环写法。

考点：递推前缀和（K4）。

解析：s[i] = s[i-1] + a[i-1]：3, 4, 8, 9, 14。正确答案 A。

实现要点：前缀和框架 = s[i] = s[i-1] + a[i-1]（1 下标）。手算：逐项累加。

排除法：B 是原数组；C 是后缀和；D 是 $s[i] = s[i-1] + i$ 的误解。

关联 · 递推的定义（C1）：前缀和是最常用的递推。

考点：杨辉三角的递推（K5）。

解析：$c[i][j] = c[i-1][j-1] + c[i-1][j]$，第 5 行 = 1 5 10 10 5 1。正确答案 A。

实现要点：杨辉三角 = 边界两边 1 + 上方两数相加。手算：逐行填表，第 $i$ 行有 $i+1$ 个数。

排除法：B 是第 4 行；C 漏一个 10；D 漏两边的 1。

关联 · 递推的三要素（C3）：二维递推的代表。

考点：递推取模（K6）。

解析：滚动变量求 $f(8) = 21$，每步 % MOD（结果未超模，值不变）。正确答案 A。

实现要点：滚动 + 取模 = c = (a + b) % MOD; a = b; b = c;——$O(n)$ 时间 $O(1)$ 空间。手算：只跟两个变量走。

排除法：B（13）是 $f(7)$；C（34）是 $f(9)$；D（55）是 $f(10)$。

关联 · 递推中的取模（G3）：防溢出的标准操作。

考点：差分区间加输出（L1）。

解析：d[1] += 2、d[4] -= 2，前缀和还原 → 2 2 2 0 0。正确答案 A。

实现要点：差分三步 = 头标记 + 尾标记 + 前缀和还原。手算：逐位累加 $d$ 的前缀和。

排除法：B 区间位置错；C 缺尾标记；D 方向反。

关联 · 区间加的差分标记（F2）：概念题的代码版。

考点：差分还原输出（L2）。

解析：d[1] = 1、d[3] = -1 = 区间 $[1,2]$ 加 1，还原 → 1 1 0 0 0。正确答案 A。

实现要点：还原 = 边累加边输出。手算：$1, 1+0, 1+0-1, \dots$。

排除法：B 是没还原的差分数组；C 缺尾标记；D 无依据。

关联 · 差分还原成原数组（F3）：概念题的代码版。

考点：翻倍需要的次数（L3）。

解析：$1 \to 2 \to \cdots \to 1024$，翻倍 $10$ 次达到 $\geq 1000$。正确答案 A。

实现要点：倍增计数 = x *= 2 + 计数循环。手算：$2^{10} = 1024 \geq 1000$。

排除法：B（9）是 $2^9 = 512$（未到）；C 是阈值；D 多一次。

关联 · 倍增的思想（E4）：对数级的直观验证。

考点：二进制拆分输出（L4）。

解析：$13 = 1101_2 = 8 + 4 + 1$ → 1 4 8。正确答案 A。

实现要点：拆分 = n & 1 判断该位 + n >>= 1 移位 + p <<= 1 位权翻倍。手算：逐位看二进制。

排除法：B 是逆序；C 多拆了 2；D 是原数。

关联 · 快速幂与倍增（E5）：拆分是快速幂的底层。

考点：差分与前缀和综合输出（L5）。

解析：两次区间加叠加后还原：$a = 1, 4, 3, 3, 0$ → 1 4 3 3 0。正确答案 A。

实现要点：多次标记全部累加后再统一还原——先改后查。手算：$d = 1, 3, -1, 0, -3$，前缀和 $1, 4, 3, 3, 0$。

排除法：B 漏了第二个区间的首标记；C 起点错；D 尾标记错。

关联 · 差分与前缀和综合（F7）：综合套路的代码版。

考点：全排列回溯计数（M1）。