递归思想与专项突破
“要理解递归,首先要理解递归。”递归不仅是一种函数编写手法,更是计算机科学中最具威力的分治建模哲学。本模块将通过调用栈模拟与可操作的汉诺塔沙盒,彻底打通你的递归直觉!
3.2 递归的两大铁律与“俄罗斯套娃”模型
什么是递归?递归就是一个大问题由若干个结构完全相同、但规模更小的子问题构成。想象打开一个大俄罗斯套娃,里面是一个小一号的套娃;继续打开,直到看见最里面那个实心的最小娃娃。
必须有明确的“递归基”(Base Case)
递归基是递归停下来的出口边界。如果缺少递归基,或者递归参数没有向着递归基收敛,函数就会无休止地无限调用自己,导致系统内存耗尽(栈溢出 Stack Overflow)。
if (n == 0 || n == 1) return 1; // 递归出口!
必须有严格向出口收敛的“递推关系”
每次自我调用时,传递给子问题的参数规模必须严格缩小(如 n - 1 或 n / 2),确保在有限步内必然能够触碰到递归基。
return n * fact(n - 1); // 规模从 n 缩减为 n - 1
3.3 函数调用栈(Call Stack)与回溯生命周期
在计算机内部,递归并不是神话,而是依赖一种名为栈(Stack)的数据结构管理的物理流程:
🔄 递归调用的完整生命周期:压栈(Push)与 出栈(Pop)
分段递推递归函数求 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 柱上,大盘必须在下,小盘必须在上。每次只能移动一个盘子,且任何时候都不能让大盘压在小盘上方。
汉诺塔可操作试玩与自动演练场
📐 汉诺塔三步走递归推导与通项公式
假设要将 n 个盘子从 A 柱借助 B 柱搬运到 C 柱,记最少步数为 H(n):
递推方程: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 经典递推真题:斐波那契求和与平面切分
斐波那契数列前 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。完全吻合!
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题)
• 当 x ≥ 10 时,F(x) = x - 3;
• 当 x < 10 时,F(x) = F(x + 4) + 1。
请问 F(4) 的计算结果是多少?( )
展开追踪: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。
由累加消元法:S_n = F(n + 2) - F(2) = F(n + 2) - 1。故选 D。
分割公式 R(n) = 1 + n(n + 1) / 2。代入 n = 10 得 1 + 55 = 56 个区域。故选 C。
将上面 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。
int gcd(int a, int b) {
while (b != 0) {
__________;
}
return a;
}
根据 gcd(a, b) = gcd(b, a % b),新 a 应为旧 b,新 b 应为旧 a % b。必须用临时变量保存旧 b,因此选择 C:int temp = b; b = a % b; a = temp;。故选 C。