C / C++ / 系统课时
用递归解决汉诺塔问题
用递归解决汉诺塔问题
汉诺塔的难点不是移动一块盘,而是把“移动 n 块盘”重新表达成更小的同类问题。本课从三步拆分出发,实现可运行的 C 程序,并用调用顺序理解递归为什么能生成完整移动方案。
学习目标
- 把汉诺塔问题拆成两个规模为
n - 1的递归子问题 - 写出带明确终止条件的 C 语言递归实现
- 根据递推关系判断移动次数和递归栈深度
把移动 n 块盘拆成三步
设有源柱 A、辅助柱 B 和目标柱 C,盘子从小到大叠放,且任何时刻都不能把大盘放在小盘上。要把 n 块盘从 A 移到 C,核心不是直接决定每一步,而是完成三个阶段:
- 把上面的
n - 1块盘从A移到B,此时借助C。 - 把最大的第
n块盘从A移到C。 - 把
n - 1块盘从B移到C,此时借助A。
第 1 步和第 3 步与原问题结构完全相同,只是盘子数量少了一块、三根柱子的角色发生了变化。当 n == 1 时,只需把唯一一块盘直接移动到目标柱,这就是终止条件。

用 C 语言实现递归移动
下面的程序把三根柱子作为字符参数传入。参数顺序固定为“源柱、辅助柱、目标柱”,这样每次递归只需要重新排列柱子的角色。
#include <stdio.h>
void hanoi(int n, char from, char auxiliary, char to) {
if (n == 1) {
printf("move disk 1: %c -> %c\n", from, to);
return;
}
// 先把上面的 n-1 块移到辅助柱,为最大盘腾出路径。
hanoi(n - 1, from, to, auxiliary);
printf("move disk %d: %c -> %c\n", n, from, to);
// 再把 n-1 块从辅助柱移到目标柱。
hanoi(n - 1, auxiliary, from, to);
}
int main(void) {
int n = 3;
if (n <= 0) {
printf("n must be positive\n");
return 1;
}
hanoi(n, 'A', 'B', 'C');
return 0;
}预期输出
move disk 1: A -> C
move disk 2: A -> B
move disk 1: C -> B
move disk 3: A -> C
move disk 1: B -> A
move disk 2: B -> C
move disk 1: A -> C这 7 行不是预先写好的移动表,而是递归调用在返回过程中自然产生的执行顺序。若把 n 改成其他正整数,程序会按照同一规则生成新的合法方案。
跟踪 n 等于 3 时的执行过程
第一次调用 hanoi(3, 'A', 'B', 'C') 不会立刻移动第 3 块盘,而是先进入 hanoi(2, 'A', 'C', 'B')。这个调用又会继续处理 1 块盘,直到 n == 1 才执行第一条实际移动。
最内层调用返回后,程序回到上一层,移动第 2 块盘,再完成另一侧的 1 块盘子问题。等左半部分全部结束,最外层调用才移动第 3 块盘,然后用同样方式完成右半部分。
理解这段过程时,可以把每次调用看成一句承诺:“我负责把这 n 块盘搬到目标柱,但我要先让一个更小的问题替我腾出空间。”递归函数只需要保证这一层的三阶段顺序正确,不必一次性记住所有移动步骤。
移动次数和栈空间
设移动 n 块盘需要 T(n) 次操作。前后两个子问题各需要 T(n - 1) 次,中间再移动一次最大盘,因此有:
并且 T(1) = 1,可得 T(n) = 2^n - 1。所以 n = 3 时是 7 次,n = 4 时是 15 次。时间复杂度为 O(2^n),盘子数量每增加 1,移动次数几乎翻倍。
递归调用的最大深度只沿一条子问题链从 n 下降到 1,因此额外栈空间是 O(n)。这说明汉诺塔非常适合练习递归结构,但不适合把很大的 n 当作高效求解任务。
关键判断始终是两点:基本情况 n == 1 能够到达,并且每次递归都把规模从 n 缩小到 n - 1。只要这两个条件成立,三步拆分就能完整覆盖所有合法移动。