汉诺塔(hanio tower)递归实现的原理思考

前言

昨天我是先看的汉诺塔理论上的实现原理，看完之后感觉还行，这不是挺简单的嘛。但是理论总归要去实际操作去实现的嘛。于是我就去看了汉诺塔的代码实现方法，看了之后说实话我有点懵逼.WTF？？？？？这么神奇？？就几句话就搞定啦？？凭什么递归就可以去实现汉诺塔?递归和汉诺塔实现原理的共性是什么，以至于递归就可以完美实现汉诺塔？？这些疑问困扰着我。然后我就去搜集有关的视频和文章，结果就是...我还是没理解真正的原理..很多博主的讲解普遍集中在将汉诺塔去一步一步实现了一遍，没有明确提到为什么选择递归算法就可以完美实现汉诺塔。后来，我通过对这些博主讲解的信息进行综合分析，总算有了一点小小的理解。下面我就来分享一下我的个人理解。

汉诺塔介绍

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

根据上文我们可以捕获汉诺塔五点关键信息:①我们有三根柱子分别标记为A,B,C。②A柱子上有从上到下依次增大的圆盘。③我们要将A柱子上的圆盘转移到C柱子上，转移之后盘子形状还是从上到下依次增大。④过程中可以通过B柱子去临时存放。⑤盘子在转移过程中小的盘子只能在大盘子的上方。

汉诺塔的原理实现

话不多说，汉诺塔实在有点抽象，接下来我将通过结合动态图片进行对汉诺塔的实现原理的介绍

---

我的总体讲解原则是，由简入繁。所以我们先从一片圆盘（n=1）开始讲起

图中我们可以看到当n=1的时候，我们是可以把A柱子移到C柱子达到目标，这个简单我提一嘴就一笔带过了

---

接下来我们来看n=2的时候的运行情况

---

由图中我们可以看出当A柱的总盘子数大于1的时候，要使从盘子原封不动从A柱移动到C柱子。且大盘子只能在小盘子下面，那我们只能先把上面的小盘子先暂时存到B柱作为过渡，然后我们就可以把A柱上的最大的盘子移动到C柱子，最后把B柱子上的小盘子移动到C柱子就可以了。我们通过总结这段运行过程可以发现：我们只要将n-1个盘子，(n代表最底下的盘子),一次性移动到B柱子上进行过渡，然后第n个盘子移动到C柱子就可以了，然后再把B柱上的盘子整体移动到C柱子就可以完成了。用更精简的语言来描述就是：先A->B，然后A->C，最后B->C

---

我们再来看一个n=3的运行图

---

---

怎么样？看完了n=3的动图演示，是不是感觉一脸懵逼？？？(反正我昨天是这样的qwq)。话不多说，我就来一步一步拆解一下n=3的运行机理。在这之前呢，我们要明确一下我们在n=2的时候得出的结论：先A->B，然后A->C，最后B->C。这个法则将贯穿全文，无论n的值为多少

---

原理分析

这里我提前说明一下，我定义最左边的柱子为A，中间的柱子为B，最右边的柱子为C

第一步拆解

我们知道n=2的时候，程序的运行步骤是先从A->B将(n-1)部分的盘子移动到B柱寄存，然后执行A->C，将最底下标号为n的盘子移动到C，最后执行B->C将寄存在B柱子的(n-1)个柱子移动到C柱子。那我们分析n=3的时候我们就可以将下图蓝色盘子上方的盘子（图中阴影部分）抽象成一个整体，那我们要求的n=3，3个盘子的转移问题就变成了n=2转移两个盘子的问题。

接下来我们将抽象后的盘子进行转移，按照n=2的转移办法，粉色的盘子会被投放到B柱子上，然后蓝色的盘子将会被投放到C柱子上。(状态图如下图)

到了这个状态之后，按照转移的顺序，我们应该把粉色的盘子转移到C柱就可以完成任务了。但是！我们这个粉色的盘子是我们抽象出来的，它内部还有俩盘子呢：所以我们要对着两个盘子再次进行分析。

第二步拆解

由于第一步我们是将蓝色盘子上方的两个盘子抽象成了一个，我们程序执行的时候可不能整体移动，所以我们要对这个粉色的整体盘子再次进行拆解，根据第一步拆解的最后步骤我们可以看到，我们第二步拆解的时候，粉色盘子是位于B柱子的时候进来的，那个视角的参照物我们是基于粉色和蓝色盘子的视角(主视角)来看的。所以从那个视角来看，我们的粉色盘子是从B柱子进入第二步拆解。既然我们进入了第二步拆解，我们的视角参照物应该切换成基于黄色和绿色盘子的视角(次视角)，我们要从这个视角来重复执行A->B,A->C，B->C的步骤，但是这里要注意，我们最终的观察角度是通过主视角来看的，于是主视角所看到的B柱子其实对应的是次视角的C柱子：因为我们是从主视角的B柱子进入的次视角，在次视角中最后是要将盘子从A->C，随后返回给主视角，所以说次视角的C相当于主视角的B柱子，次视角的B相当于主视角的C柱子。接下来我们通过图片来加深一下理解
如下图。

接下来我们来看一下次视角状态下盘子移动后的A->B，A->C的中间结果

那我们的主视角是什么样的情况呢，接下来我们来看一下次视角对应的主视角盘子移动情况

看到这里我们相信你就明白了吧，每一次对抽象盘子进行拆解的时候，它们都会进入以抽象盘子为基础的次视角，但是我们从外部来看到的应该是没有拆解前的主视角的移动情况。所以啊，我们再看看一遍n=3的时候的运行图，来加强一下理解。我觉得最难的点在于我们人总是会惯性地从我们的主视角去看，而每一次拆解进入的时候是抽象盘子的次视角在执行A->B,A->C，B->C的迁移动作。这导致了我们看的很懵逼，越看越难理解。

