通过递归解决汉诺塔问题

    汉诺塔(Tower of Hanoi)问题源于印度传说，大梵天创造世界时造了三根金钢石柱子，其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。                      

汉诺塔问题

    我们可以使用递归思路分解汉诺塔问题，例如我们有5个盘子在1柱需要挪到3柱，那只需要把4个盘子挪到2柱，最大盘子挪到3柱问题就解决了，把2柱的4个盘子移到3柱上就完成移动。

    接下来就是想怎么把4个盘子从1柱挪到2柱，同样是想办法把上面3个盘子挪到3柱，把剩下的最大盘子从1挪到2柱，再用同样的方法把3个盘子从3挪到2柱。同理，3个、2个盘子也是这么移动。基本的结束条件就是1个盘子的移动问题。

    通过分治策略逻辑分三步：

1、首先将上层N-1个盘片从开始柱，经由目标柱移到中间柱；

2、然后将第N个（最大的）盘，从开始柱移到目标柱；

3、最后将放在在中间柱的N-1个盘，经由开始柱，移到目标柱。

代码很简单，如下：

递归解决汉诺塔问题

    第一个moveTower递归是将开始柱的N-1个盘从开始柱移到中间柱，然后moveDisk递归是将第N个盘，从开始柱移到目标柱，第二个moveTower递归是将中间柱的N-1个盘移到目标柱上。

     最后关于递归算法，我们虽然看着代码很简单，但真要深入理解也是很费脑细胞的，不过递归确实有中数学上的简洁美和逻辑美。