无趣的汉诺塔 （递归问题的个人理解）

---

从前有座山,山上有座庙,庙里有个老和尚和一个小和尚,有一天,老和尚对小和尚说:从前有座山,山上有座庙,庙里有个老和尚和一个小和尚,有一天,老和尚对小和尚说:从前有座山,山上有座庙,庙里有个老和尚和一个小和尚,有一天,老和尚对小和尚说…….

汉诺塔游戏是博主高中时候接触到的一款游戏。当时宿舍里大家都没有手机，直到有一天，一哥们带来了一款诺基亚手机（具体哪个版本记不清楚了），从此为无聊的高中生活打开了新世界的大门。手机上有中国象棋，五子棋等小游戏，都不知道玩过多少遍了还不厌烦，而一款叫汉诺塔的陌生游戏也借机进入博主的视线。当时最多挑战过7个盘的汉诺塔，已经是熬夜奋战了几个小时，挑战成功后还有些许沾沾自喜。如果当时知道它背后的原理有多简单后，应该也不会不会去玩了，也许也不会有这篇博客了。

1. 汉诺塔游戏

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。 —— [ 百度百科 ]

乍一听可能还是不理解，那就把问题再梳理简化一下吧。如下图所示， A柱有3个盘，B柱和C柱没有盘，现在要把A柱的盘全部挪到C柱，规则很简单：

1. 每次只能移动1个盘
2. 大盘不能放在小盘下面
3. 中间的B柱可用来临时存放盘，但遵从规则1和2
   

那么，开始愉快的玩游戏吧：
2个盘： 观尔乃插标卖首
3个盘： 看我的厉害
4个盘： 主公，这可如何是好
5个盘： WTF!
。。。
10个盘： 摔桌子走人

看来，如果完成7层或者8层汉诺塔，就已经接近普通人的极限了。穷则变，变则通。这个问题归结起来，就是一个递归问题。

2. 初看递归问题

递归问题【1】是一种可以根据具前后两步之间的逻辑关系及初始步的值，来推算出当前步结果的问题。最简单的例子就是高中的等差等比数列，例如有这样一个问题：已知第一个数字为1，后面每一位都是前一位的2倍，求第n位的数字是多少？如果使用数学公式来表述，这个问题可以写为：

