注：本文如涉及到代码，均经过Python 3.7实际运行检验，保证其严谨性。
本文阅读时间约为5分钟。
本节介绍的是十分经典的递归例子——汉诺塔问题。
汉诺塔问题介绍
汉诺塔问题是由法国数学家Edouard Lucas于1883年根据传说提出来的。
传说在一个印度教寺庙里有三根柱子，其中一根从上向下套着64个由小到大的黄金盘片，僧侣们的任务就是把这一叠黄金盘从一根柱子搬到另一根，但是有两个限制规则：
- 规则1：一次只能搬一个盘子。
- 规则2：自始至终大盘子都不能叠在小盘子上，只能让小盘子叠在大盘子上。
神的旨意说，一旦这些盘子完成迁移，寺庙将会坍塌，世界将会被毁灭。
关于汉诺塔和世界末日的联系
神的旨意是正确的。因为要搬完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柱子，就完成了整个挪动。这个过程如下图所示：
事情还没有完。
接下来的问题，就是解决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 #3
Moving disk[2] from #1 to #2
Moving disk[1] from #3 to #2
Moving disk[3] from #1 to #3
Moving disk[1] from #2 to #1
Moving disk[2] from #2 to #3
Moving disk[1] from #1 to #3
<<<
移动的次数为2**height-1次，所以上面的例子是移动了2**3-1=7次。
友情提示：如果height=64，运算量将十分巨大，一般电脑恐怕不太容易撑住……
To be continued.
