汉诺塔递归算法精讲

---

前言

递归算法是计算机算法中的基础算法，也是非常重要的算法，从某种程度上讲，它有一点儿AI的影子。人脑是可以完成递归思路的，但是对不起，残酷的现实是，一般人脑在精力集中的情况下，能递归个三五层就就基本晕菜了。反正我是这样，你或者您可能深度多一些。当然个别领域，例如棋手，可能深度多达10层或者20层，这是凤毛麟角了。

废话少说，说说汉诺塔的递归解法思路，并给出本人朴素的解释，力图使一看就晕的小伙伴们，能看清楚。

---

一、汉诺塔是个啥？

尽管您或许知道这个小游戏，但是为了将问题说清楚，还是要简单介绍一下。以下内容来自 《百度百科》

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

二、手动解法

下面尝试用静态图来分析和描述一下手动解法，大家也可以参考下列链接，以期获得感性认识。
汉诺塔在线游戏
为了简便起见，我们从三个开始尝试。
如图：

根据题目要求，每次移动一个，而且必须是小的在上面。如果胡乱尝试，您可能好会成功，但是可能会不得要领，因此先分析，才能厘清思路。
分析：我们考虑最后一步，必然是将 1 从什么地方 移到 C 上，倒数第二步，必然是将2 从什么地方移到C上，倒数第三步必然是将3 从什么地方移到C上。因为3 最大，因此，倒数第三步时，必然是3的上面没有盘子，C的上面没有盘子。否则就违背了原则，因此，如果想办法通过什么方法变成下面的情况，倒数第三步就实现了。
如图：

此时就可以把 3 移到 C上，如图

冷静一下，你会发现，此时问题已经降级为，如何将两个盘子移到C上的问题，只是位置从A 变成了B，聪明的你，可以知道这并没有区别。所以现在的问题是 怎么将两个盘子移到到C上。这个问题就非常简单了，1->A, 2->C,1->C。 由于我们遵守小的在上面的原则，就是说每次只能取最上面的 一个 盘子，因此上面的步骤也可以用位置来表示就是
B->A, B->C, A->C, 至于上面的盘子是啥，其本身已经记住了。
OK， 三个已经完成了。

三、解法抽象

现在我们整理一下思路：
要想把3个盘子从A移到C上，必须先把3-1个盘子从A移到B上；套用上面的想法，
做进一步的思考：如果想把3-1个盘子从A移到B上，必需先把 3-1-1个盘子从A移到C上。
仔细看上面的步骤，我们进一步分析其细节，把语言可以精确的描述为：

要想把3(n）个盘子从A 移到C上，必须先把3-1（n-1）个盘子通过C移到B上；
如果想把3-1（n-1）个盘子从A移到B上，比需先把 3-1-1（n-1-1）个盘子通过B移到C上。
可以看出上述的步骤的相似性，就是有三个抽象点，第一：起点， 第二 终点， 第三是：过度点。

仿照上面的思路，我们可以得到 n个盘子的移动方法；
要想把n个盘子移到C上，必须先把n-1个盘子通过C移到B上；
采用更抽象的描述就是：
要想把n个盘子从 起点 移到 终点上，必须先把n-1个盘子通过 终点 移到 过渡点上；
我们用 From 表示起点，To 表示终点 , By 表示过渡点，那么上面的描述就是

要想把n个盘子从from 移到 to ，必须先把n-1个盘子通过 to 移到 by 上；

进一步，假设我们完成了一个过程，叫 HanoiMove， 根据上面的分析，它必须包括四个关键属性： 个数n，起点 from，过渡点 by，终点 to，我们不妨记作

HanoiMove（n,from, by, To) ,这个表示 把 n 个盘子从From 经过 by， 移到到 To，聪明的你应该看出来这不就是函数吗？为了更清楚起见，我们采用 相应的位置表示起点，过渡点和终点。

四、递归解法

根据上面的分析，我们只要逐层降级就可以完成任务了，这就用到了递归，为了说清楚，我们慢慢来。

第一步：调用 HanoiMove（n,from, by, To) ，表示将n从 From 经过 by 移到 To 上。

第二步：HanoiMove（n-1,from, by, To ) ，这个表示 将n-1个盘子，从 from 经过to移到 by 上

第三步：此时From 上面只有一个 最大号的 盘子了 ，编号n，只需 将 编号n的盘子从 From 移动到 to上就可以了。注意此时是移动一个盘子，没有递归的问题。

第四步：这个时候， n-1个盘子 在 by 上面（by成为起点了，from 是过渡点， to仍然是终点）， 调用前面的过程 HanoiMove（n-1,by, from, to ) 这个表示 将n-1个盘子，从 by 经过From移到 to上

到这一步就完成了所有的盘子的搬运。

写成伪代码的函数就是：

HanoiMove（n,from, by, To){HanoiMove（n-1,from, by, To ) 输出：From->toHanoiMove（n-1,by, from, to )

}
但是这样就行了吗？
递归调用的一个关键就是结束条件，如果没有，就会一直递归下去，直到溢出错误出现。上面的伪代码中，没有结束条件，那么结束条件是什么呢？显然是n=1 的时候，就结束了。因此，加上结束条件之后的代码为：

HanoiMove（n,from, by, To){if（n==1） {输出：From->toreturn }HanoiMove（n-1,from, by, To ) 输出：From->toHanoiMove（n-1,by, from, to )

}
可以将上述伪代码，改编成某种语言运行

其C#代码如下：

       public void HanoiMove(int n, string from, string by, string to){if (n > 1){HanoiMove(n - 1, from , to, by);Console.WriteLine( String.Format("\r\n{0} {1}->{2}", n, from, to));//是盘子编号，可以不用。HanoiMove(n - 1, by, from, to);}else{Console.WriteLine( String.Format("\r\n{0} {1}->{2}", n, from, to));}}

注意：上面的输出的n 可以不用。

---

五、总结

对于递归调用的代码实现，一定要将过程抽象出来，反复的在头脑中进行这一过程的拟合，将具体步骤进行高度的抽象，具化成参数和表达式（输出），并设置结束条件（递归出口）。

MaraSunDB BJFWDQ 2023-02-15

`