对汉诺塔递归问题的另外一种理解思路

汉诺塔是一个由数学家爱德华卢卡斯（Edouard Lucus）于1883发明的游戏。

思考题：
有三根细柱（A，B，C）,A柱上套着6个圆盘，这些圆盘大小各异，按照从大到小的顺序自下而上摆放。现在要把套在A柱上的6个圆盘移动到B柱上，并且在移动圆盘时遵守以下规定：
（1）一次只能移动柱子最上端的一个圆盘；
（2）小圆盘上不能放大圆盘。

将1个圆盘从一根柱子移动到另一根柱子，算是移动一次。那么，将6个圆盘全部从A移动到B最少需要移动几次呢？

首先我们在头脑中可以速度构建出3层的汉诺塔的解法：

在来回移动圆盘的过程中，你一定会觉得在重复做相同的事情。之所以会产生这种感觉是因为我们有“发现规律的能力”。这种感觉很重要。

虽然移动的目的地不同，但是这两个动作是非常相似的。而且这种“移动两个圆盘”的动作，就是“2层汉诺塔”的解法。
由此，我们认为“6层汉诺塔”可以通过以下步骤解出：
（1）首先，将5个圆盘从A柱移动到C柱（解出5层汉诺塔）
（2）然后，将6个之中最大的圆盘从A柱移动到B柱
（3）最后，将5个圆盘从C柱移动到B柱（解出5层汉诺塔）

……

通过这种思考方式，我们可以总结出n层汉诺塔的解法。
以下，我们不使用A、B、C这三根柱子的具体名称，而是将其设为x，y，z。因为x，y，z会不固定地对应A、B、C中的某一个。x为起点柱，y为目标柱，z为中转柱。

解出n层汉诺塔的问题，即“利用z柱将n个圆盘从x柱转移到y柱”

我们来分析一下：
当n = 0时，不做任何动作。
当n>0时，
（1）首先，将n-1个圆盘从x柱，经由y柱中转，移动到z柱。（解出n-1层的汉诺塔）
（2）然后，将1个圆盘从x柱移动到y柱。
（3）最后，将n-1个圆盘，经过x柱中转，移到y柱（解出n-1层汉诺塔）

由以上步骤，我们知道，为了解出n层汉诺塔，需要使用“n-1层汉诺塔”的解法。
我们将解出n层汉诺塔所需的最少移动次数表示为H(n)

例如，移动0个圆盘的次数为0，那么H(0) = 0
而移动1个圆盘的次数为1，那么H(1) = 1
根据解n层汉诺塔所用的步骤，可以将移动次数H(n)的式子写为
H(n) = 0 (n = 0时)
H(n-1)+H(n-1) (n = 1,2,3…时)

《程序员的数学》原书中给出了C语言的实现的汉诺塔的解法，这里我改用Python语言做一个简单的实现。

def hanoi(n,x,y,z):
    if(n==0):
        pass
    else:
        # 实现n-1层汉诺塔
        # 即将n-1个圆盘从x柱，经由y柱中转，移动到z柱
        hanoi(n-1,x,z,y);
        # 将1个圆盘从x柱移动到y柱
        print("%s-->%s" %(x,y))
        # 将n-1个圆盘，经过x柱中转，移到y柱（解出n-1层汉诺塔）
        hanoi(n-1,z,y,x)
if __name__ == '__main__':
    hanoi(6,'A','B','C')

运行结果略