企业官网建设流程全解析

Java 递归 汉诺塔 新手学习

今天上课学了汉诺塔递归，一开始完全看不懂为什么调换一下参数名字，代码就知道怎么移动盘子了。写下来记录一下我是怎么想明白的。

汉诺塔问题

三个柱子 A、B、C，有 n 个盘子叠在 A 上，要全部移到 C 上。规则：每次只能动一个盘子，大的不能放在小的上面。

递归思路

不要想着怎么一步步移动，先想大问题怎么拆成小问题：

要把 n 个盘子从 A 移到 C，分三步：

1. 先把上面 n-1 个盘子，从 A 移到 B（借助 C）
2. 把最底下最大的那个盘子，从 A 直接移到 C
3. 再把 B 上的 n-1 个盘子，从 B 移到 C（借助 A）

而移动 n-1 个盘子的方法，和移动 n 个盘子的方法是一模一样的，只是起点、辅助、目标换了。这就是递归。

代码

public static void hanoi(int n, char pos1, char pos2, char pos3) { if (n == 1) { move(pos1, pos3); return; } hanoi(n - 1, pos1, pos3, pos2); move(pos1, pos3); hanoi(n - 1, pos2, pos1, pos3); } public static void move(char pos1, char pos2) { System.out.println(pos1 + "->" + pos2); } public static void main(String[] args) { hanoi(3, 'A', 'B', 'C'); }

我一开始最困惑的问题

为什么代码里没有真的去记录每个柱子上有几个盘子，只是调换 pos1、pos2、pos3 这三个参数，就知道怎么移动了？

后来想明白了：三个物理柱子 A、B、C 是固定不变的。hanoi 方法的三个参数 pos1、pos2、pos3，根本不是代表 A、B、C 这三个柱子本身，而是代表三个角色：

• pos1：当前这个任务的起点
• pos2：当前这个任务的辅助
• pos3：当前这个任务的目标

比如调用 hanoi (3, 'A', 'B', 'C')： 起点是 A，辅助是 B，目标是 C。

然后第一个递归调用 hanoi (n-1, pos1, pos3, pos2)： 意思是，现在要搬上面 n-1 个盘子，这个子任务的起点还是 A，但是辅助换成了 C，目标换成了 B。

A、B、C 这三个字母从来没变过，只是在不同的子任务里，它们扮演的角色不一样了。

代码根本不需要知道每个柱子上现在有几个盘子，它只需要按照规则，把大任务拆成三个小步骤，然后递归下去就行。

n=1 是什么意思

n=1 是递归的终点。当分到只剩 1 个盘子的时候，不用再拆了，直接把这个盘子从当前任务的起点 pos1，移到当前任务的目标 pos3，然后 return 结束这一层。

这里的 pos1 和 pos3，已经是经过层层调换后的角色了，所以 move 打印出来的移动步骤就是正确的。

单引号和双引号的问题

一开始写 hanoi (3, "A", "B", "C") 报错了，因为方法参数定义的是 char 类型，char 只能放单个字符，必须用单引号 'A'。双引号是 String 字符串，类型对不上。

运行结果（n=3）

A->C A->B C->B A->C B->A B->C A->C

一共 7 步，正确。

一点心得

递归这个东西，光看代码真的绕。我后来把 n=3 的每一层调用都写在纸上，一层一层列出来，看哪些时候进 if，哪些时候执行 move，哪些时候 return，才慢慢搞懂