一.介绍
汉诺塔传说是源于印度的古老传说。
汉诺塔游戏一共有三根柱子，第一根柱子上有若干个盘，另外两根柱子上没有盘。
柱子上的盘是按照大小从小到大的排列的，最上面的盘是最小的，越到下面越大。
每一次将任意一根柱子上最上面的一个盘放到另外一根柱子上，但要遵守以下两条：
1.每一次必须移动一个盘
2.大盘不可以压在小盘上面
我们的目标就是反复移动盘，直到把所有的盘从第一根柱子上全部移动到其他的柱子，比如，这里我们就定死，全部移动到第三根柱子，则达到目的。
以上6个盘的移动方法我做了个动画，如下所示：
二.递归
如果是第一次看到汉诺塔，估计会一下子变的手足无措。
但我们细细的去想想，从简单的开始入手，先看一个盘的情况，这个太简单了，只需要一步即可。
既然是递归，我们就要考虑问题的分解，也就是降阶。
我们考虑n个盘的汉诺塔问题(n>1)。
我们来看，最大的那个盘什么时候才可以移动走呢？因为这是最大的盘，大盘不可以压小盘，所以它移动的前提一定是在其他的盘都在另外一根柱子上，这样可以空出来一根柱子让它移动过去。而同时，它的存在并不影响任何小盘的移动。
于是我们可以把问题分解一下：
当n>1时，我们把n个盘从第一根柱子移动到第三根柱子，可以分为三个步骤：
1.把上面的n-1个盘从第一根柱子移动到第二根柱子
2.把最大的盘从第一根柱子移动到第三根柱子
3.把那n-1个盘从第二根柱子移动到第三根柱子
于是，一个问题就这样被分解为三个小问题，达到了递归的降阶。
用数学归纳法很容易证明上述的移动方法，对于n个盘的移动步数是2n-1
当然，问题本身的形式化，我们用可以用hanoi(n, from, to, buffer)来表示问题，n是盘子的个数，from是盘子初始时所在的柱子，to是盘子最终所在的柱子，buffer是除了from和to的另外一个柱子。
于是用伪码来表示这个递归：hanoi(n, from, to, buffer):beginif n=1beginmove_disk(from,to)endelsebeginhanoi(n-1,from,buffer,to)hanoi(1,from,to,buffer)hanoi(n-1,buffer,to,from)endend
递归过程动画：
