C++ 递归经典:汉诺塔问题详解
问题描述
汉诺塔(Tower of Hanoi)是递归算法中最经典的入门案例之一。题目通常描述为:有三根柱子 A、B、C,A 柱上有 n 个大小不同的圆盘,从小到大叠放。要求将 A 柱上的所有盘子移动到 C 柱上,移动过程中需遵守以下规则:
- 每次只能移动一个盘子;
- 大盘子不能放在小盘子上面。

核心思路
面对这个问题,直接思考如何一次性移动 n 个盘子会非常复杂。作为工程师,我们习惯化繁为简,从最简单的情况入手找规律。
- 当 n = 1 时:只有一个盘子,直接从 A 移到 C 即可。
- 当 n = 2 时:需要借助 B 柱。先把上面的小盘移到 B,再把大盘移到 C,最后把小盘从 B 移到 C。
- 当 n > 2 时:我们可以利用 n=2 时的策略。假设我们要把 A 上的 n 个盘子移到 C,可以拆解为三步:
- 将 A 上方的 n-1 个盘子借助 C 移到 B(此时最大的盘子在 A 底部不动);
- 将 A 中剩下的最大盘子直接移到 C;
- 将 B 上的 n-1 个盘子借助 A 移到 C。
这里的关键在于理解递归的'黑盒'特性:当我们调用函数去处理 n-1 个盘子时,不需要关心它内部具体怎么移,只需要知道它能完成'把一堆盘子从起点移到终点'这个任务即可。同时要注意,步骤 3 中的'起点'其实是步骤 1 中的'终点'(B 柱),而'辅助柱'则是 A 柱。

算法流程
基于上述分析,我们可以设计一个递归函数 dfs。它的职责是将指定数量的盘子从源柱子移动到目标柱子,并指定一个辅助柱子。
- 终止条件:如果当前只需移动 1 个盘子(n=1),直接将其从源柱子弹出并压入目标柱子。
- 递归分解:
- 先将 n-1 个盘子从源柱子移到辅助柱子(此时目标柱子充当辅助角色);
- 再将第 n 个盘子(最大的那个)从源柱子移到目标柱子;
- 最后将 n-1 个盘子从辅助柱子移到目标柱子(此时源柱子充当辅助角色)。

代码实现
下面是完整的 C++ 实现。注意观察参数传递的顺序变化,这是理解递归逻辑的关键点。
class Solution {
public:
// 辅助递归函数:将 n 个盘子从 src 移到 dest,aux 作为中转
{
(n == ) {
dest.(src.());
src.();
;
}
(src, dest, aux, n - );
dest.(src.());
src.();
(aux, src, dest, n - );
}
{
n = A.();
(A, B, C, n);
}
};


