汉诺塔解法与递归思维

汉诺塔是经典的递归益智游戏，也是理解「分而治之」思维的最佳入门。

规则

有三根柱 A、B、C，A 柱上从大到小叠 n 个圆盘，目标是把所有盘移到 C；每次只能移动一个盘，且大盘不能压小盘。

递归解法

核心思路：把「移动 n 个盘」拆成

1. 先把上面 n−1 个盘从 A 移到 B（借助 C）；
2. 把最大盘从 A 移到 C；
3. 再把 n−1 个盘从 B 移到 C（借助 A）。

最小子问题 n=1 直接移动。这一「大事化小」正是递归：函数调用自身处理更小的同构问题。

步数与拓展

n 盘最少需 2^n−1 步。汉诺塔的意义在于训练把大问题化小的抽象能力，也是理解计算机递归与栈结构的入门范例，许多算法教材都拿它当第一个例子。