好了，思路到这里我们点到为止，大致的运行思路就是这样，关键在于主次视角的切换的理解，接下来我们将为什么用递归来实现汉诺塔

为什么用递归算法实现？

要解决这个疑问呢，我们首先要搞明白，汉诺塔的盘子的迁移特性和递归的特性，它们两者之间的有没有共通性才是我们选择递归来实现汉诺塔的关键。那下面我来分析一下，看看它们之间是不是真的有共通点

汉诺塔盘子的迁移特性

我们通过对两个以上的盘子进行抽象，让我们把要解决的问题转换成一个个n=2的盘子迁移问题，直到n=1为止。比如我们总的n=3，那我们第一步就要把三个盘子中的两个抽象成1个，保留最底下的那个盘子。这样我们要解决的问题又变成了解决n=2的盘子迁移问题。换句话来我们将复杂的问题，通过层层外包进行了分布化处理

递归的特性

递归可以类比成公司领导下发秘密任务，通过层层下属的反馈最后达到完成任务的目的。假如老板A准备发了一则秘密任务“test”，于是老板把他的亲信"B"高管叫过来了，说你去帮我完成，完成后给予他反馈。然后"B"高管肯定也不会自己干的，于是它就把任务告诉了他的亲信”C“，让C完成之后给予反馈。

怎么样？看了汉诺塔的迁移特性和递归的特性，有没有发现他们其实都是在通过层层外包，最后将问题转换成最简单的问题再去解决。最后达到将复杂的问题简单化的目标。所以我们完全可以使用递归算法去实现汉诺塔问题！！

代码实现

知道了为什么能用递归算法实现汉诺塔问题，接下来我们就来感受一下在代码下的汉诺塔实现，这里我给出两个版本，一个是python版本，一个是c++版本。

---

c++版本

&nbsp;#include<bits/stdc++.h>&nbsp;using namespace std;&nbsp;int sum = 0, m;&nbsp;void hanoi(char x,char y,char z,int n){//x，y，z分别代表A,B,C柱子&nbsp; &nbsp; &nbsp;if(n==1) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;sum++;&nbsp; &nbsp; &nbsp; &nbsp; cout<<"#"<<n<<": "<<x<<"->"<<z<<endl;//A->C&nbsp; &nbsp;  }//当n=1，也就是只有一个盘子的时候我们直接把盘子丢给C柱子即可&nbsp; &nbsp; &nbsp;else {//否则我们就要进入else语句，通过不断的抽象化盘子，去简化问题&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;hanoi(x,z,y,n-1);//抽象化盘子将A->B柱子&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;sum++;//&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;cout<<"#"<<n<<": "<<x<<"->"<<z<<endl;//执行完抽象化的盘子之后，这里我们是将最底下的那个盘子直接移动到C柱子上&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;hanoi(y,x,z,n-1);//最底下的盘子我们已经在上面移动到了C柱子，接下来我们把暂存在B柱子的盘子移动到C柱子就好了，这段代码就是实现这个功能B->C柱子&nbsp; &nbsp;  }&nbsp;}&nbsp;int main(){&nbsp; &nbsp; &nbsp;int n; &nbsp; &nbsp;cin>>n>>m;&nbsp; &nbsp; &nbsp;hanoi('A','B','C',n);&nbsp; &nbsp; &nbsp;cout<<sum<<endl;&nbsp; &nbsp; &nbsp;return 0;&nbsp;}

当我们执行抽象化盘子从B柱子->柱子C的时候

 hanoi(y,x,z,n-1);//最底下的盘子我们已经在上面移动到了C柱子，接下来我们把暂存在B柱子的盘子移动到C柱子就好了，这段代码就是实现这个功能

程序通过递归下一次会进入A->B柱的代码：

 hanoi(x,z,y,n-1);//抽象化盘子将A->B柱子

**发现没有？这里有一个主次视角的转换。我来举个例子好了比如我们先执行hanoi(y,x,z,n-1); 这里y=B,x=A，z=C，代入可以得到hanoi(B,A,C,n-1);，接着执行hanoi(x,z,y,n-1); 这里我们将刚刚函数读入的x，y，z对应填入这个函数，可以得到hanoi(A,,C,B,n-1); 文字有点不好描述，请看下面的动图演示：(还是以n=3进入n=2的数据作为例子)

所以我们从n=3的主视角看到的就是如下的运动情况：

看到没有！！主视角的黄色盘子第一步移动就去了C盘子，C盘子就对应了次视角的B盘子

---

Python版本

def move(n,a,b,c): if n == 1:     print(a,"--->",c)//解决当盘子只剩一个的时候的迁移问题
 else:    move(n-1,a,c,b)//将抽象化的盘子从A->B    print(a,"--->",c)
//把最底下的盘子从A->C柱子  
  move(n-1,b,a,c)//把抽象的盘子从B->C柱子

写在最后

我只能说汉诺塔这个问题，如果单纯告诉程序去运行思路，那看起来是挺简单的，但是深入思考它内部的运行原理是挺抽象的，因为里面涉及了主次视角的转变，而我们又总是以主视角去观察盘子移动的，这就让人感觉产生了汉诺塔运行起来毫无规律的误解。以上就是我对汉诺塔的个人理解。本人水平有限。如果理解错了，请见谅，欢迎指正。

---

• 分类： 数据结构
• 标签： 无标签