一、故事背景
相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。
二、简化问题
- 把 A 杆上的所有盘子放在 C 杆上
- 规则是：
（1）盘子可以被随意移动到别的杆，但一次只能移动一个盘子
（2）最终在 C 杆上呈现的结果是：小盘在上，大盘在下
三、建立模型（动态图）
- 一个圈圈
- 两个圈圈
- 三个圈圈
- 四个圈圈
四、代码实现
程序清单：
public class test { public static void main(String[] args) { Hanoi(1, 'A', 'B', 'C'); System.out.println(); Hanoi(2, 'A', 'B', 'C'); System.out.println(); Hanoi(3, 'A', 'B', 'C'); System.out.println(); Hanoi(4, 'A', 'B', 'C'); System.out.println(); } public static void Hanoi(int n, char A, char B, char C) { if (n == 1) { move(A, C); } else { Hanoi(n - 1, A, C, B); move(A, C); Hanoi(n - 1, B, A, C); } } public static void move(char pos1, char pos2) { System.out.print(pos1 + "->" + pos2 + " "); } }
输出结果：
五、代码分析
- 主函数写了四种情况，分别对应 1 - 4 个盘子
- move 函数表示每一次盘子从一个位置移动到另一个位置
- Hanoi 函数是核心，它呈现了递归思想
- Hanoi 函数中 if (n == 1) 这一行代码就是终止条件，而下面对应的 else 就是规律公式，用来无限趋近于这个终止条件的，当达到这个终止条件时，那么就层层返回！也就是开始递归中的 “ 归 ”！
接下来，就Hanoi 函数，我们进行分析
当 n = 1 时，也就是说此时只有一个盘子，那么只需要移动一次，直接把它放到 C 杆上就行了。
当 n = 2 时，此时有两个盘子，那么我们先得把两个圈圈中最小的圈圈从 A 杆移动到 B 杆，过渡一下，然后才能把最大的圈圈放在 C 杆上，从而实现最终目的，也就是说，此时的B杆充当了中介。
当 n = 3 时，…
当 n = 4 时，…
上面我就不再赘述了，所以我们找到了规律：
不论几个盘子，B杆始终充当了中介杆，而此时，不论怎么移动，肯定出现了这种情况：C杆已经放置了最大的那个盘子，B杆上放的是除了那个最大盘子之外的所有盘子。
如下：
n = 3 时
此时 B 杆上的盘子个数为 n - 1 = 2
n = 4时
此时 B 杆上的盘子个数为 n - 1 = 3
当盘子很多很多时，假设就为n
此时B杆上的盘子个数为 n - 1
那么我们就把这 n - 1 个盘子想象成一个整体，直接就挪到C杆上，但是我们不关心这其中有多少步骤，不关心这些步骤又是怎么算的，因为我们可以把这个计算步骤交给计算机去算，作为程序员，我们只要设置程序让他跑就行了。
所以，请注意！！！
现在我们回过头看程序清单中 Hanoi 函数，我们就不迷糊了，请看图：
当 n >= 2 时，我们先把 n - 1 个盘子先从 A 挪到 B，再从 B 挪到 C，在这个过程中，我们要有整体的思想
我们要思考的是：在某一个过程，哪些盘子充当整体？哪个杆又充当中介？
很多人的思想总是停留在一个一个盘子的挪，这种思想是非常复杂的，甚至这样想问题的出发点就是错的！因为你找不到规律不说，在盘子的数量为4个以上时，你很可能会移错步骤，一步错，那么步步错！
你可以看到我在上面的动态图演示的时候，那已经是最完美的情况了，在不会移错的情况下都那么复杂，何况移错的情况下呢？
总结
- 经典的汉诺塔问题在计算机中，包含了递归思想，这就要回到递归的本质，通过找到规律，从而大事化小，得出结果。
- 前两个博客介绍了递归的思想和例子，这篇博客用来结尾基础部分的递归，后面等学到算法的时候，再回过头看，或许思路会更加清晰。
Over. 谢谢观看哟~
