汉诺塔递归算法精讲

大家好，欢迎来到IT知识分享网。

前言

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

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

一、汉诺塔是个啥？

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

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

二、手动解法

三、解法抽象

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

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

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

四、递归解法

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

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

第二步：HanoiMove（n-1,from, to, by ) ，这个表示 将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, to, by) 输出：From->to//表示将大号的盘子直接移到终点上。 HanoiMove（n-1,by, from, to ) 

HanoiMove（n,from, by, To){ if（n==1） { 输出：From->to return } HanoiMove（n-1,from, by, To ) 输出：From->to HanoiMove（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

`