汉诺塔攻略（就我一菜鸡的主观解读）

写在前面：我是菜鸡，所有文章都是主观的。我不认为正确性有保证。我是素鸡，请轻喷。

河内塔问题：传说古印度圣庙里有一种游戏叫河内。游戏是在一个有三根杆(编号为A、B、C)的铜板装置上。在A杆上，从下到上，从大到小，依次放置64个金盘(如图1)。游戏目标：将A条上的所有金盘移动到C条上，按照原来的顺序折叠。操作规则：一次只能移动一个板，移动过程中保持大板在下方，小板在所有三根杆的上方。在操作过程中，板可以放置在任何杆A、B和c上。

好吧，那显然，我是个菜鸡，解决不了这个问题。然后搜索答案。一搜就出来了，他们一大堆，按了几下推到了他们面前.培训班广告。好，继续往下看。一个看起来很厉害的老师开始分析：同学们，看看河内塔问题。刚才我们已经递归学习过了。我相信学生们已经掌握了技巧。我们可以把这个问题简化为三个步骤。

(1)将1号至n-1号光盘从A杆移动到B杆，以C杆为中介；

(2)将A栏中剩余的第N个磁盘移动到C栏；

(3)以A-bar为中介；将1号到n-1号光盘从B杆移动到C杆。

然后就开始写代码，然后就写完了，然后就牛逼了！听着，我看起来很蠢。然后我又去搜了几个，解释完全一样，但是没有人详细解释是怎么实现的。具体递归步骤演示强调了以上三个步骤，然后代码就出来了。我的感觉就好像人类从原始社会跳到了火星。以前有人开玩笑说我数学课弯腰捡笔，从此我整个学期数学课都在飞。那是我当时的感受。不同的是，我连腰都没弯，一直盯着黑板。

void Move(char pos1，char pos2){printf('%c-%c '，pos1，pos 2)；}

void Hanoi(int n，char pos1，char pos2，char pos3){if (1==n){Move(pos1，pos 3)；}else{Hanoi(n - 1，pos1，pos3，pos 2)；移动(pos1，pos 3)；河内(n - 1，pos2，pos1，pos 3)；}}

int main(){ int n=0；char pos1=' Achar pos2=' Bchar pos3=' C河内(1，pos1，pos2，pos 3)；河内(2，pos1，pos2，pos 3)；printf(' \ n ')；河内(3，pos1，pos2，pos 3)；printf(' \ n ')；河内(4，pos1，pos2，pos 3)；printf(' \ n ')；返回0；}贴源代码，为什么？大家都知道。不知道直接复制粘贴好不好。

然后我研究了这个东西很久。当然最后还是到了七七八八。跳过我吧，天才。也许我真的很傻。我研究的结论是，你能找到的关于这个问题的解读，有一半以上属于老手不听也能听得懂，新手一脸茫然也听不懂。至少我是这么认为的：我前几次看这段代码，我甚至不知道递归是从哪里进来的，又是从哪里出来的。

言归正传(先是你接受我的傻逼设定，然后就好看多了):

开始之前，先了解大家强调的三个步骤。我想我能理解那个，就是把塔分成两部分，一部分移到B，最下面一层移到C，然后B的移到C，然后我遇到的第一个问题，抛开递归的步骤，就是我真的没看懂3354。按照别人说的，我简单重复了强调的三个步骤。开始或结束，不管塔算几层，都应该有相同的台阶。开头应该是A-B，结尾应该是A-C .但代码随便运行显然不是这样：

你会发现它是交错的。这很容易解释。做一个棋子的时候直接从A列移动到C列，而做两个棋子的时候就要经过B列的周转，可能有人会说，从B列转三块就可以了，用三块的时候，如果把顶块移动到B列，只能把底块放在B列，而不是C列，步数相同。也就是说，当塔楼楼层为单数时，第一步是A到C，最后一步是A到C；而偶数，第一步是A到B，必须以B到c结尾.而代码也是在Hanoi(n-1，pos1，pos3，pos2)这一步中反复递归，不断变换位置，来实现这一点。

不知道为什么没人提这个。可能大家都默认知道了？但是我比较笨，不太懂。第一个写代码的人应该也想过这个问题，而不是简单的按照三个步骤，然后哗哗哗，流畅地写出来。非常聪明！

第二个问题是如何递归？说的通俗一点，程序运行的顺序是什么？这很简单，逐句调试，一个一个运行。以及为什么是这个顺序。直到看到下图和另一篇刚刚出现在某个角落的文章，我才明白为什么它的递归是这样一种运行逻辑。

三个块的例子

我们以n=3为例来详细解释一下。我们需要点对点堆栈的概念。简单来说，在每次递归之前，程序会将当前数据存储在堆栈中(从下到上)。递归结束后，数据会从上到下被向上调用，然后程序会返回到存储数据的地方，继续向后执行。这时，堆栈中的数据也会消失。当程序到达河内函数时，很明显N！=1，持有else.的部分此时hanoi函数中的变量值为hanoi(3，A，B，C)。在执行第八条语句之前，它应该存储在堆栈中。在下递归后，四个值变成hanoi(2，a，c，b)。此时，堆栈中的数据是

在第二个河内(2，A，C，B)之上，在初始河内(3，A，B，C)之下

再运行一次，n为1，执行printf的语句。然后叫hanoi2消失，然后hanoi1结束。也就是有人解释的“跳回”，所以才跳回这里。

我再用n=4一步步来一遍，就不用一开始看主函数了。我直接从hanoi开始，主要介绍n值的变化和程序运行的顺序：

这里是n=4，如果判断是no，在else的第一步执行hanoi，执行完之后，这里是n=3，然后回到if判断，然后第一步回到hanoi，这里n=2，然后判断，回来的时候，n=1，执行Move:

就上面那个东西move，执行完move后，第一步的hanoi语句暂时结束，但还是存储n=2，3，4的值。按顺序，从n=2开始。前两步结束后，继续往下走，进行第二招。第三步，第二个hanoi，n的值变成1，执行if，也就是move。第一步被河内救了(如果判断对错的话，是第一个河内而不是顺序第二个)，所以你每次都要回到第一步河内结束的位置。这时候，n=2的那个已经完成了。排除堆栈，继续n=3。执行move，然后来第二个hanoi，n的值变成2。如果判断失败，它会回来变成1。判断成功后执行该语句。因为上面还有一个n值变成了2，没有处理，所以在返回第一个河内的时候，先调用它，也就是n值还是2。然后移动，那么n变成1，如果执行成功。

当最复数n=4时。首先跳回取n=4执行move，然后遍历第二个hanoi直到n为1，如果成功就执行。N=2第一句hanoi完成后再次出现，执行move，第三步后，N变成1，if执行成功后。第一句hanoi完成后再次出现N=3，执行move，第三步后N变成2。再次判断后，如果第一句河内执行一次就成功了。再次，第一句hanoi结束后n=2，因为上一步n=3第一次变2时if失败，而且是栈中最后一个。

叙述可能复杂繁琐，但还是一步一步说比较好。反正写完之后印象深刻。目的也达到了，希望能帮到人，哪怕是一两个。

最后说一下递归。当你发现问题可以从一个大问题连续拆分成两个，而且拆分方法有迹可循，就是这样。