模块 03 · 重难点专项

递归思想与专项突破

“要理解递归,首先要理解递归。”递归不仅是一种函数编写手法,更是计算机科学中最具威力的分治建模哲学。本模块将通过调用栈模拟与可操作的汉诺塔沙盒,彻底打通你的递归直觉!

3.2 递归的两大铁律与“俄罗斯套娃”模型

什么是递归?递归就是一个大问题由若干个结构完全相同、但规模更小的子问题构成。想象打开一个大俄罗斯套娃,里面是一个小一号的套娃;继续打开,直到看见最里面那个实心的最小娃娃。

铁律 1

必须有明确的“递归基”(Base Case)

递归基是递归停下来的出口边界。如果缺少递归基,或者递归参数没有向着递归基收敛,函数就会无休止地无限调用自己,导致系统内存耗尽(栈溢出 Stack Overflow)。

if (n == 0 || n == 1) return 1; // 递归出口!
铁律 2

必须有严格向出口收敛的“递推关系”

每次自我调用时,传递给子问题的参数规模必须严格缩小(如 n - 1 或 n / 2),确保在有限步内必然能够触碰到递归基。

return n * fact(n - 1); // 规模从 n 缩减为 n - 1

3.3 函数调用栈(Call Stack)与回溯生命周期

在计算机内部,递归并不是神话,而是依赖一种名为栈(Stack)的数据结构管理的物理流程:

🔄 递归调用的完整生命周期:压栈(Push)与 出栈(Pop)

阶段一:递推压栈(Push)
当函数调用自己时,操作系统会开辟一个崭新的栈帧(Stack Frame),把当前的局部变量、参数以及函数执行到的代码行号(返回地址)打包“压入栈底”。函数层层向下钻取,调用栈高度不断增加。
阶段二:触底反弹(Base Case)
最深层函数触碰到递归基条件,此时不再向下调用,而是第一次直接返回一个具体的确定值(如 1 或 0)。
阶段三:回溯出栈(Pop)
外层函数从等待中苏醒,接收到内层函数的返回值,继续完成自己的后续计算,随后释放自己的栈帧并“弹出调用栈”。直到最外层最初的主函数拿到最终答案。
真题直击 · 2025 第13题

分段递推递归函数求 F(4) 的压栈回溯过程

数列 F(x) 满足:x ≥ 10 时 F(x) = x - 3;x < 10 时 F(x) = F(x + 4) + 1。求 F(4)。

调用步骤 当前函数帧 条件判断 展开表达式 调用栈状态(从底到顶)
Step 1 (压栈) F(4) 4 < 10 等待 F(8) + 1 [ F(4) ]
Step 2 (压栈) F(8) 8 < 10 等待 F(12) + 1 [ F(4), F(8) ]
Step 3 (触底) F(12) 12 ≥ 10 (基) 立即返回 12 - 3 = 9 [ F(4), F(8), F(12) ]
Step 4 (回溯) F(8) 出栈 接收到 9 F(8) = 9 + 1 = 10 [ F(4) ]
Step 5 (出栈) F(4) 出栈 接收到 10 F(4) = 10 + 1 = 11 栈空,输出最终结果 11

3.4 汉诺塔(Towers of Hanoi)互动演练沙盒

汉诺塔是人类数学史上最经典的递归模型。规则:有三根柱子 A、B、C。初始时若干大小不等的圆盘穿在 A 柱上,大盘必须在下,小盘必须在上。每次只能移动一个盘子,且任何时候都不能让大盘压在小盘上方。

互动实验 02

汉诺塔可操作试玩与自动演练场

已移动步数:0 步(3 盘理论最少步数:7 步)
💡 点击柱子可以手动搬运盘子(先点源柱子选择顶盘,再点目标柱子放置)。试试看能不能在 7 步内完成!

📐 汉诺塔三步走递归推导与通项公式

假设要将 n 个盘子从 A 柱借助 B 柱搬运到 C 柱,记最少步数为 H(n):

第一步
将上面 n - 1 个盘子从 A 柱搬到 B 柱(借助 C 柱),共需要 H(n - 1) 步;
第二步
将 A 柱上剩下的唯一最大盘(第 n 个盘)直接一步移到 C 柱,需要 1 步;
第三步
将 B 柱上的 n - 1 个盘子搬到 C 柱(借助 A 柱),共需要 H(n - 1) 步。

递推方程:H(n) = 2 · H(n - 1) + 1,且 H(1) = 1。
两边加 1 得:H(n) + 1 = 2(H(n - 1) + 1),因此数列 {H(n) + 1} 是首项为 2、公比为 2 的等比数列!
封闭通项公式:H(n) = 2ⁿ - 1。(n = 3 时步数为 2³ - 1 = 7 步;n = 4 时步数为 2⁴ - 1 = 15 步)

3.5 经典递推真题:斐波那契求和与平面切分

