◎学完你会
- 看懂汉诺塔的规则：大盘不能压小盘、一次只移一片；
- 用递归三步（搬走 n-1 → 移大盘 → 搬回 n-1）写出
hanoi 函数，并说清每个参数为什么那样传；
- 会算最少步数 2n−1，会区分两处
cout 各执行几次（2n−1 与 2n−1−1），体会"指数爆炸"：12 层就要 4095 步。
1汉诺塔：三根柱、一盘不能压小盘
目标：把 A 柱上从小到大叠好的 n 个盘，全部移到 C 柱。规则只有两条：① 每次只能移动一片；② 任何时刻大盘不能压在小盘上面（可用 B 柱中转）。
递归三步（把"n 个盘从 A 移到 C"拆开）：
① 搬走：把上面 n-1 片，从 A 借 C 移到 B（这是同一问题的更小版）——递归调用①。
② 移大盘：把最底下第 n 片，直接从 A 移到 C——一次普通移动。
③ 搬回：把 B 上的 n-1 片，借 A 移到 C——递归调用②。
已走 0 / 0 步
递归深度 0
—
点"单步"开始，观察每一步移动与右侧代码行同步高亮。
换层数会重置动画。建议 3~5 层配"慢"速看清规律；8 层以上改用"极速"体会指数爆炸（12 层共 4095 步）。
2递归代码：三步一对应
void hanoi(int n, char from, char via, char to){
if(n==1){ cout<<from<<"->"<<to<<endl; return; } // 出口：只剩 1 片，直接移
hanoi(n-1, from, to, via); // ① 把上面 n-1 片搬到 via（借 to）
cout<<from<<"->"<<to<<endl; // ② 把第 n 片搬到 to
hanoi(n-1, via, from, to); // ③ 把 n-1 片搬回 to（借 from）
}
| 递归三步 | 代码位置 | 做了什么 |
|---|
| ① 搬走 n-1 | hanoi(n-1, from, to, via) | 先把上面的 n-1 片挪到中转柱（via） |
| ② 移大盘 | cout << from << "->" << to | 最底下大盘直接去目标柱（to） |
| ③ 搬回 n-1 | hanoi(n-1, via, from, to) | 把中转柱上的 n-1 片再挪到目标柱 |
关键在参数互换：hanoi(n-1, from, to, via) 里，via 和 to 换了位置——因为"目标"变成了中转柱。写错这一行是汉诺塔最常见的错。
3最少几步？T(n) = 2·T(n-1) + 1
要移 n 个盘：先花 T(n-1) 步搬走 n-1 片，再 1 步移大盘，再 T(n-1) 步搬回。所以 T(n) = 2·T(n-1)+1，且 T(1)=1。解出来就是 2n−1。
| 层数 n | 最少步数 2ⁿ−1 | 层数 n | 最少步数 2ⁿ−1 |
|---|
| 3 | 7 | 8 | 255 |
| 4 | 15 | 9 | 511 |
| 5 | 31 | 10 | 1023 |
| 6 | 63 | 11 | 2047 |
| 7 | 127 | 12 | 4095 |
两个 cout 各执行几次？（常考）
代码里有两处 cout：出口行（n==1 时单盘直移）和 ② 行（移大盘）。次数不一样：
| 代码行 | 执行次数 | 为什么 |
|---|
| 出口行 L2 | 2n−1 | 递归树有 2n−1 个叶子；每片盘最终都由某个 n==1 的调用搬走 |
| ② 移大盘 L4 | 2n−1−1 | 只在非叶子调用里执行，每个非叶子调用一次 |
| 合计 | 2n−1 | = T(n)，与最少步数吻合 |
别把 ② 行的次数当成 n：n=3 时 ② 行恰好执行 3 次，很容易误以为"n 层就 n 次"。实际 n=4 是 7 次（2³−1）、n=5 是 15 次——它同样是指数增长，只是比总步数少一半。n=3 那个"3"纯属巧合。
每加一层，步数翻倍还多 1：从 11 层到 12 层，一下子多了 2048 步。这就是递归深度的代价——能用递推/循环解决的大 n 问题，别硬递归（见 14.2 递归改递推）。
!易错点
坑 1 · 中转柱传错（最隐蔽）：函数签名顺序是 (n, from, via, to)。① 行正确写法 hanoi(n-1, from, to, via)——第 2、3 个实参相对签名调换了位置，因为这一层的"目标柱"变成了下一层的"中转柱"。常见错是原样传：hanoi(n-1, from, via, to)。
本机实测后果（g++ 15.2，n=3）：仍输出 7 步——步数看着完全正常，但第 2 步就把盘 2 压到盘 1 上，全程 6 次非法移动，最终 C 柱自下而上是 [1,2,3]（小盘在底）。步数对 ≠ 结果对，这个错光看输出行数发现不了。
记法：① 行调 via↔to，③ 行调 from↔via（hanoi(n-1, via, from, to)——这一层的中转柱变成下一层的起始柱）。
坑 2 · 出口写错：分两种情况，后果完全不同：
① 压根没写出口 → 递归永不停止，栈溢出崩溃（RE）。本机实测确认：无出口的 hanoi(1,...) 直接崩（退出码 0xC00000FD）。
② 出口写成 n==0 → 不会崩溃，但结果错。因为递归调的是 n-1，一路减到 0 仍能触发出口。本机实测 n=3 输出 15 步（应为 7 步），且第 8 步在源柱已空时还要移盘。
③ 真正会无限递归的是：出口 n==1，却从 n=0 或负数开始调用——永远碰不到出口。
写完先确认：出口条件能被实际调用命中。
坑 3 · 少搬最后一步：只写 ① ②，忘了把中转柱上的 n-1 片搬回（③）。结果大盘到了 C，但上面的盘全丢在 B。三步缺一不可。
坑 4 · 深递归爆栈：递归深度 = n，每层一个栈帧。本机实测（g++ 15.2 / Windows 默认栈）：深度 4 万层还能过，4.5 万层就溢出崩溃。⚠️ 这个阈值依赖环境和栈大小，OJ 上不一样，别当固定数字背——只需记住"深度上万就要警惕"。
另外汉诺塔还有个更早的拦路虎：输出量本身是 2n−1 行，本机实测 n=20 就要打印 1,048,575 行——没等爆栈就先被输出淹了。汉诺塔当理解递归的玩具，真实工程遇到"递推能解"的问题优先用循环（见 14.2 递归改递推）。
✎练一练
1. 汉诺塔的移动规则中，哪一条必须遵守？
选 B。汉诺塔两条铁律：一次只移一片 + 大盘不能压小盘。B 正确；A 违反"一次一片"，C 把 B 柱当摆设了（B 是中转柱），D 是次数混淆（最少是 2ⁿ−1，不是 2ⁿ）。
2. 递归解决汉诺塔"n 个盘从 A 移到 C"时，第一步应该做什么？
选 C。大盘要去 C，必须先给它"腾地方"——把上面的 n−1 个盘先搬到中转柱 B（递归三步第①步）。先移大盘会压到 C 上的小盘，违规。
3. 4 层汉诺塔最少需要几步？
选 B。最少步数 = 2⁴−1 = 15。T(4)=2·T(3)+1=2·7+1=15。A 是 3 层的 7 步，C 是 2⁴（少减 1），D 是 5 层的 31 步。
4. 看代码：hanoi(3,'A','B','C') 第一行会先调用下面哪一个？
选 A。第一句是 hanoi(n-1, from, to, via)，代入 n=3、from=A、to=C、via=B 得 hanoi(2,'A','C','B')——把上面 2 片从 A 搬到 B（经 C）。这是"搬走 n−1"那一步。
5. 运行 hanoi(4,'A','B','C')，程序里 ② 移大盘那行（cout<<from<<"->"<<to，非出口行）会被执行几次？
选 D（24−1−1 = 7 次）。② 行只在非叶子调用里执行一次，次数 = 2n−1−1。A 是最典型的陷阱：n=3 时 ② 行恰好执行 3 次，很容易误以为"n 层就 n 次"，但 n=4 是 7 次、n=5 是 15 次——它同样是指数增长，n=3 那个"3"纯属巧合。B（8 次）是出口行的执行次数 2n−1；C（15 次）是总移动 2⁴−1。验算：出口行 8 次 + ② 行 7 次 = 15 次 = 总移动，对得上。
✦跨学科：指数爆炸 · 神话里的"世界末日"
梵天寺僧侣的传说：把 64 片金盘移完，世界就到末日。若每移一片用 1 秒，总共要 2⁶⁴−1 = 18,446,744,073,709,551,615 秒 ≈ 5849 亿年——是宇宙年龄（约 138 亿年）的 42 倍还多。
这就是指数增长：n 只加了 1，工作量却翻倍。生物学里同样的规律触手可及——大肠杆菌在最适条件（37 ℃、富营养、通气）下最短约 20 分钟分裂一代，40 代（约 13.3 小时）后 1 个细胞变成 2⁴⁰ ≈ 1.1 万亿个；细胞分裂、病毒增殖都是这个模式。一开始不起眼，后面爆得措手不及。
算法题里看到指数复杂度（如 2ⁿ），第一反应就该是：这个规模撑不住，得找更聪明的办法。
数字来源：宇宙年龄 138 亿年取自 Planck 2018 宇宙学参数结果（ΛCDM 模型）；大肠杆菌最短代时约 20 min 见 Harvard BioNumbers #103514（Sezonov et al., E. coli physiology）。5849 亿年、42 倍、1.1 万亿、13.3 小时均为本机复算。