【Python】（十一）从汉诺塔看Python中的递归问题

递归的原则

• 递归算法必须具有基本情况。
• 递归算法必须改变其状态并向基本情况靠近。
• 递归算法必须以递归方式调用自身

汉诺塔问题

法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。（来源：互动百科）

该问题可以简化出以下要点：

• 64片金片，从一根针移动到另一根针上，可以借助第三根针
• 大片永远不能放在小片的上面

汉诺塔问题的经典解法

假设金片都在宝石针A上，我们需要把这些金片借助宝石针B，移动到C上。总共有n片需要移动。

1. 将较小的n-1片，从A，借助C，移动到B上。
2. 将最大的第n片，从A，直接移动到C上。
3. 将较小的n-1片，从B，借助A，移动到C上

这一思路的核心假设是在我们处理n片的时候，已经具备了处理n-1片的的能力。这就是递归的思想。当问题简化至移动1片时，我们就可以直接解决了。

#将num片金片，从from_needle,借助by_needle,向to_needle移动
def moveTower(num, from_needle, to_needle, by_needle):
    if 1 == num :
        print('Move Plate %d from %s to %s'%(num, from_needle, to_needle)) #只剩一个时，可不经过借助针，直接移动
    else:
        moveTower(num-1, from_needle, by_needle, to_needle)
        print('Move Plate %d from %s to %s'%(num, from_needle, to_needle)) # 打印出每次单片的移动
                                #所有的移动最终都可以追溯至单片的移动，因而，但打印出所有单片的移动就是打印出了所有的移动
        moveTower(num-1, by_needle, to_needle, from_needle )

def main():
    num = 3
    moveTower(num, 'A', 'C', 'B') # 从A借助B移动到C

if __name__ == "__main__":
    main()

当需要移动3片时，实验结果如下:

Move Plate 1 from A to C
Move Plate 2 from A to B
Move Plate 1 from C to B
Move Plate 3 from A to C
Move Plate 1 from B to A
Move Plate 2 from B to C
Move Plate 1 from A to C

可以用手动方法验证，结果是正确的。

当移动10片时，运行结果如下：

Move Plate 1 from A to B
Move Plate 2 from A to C
Move Plate 1 from B to C
Move Plate 3 from A to B
Move Plate 1 from C to A
Move Plate 2 from C to B
Move Plate 1 from A to B
Move Plate 4 from A to C
Move Plate 1 from B to C
Move Plate 2 from B to A
Move Plate 1 from C to A
Move Plate 3 from B to C
Move Plate 1 from A to B
Move Plate 2 from A to C
Move Plate 1 from B to C
Move Plate 5 from A to B
... ...
Move Plate 4 from A to C
Move Plate 1 from B to C
Move Plate 2 from B to A
Move Plate 1 from C to A
Move Plate 3 from B to C
Move Plate 1 from A to B
Move Plate 2 from A to C
Move Plate 1 from B to C

总共进行了1023步移动。