分治策略解决汉诺塔问题的本质是将移动n个盘的大任务分解为两个n−1盘子问题加一次单盘移动，通过动态切换柱子角色实现递归求解。
分治策略解决汉诺塔问题，本质是把“移动 n 个盘”这个大任务，拆成三个结构相同、规模更小的子任务，并利用中间柱灵活切换角色。它不靠穷举，而靠逻辑递推——只要理解清楚每一步在“让路”和“归位”，代码就自然浮现。
分治三步：拆解、递归、合并
分治不是抽象概念，而是可操作的三步动作：
- 分解：把 n 个盘的问题，拆成两个 n−1 盘子问题 + 一个单盘移动。关键在于明确哪根柱是当前“目标”，哪根是“辅助”——它们的角色随递归深度动态互换。
- 解决：当只剩 1 个盘时，直接移动（终止条件）。这是唯一真正执行物理操作的环节，其余全是调度逻辑。
- 合并：不是数学加法，而是动作顺序的衔接——先腾空底座（n−1 盘移走），再落定最大盘，最后把 n−1 盘叠上去。三段动作天然构成完整解。
柱子角色动态切换是核心细节
很多人卡在参数顺序（如 hanoi(n-1, A, C, B) 中为什么是 C 和 B），其实就是在记“谁是辅助”。记住这个逻辑：
- 要从 A 移到 C，B 是辅助 → 第一步要把上面 n−1 个盘从 A 借助 C 暂存到 B → 所以调用 hanoi(n-1, A, B, C)
- 最大盘从 A 直达 C → 打印或记录这一步
- 再把 B 上的 n−1 个盘，借助 A 移到 C → 调用 hanoi(n-1, B, C, A)
每次递归调用中，“源”“目标”“辅助”三者重新绑定，不是固定对应 A/B/C 字母，而是由当前任务决定。
最小规模必须能直接解
分治有效，前提是存在无需再分的原子操作。对汉诺塔来说，就是 n = 1：
- 此时无需腾挪，不涉及任何辅助柱，直接源→目标
- 这一层不调用自身，递归栈开始回退
- 若遗漏该终止条件，程序会无限递归直至栈溢出
总步数可严格推导，验证分治正确性
设 T(n) 表示移动 n 个盘的最少步数：
- T(1) = 1
- T(n) = 2×T(n−1) + 1（两次 n−1 操作 + 一次最大盘移动）
- 解得 T(n) = 2ⁿ − 1 —— 这个闭式解，正是分治结构成立的数学证据
运行时打印每一步，你会发现：前 2ⁿ⁻¹−1 步负责把上层搬离；第 2ⁿ⁻¹ 步是底盘落位；后 2ⁿ⁻¹−1 步完成上层归位——完全符合分治的三段式节奏。
