注：本文如涉及到代码，均经过Python 3.7实际运行检验，保证其严谨性。

本文阅读时间约为5分钟。

本节介绍的是十分经典的递归例子——汉诺塔问题。

汉诺塔问题介绍

汉诺塔问题是由法国数学家Edouard Lucas于1883年根据传说提出来的。

传说在一个印度教寺庙里有三根柱子，其中一根从上向下套着64个由小到大的黄金盘片，僧侣们的任务就是把这一叠黄金盘从一根柱子搬到另一根，但是有两个限制规则：

规则1：一次只能搬一个盘子。规则2：自始至终大盘子都不能叠在小盘子上，只能让小盘子叠在大盘子上。

神的旨意说，一旦这些盘子完成迁移，寺庙将会坍塌，世界将会被毁灭。

Pic-406-1 汉诺塔示意图

关于汉诺塔和世界末日的联系

神的旨意是正确的。因为要搬完64个盘片，需要的移动次数是2**64-1=18446744073709551615，就算寺庙里有人能快到每秒搬动一次盘子，按一年365天、一天24小时计算，全部搬完也需要584942417355.072年，即超过5800亿年。到时地球早就被毁灭了，因为地球的寿命只剩下大约50亿年。

从递归三定律来分析汉诺塔问题

递归三定律有基本结束条件、如何减少规模、调用自身。我们看如何把递归三定律套用到汉诺塔问题上。

汉诺塔问题分解为递归形式

假设有5个从上往下由小到大的盘子，1#、2#和3#分别代表3个柱子，其中1#表示起始柱子(fromPole)，2#代表中间柱子(withPole)，3#代表目标柱子(toPole)。

我们要解决的问题就是，需要把1#柱子上的5个盘子挪到3#柱子上。这个挪移过程需要遵循上面说的两个限制规则：

规则1：一次只能搬一个盘子。规则2：自始至终大盘子都不能叠在小盘子上，只能让小盘子叠在大盘子上。

如果能有办法把最上面的一摞4个盘子统统挪到2#柱子，问题就好解决了： 把剩下的最大号盘子直接从1#柱子挪到3#柱子。再用同样的办法把2#柱子的那一摞4个盘子挪到#3柱子，就完成了整个挪动。这个过程如下图所示：

Pic-406-2 汉诺塔递归思路示意图

事情还没有完。

接下来的问题，就是解决4个盘子如何从1#挪到2#？

此时问题规模已经减小。

同样是想办法把上面的3个盘子挪到3#，把4个盘子中最大的那个盘子从1#挪到2#。

再用同样的办法处理剩下的3个盘子，即分为上面2个盘子和下面最大的盘子。

接着同样处理剩下的2个盘子。

以上办法就是不断地调用自身，同时也在不断地减小问题的规模。

最后剩下1个盘子，直接移动即可。1个盘片的移动问题就是我们要找的基本结束条件。

至此，汉诺塔问题分解结束。

下面，我们来厘清汉诺塔递归思路。

汉诺塔递归思路

根据上文的分解分析，将盘片从开始柱fromPole，经由中间柱withPole，移动到目标柱，由以下3步可以完成：

将上层N-1个盘片的盘片塔，从开始柱，经由目标柱，移动到中间柱。将第N个盘片，也就是最大的盘片，从开始柱，移动到目标柱。将放置在中间柱的N-1个盘片的盘片塔，经由开始柱，移动到目标柱。

至此，代码出来了：

def moveTower(height, fromPole, withPole, toPole):       if height >= 1:        moveTower(height - 1, fromPole, toPole, withPole)        moveDisk(height, fromPole, toPole)        moveTower(height - 1, withPole, fromPole, toPole)def moveDisk(disk, fromPole, toPole):    print(f"Moving disk[{disk}] from {fromPole} to {toPole}")moveTower(3, "#1", "#2", "#3")<<<Moving disk[1] from #1 to #3Moving disk[2] from #1 to #2Moving disk[1] from #3 to #2Moving disk[3] from #1 to #3Moving disk[1] from #2 to #1Moving disk[2] from #2 to #3Moving disk[1] from #1 to #3<<<

移动的次数为2**height-1次，所以上面的例子是移动了2**3-1=7次。

友情提示：如果height=64，运算量将十分巨大，一般电脑恐怕不太容易撑住……

To be continued.