$$f(n)=\left\{ \begin{array}{rcl} 1 & & n=1\\ 2f(n-1) & &n \not=1 \end{array} \right.$$
根据高中的数学知识，我们很快就能推到出 $f(n) = 2^{n-1}$。但是对计算机来讲，做出这样具有总结性的推导是很困难。但是计算机的优势就是可以在 短时间内完成 大量重复而单调的事情。因此，这样的问题到计算机这里，就变成了一步步老老实实计算的过程，简易的python代码如下：

# -*- coding: utf-8 -*-def fun(n):if n == 1:# 初始条件return 1else:# 前后两步的数学关系return 2 * fun(n-1)

这样，无论你想得到第几个数字，只要调用函数fun()即可。总结下来，解决递归问题时有两个重要环节：1. 前后两步之间的逻辑关系； 2. 第一步的值
那扯了这么多，与汉诺塔游戏有什么关系呢？别急，我们再战汉诺塔游戏

3. 再战汉诺塔

这一次，我们在玩这个游戏时需要换一种思路，不从头一点点去玩，直接跳到中间某一步，看看能否找到规律性的东西。

3.1 前后两步的逻辑关系

先做一个定义：

我们定义一种操作f(A, C, B, n)，这种操作可以将n个从小到大排列的盘子从A柱移动到C柱，中间可以借助B柱进行暂存

假设我们已经到达下图这一步（要赢则必经的一步）， 即将最大盘上面的所有盘已经移动到B柱，且C柱没有任何盘， 那么我们下一步最正确的操作则是将最大盘移动到C柱位置。

在完成上上述步骤后，将B柱上的盘设法全部移动到C柱即可，如下图所示。

将实现这一步的操作可以等效为三个过程：
1. 将A柱上n-1个盘子装在包内，一起移动到了B柱位置 ；f(A, B, C, n-1)
2. 将A柱上仅剩的最大盘移动到C柱；
3. 将B柱上的n-1个盘子装在包内，一起移动到C柱最大盘上面 f(B, C, A, n-1)

这样看起来就相对简单多了。但是问题来了，如何实现将n-1个盘打包并移动到目标的柱子上呢？回头看我们定义的操作，看是不是发现了什么。对，整个汉诺塔游戏其实也可以看作是一个操作，即将A柱上的n个盘打包，然后在B柱的协助下，一起移动到C柱f(A, C, B, n)，这个过程和将n-1个盘打包并移动一模一样!
我们定义一个函数来模拟这种操作：

def hanno(pillar_from, pillar_to, pillar_unuse, num):"""pillar_from: 从那个柱子拿盘pillar_to: 把盘子放在哪个柱子上pillar_unuse: 哪个柱子用来中转num: 要把几个盘打包后进行移动"""hanno(pillar_from, pillar_unuse, pillar_to, num-1)# 打印出盘的移动操作print('{} >> {}'.format(pillar_from, pillar_to))hanno(pillar_unuse, pillar_to, pillar_from, num-1)

3.2 第1步的具体操作

上面的函数实质上定义了递归问题中相邻两步的逻辑关系，可以很明显的看出，我们编写的那个函数实际上是在不断向盘子数为1的情况追溯。当盘子数目为1时，我们就要给出一个很明确的做法，让这一步不再依赖任何一步。这样整个函数就不会无限制的追溯下去而陷入死胡同了。
那么当盘子数目为1时，该如何操作呢？非常简单，直接将这个盘子直接放到目标柱子上不就好了嘛！因此写个条件语句，来终止回溯的过程：

def hanno(pillar_from, pillar_to, pillar_unuse, num):"""pillar_from: 从那个柱子拿盘pillar_to: 把盘子放在哪个柱子上pillar_unuse: 哪个柱子用来中转num: 要把几个盘打包后进行移动"""if num == 1:# 1个盘的汉诺塔游戏该怎么操作print('{} >> {}'.format(pillar_from, pillar_to))returnhanno(pillar_from, pillar_unuse, pillar_to, num-1)# 打印出盘的移动操作print('{} >> {}'.format(pillar_from, pillar_to))hanno(pillar_unuse, pillar_to, pillar_from, num-1)

接下来呢，额、、、完了啊，就只要这几行程序。

但是，为了如果我们想要知道程序操作了多少步，那么还需要小小增加一点对象。完整版的代码及测试如下：

# -*- coding: utf-8 -*-
"""
Created on Thu Sep  6 19:09:18 2018
@author: duanshao
"""
count = 0
def hanno(pillar_from, pillar_to, pillar_unuse, num):"""pillar_from: 从那个柱子拿盘pillar_to: 把盘子放在哪个柱子上pillar_unuse: 哪个柱子用来中转num: 要把几个盘打包后进行移动"""# 用于统计操作步数global countif num == 1:# 1个盘的汉诺塔游戏该怎么操作print('{} >> {}'.format(pillar_from, pillar_to))count += 1returnhanno(pillar_from, pillar_unuse, pillar_to, num-1)print('{} >> {}'.format(pillar_from, pillar_to))count += 1hanno(pillar_unuse, pillar_to, pillar_from, num-1)# 10个盘的汉诺塔游戏操作过程
hanno('A', 'C', 'B', 10)
print('总共经历了{}步操作'.format(count))

4. 再看递归问题

仔细想一想，递归为什么叫递归，或者说recursion 为什么翻译为递归。对照着下图，可以将递归嘎嘣利落脆的解释为有去（递去） 和有回（归来）。“递去”是指：递归问题必须可以分解为若干个小规模且与原问题相似的子问题，与原问题类似，这些子问题可以用相同的思路来解决；“归回”是指 : 这些问题会演化到一个明确的终点(临界点)，且一旦到达了这个终点，就不再往更小的问题去演化。最后，从这个终点开始原路返回，问题得以解决。　

5. 总结与归纳

统计一下汉诺塔的层数与最少操作步数之间的关系，可以得到下图。可见每增加一个盘，操作次数需要翻倍并且多加1次，看来，超过10个盘的汉诺塔游戏就已经不大适合人类去玩了。当然，你非要挑战的话，也只能送上一句Good Luck!

递归思想在计算机编程中经常用到，比如计算阶乘，判定一系列字符串中是否有相同的内容等等。之前看到这样一道题：有这样一个列表, L=[‘sa’, [’s’, [[‘ff’], ‘bbg’]], ‘kk’], 要求将其中的字符串全部提取出来，变成一个只有字符串的列表，即结果为[‘sa’, ‘s’, ‘ff’, ‘bbg’, ‘kk’]，看完这篇博文的小伙伴，可以使用递归算法去实现一下。