真题直击 · 2025 第14题

斐波那契数列前 n 项和 S_n 表达式

F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)。求 S_n = F(1) + ... + F(n)。

移项错位相消法:
由 F(k) = F(k + 2) - F(k + 1),累加展开:
F(1) = F(3) - F(2)
F(2) = F(4) - F(3)
F(3) = F(5) - F(4)
...
F(n) = F(n + 2) - F(n + 1)
上下相加,中间所有项正负相消,得到:
S_n = F(n + 2) - F(2) = F(n + 2) - 1。
验算 n=3:S_3 = 1+1+2=4,F(5)-1 = 5-1=4。完全吻合!
真题直击 · 2025 第26题

10 条直线最多分割平面区域数

平面上 10 条两两相交且无三线共点的直线,最多把平面分割为几个区域?

增量递推法:
• 0 条线:1 个区域;
• 第 1 条线:增加 1 个区域(共 2 个);
• 第 2 条线:与第 1 条线交于 1 点,被分为 2 段,增加 2 个区域(共 4 个);
• 第 n 条线:与前面 n - 1 条线产生 n - 1 个交点,被分成 n 段,每段切出一个新区域,即:R(n) = R(n - 1) + n。
通项公式:R(n) = 1 + n(n + 1) / 2。
代入 n = 10:1 + 10 × 11 / 2 = 1 + 55 = 56 个区域。
课后强化测验

模块三 · 全真过关检测(共5题)

第 1 题 2025海淀第二赛段真题第13题 4 分
定义在整数集合上的递归函数 F(x) 满足:
• 当 x ≥ 10 时,F(x) = x - 3;
• 当 x < 10 时,F(x) = F(x + 4) + 1。
请问 F(4) 的计算结果是多少?( )
A. 9
B. 10
C. 11
D. 12
【解题精析】
展开追踪:F(4) = F(8) + 1 = (F(12) + 1) + 1。
由于 12 ≥ 10,触碰递归基:F(12) = 12 - 3 = 9。
回溯出栈:F(8) = 9 + 1 = 10;F(4) = 10 + 1 = 11。故选 C。
第 2 题 2025海淀第二赛段真题第14题 4 分
斐波那契数列定义为:F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2) (n ≥ 2)。若用 S_n 表示其前 n 项之和(即 S_n = F(1) + F(2) + ... + F(n)),那么 S_n 等于( )。
A. F(n + 1)
B. F(n + 2)
C. F(n + 1) - 1
D. F(n + 2) - 1
【解题精析】
由累加消元法:S_n = F(n + 2) - F(2) = F(n + 2) - 1。故选 D。
第 3 题 2025海淀第二赛段真题第26题 4 分
在平面上画 10 条直线,任意两条直线都相交且没有三条直线交于同一点。这 10 条直线最多可以把平面分割为( )个区域。
A. 46
B. 55
C. 56
D. 67
【解题精析】
分割公式 R(n) = 1 + n(n + 1) / 2。代入 n = 10 得 1 + 55 = 56 个区域。故选 C。
第 4 题 算法思维核心题 4 分
汉诺塔问题中,将 n 个盘子从柱子 A 借助柱子 B 移动到柱子 C。若记移动 n 个盘子的最少步数为 H(n),根据经典分治递推策略,下列关于 H(n) 的递推式和通项公式正确的是( )。
A. H(n) = H(n - 1) + 1,通项为 n
B. H(n) = 2 · H(n - 1) + 1,通项为 2ⁿ - 1
C. H(n) = 2 · H(n - 1),通项为 2ⁿ
D. H(n) = 3 · H(n - 1) - 1,通项为 3ⁿ - 2
【解题精析】
将上面 n-1 个盘移到 B(H(n-1) 步),最大盘移到 C(1 步),再将 n-1 个盘从 B 移到 C(H(n-1) 步)。递推式 H(n) = 2·H(n-1) + 1,通项 H(n) = 2ⁿ - 1。故选 B。
第 5 题 2025海淀第二赛段真题第18题衍生 4 分
以下是用 C++ 实现求两个正整数 a 与 b 的最大公因数的函数。若采用递推迭代写法,在横线处填入( )可以正确完成两数更新。
int gcd(int a, int b) {
    while (b != 0) {
        __________;
    }
    return a;
}
A. int temp = b; b = a / b; a = temp;
B. int temp = a; a = b / a; b = temp;
C. int temp = b; b = a % b; a = temp;
D. b = a % b; a = b;
【解题精析】
根据 gcd(a, b) = gcd(b, a % b),新 a 应为旧 b,新 b 应为旧 a % b。必须用临时变量保存旧 b,因此选择 C:int temp = b; b = a % b; a = temp;。故选 C。

恭喜攻克递归专项!

接下来将进入计算机数据管理的核心:数据结构进阶应用(二维数组与栈队列)。

前往模块四:数据结构进阶 →