汉诺塔（递归思想）

知识点 · 要点

• 规则：每次只移动一个圆盘，大盘不能放在小盘上。
• 移动 n 个盘最少需要 2ⁿ − 1 步。
• 递归思路：先把 n−1 个移到中转柱，移最大盘，再把 n−1 个移过来。
• 盘数与步数：3 个 7 步，4 个 15 步，5 个 31 步。

拓展延伸

• 传说 64 个金盘移完需要 2⁶⁴−1 步，即使每秒移动一次也要约 5850 亿年。
• 递归是一种「把大问题拆成同类小问题」的思想，是算法设计的核心方法之一。