一、前言

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

---

二、准备工作

关于递归函数

递归函数是一种自己调用自己的函数，在这种函数在解决某些复杂问题中给人们带来方便。
但值得一提的是：函数调用自身的过程中必定存在可使递归调用终止的条件,否则导致出现无限递归。而且，这种函数本质上并不适合人脑使用。因为递归函数具有计算量大，层次深（人工计算容易混乱）
的特点。

递归最重要的两点必须要注意：

一、一定要让递归的函数越来越接近终止条件。如果函数在递归过程中不接近终止条件，那么就会出现无限递归！这个很好理解！
二、结束条件一定要设计好。如果没有设置好合适的结束条件，将会使得计算结果不达预期。

---

三、汉诺塔步数计算

#include<stdio.h>int hanoi1(int n)
{if(n==1){return 1;}else{return 2*hanoi1(n-1)+1;}
}int main(){int num = 0;int result = 0;printf("请输入圆盘的个数\n");scanf("%d",&num);result = hanoi1(num);printf("%d个圆盘的移动次数为：%d次\n",num,result);return 0;
}

详解：函数的设计符合递归函数的两个基本条件：

一、合适的结束条件（当n的值为1的时候，意味着只有一个圆盘时，直接把圆盘从a柱转移到c柱。只需要一步，所以返回值为1）

二、递归的函数越来越接近终止条件（在递归过程中，n不断的减一，知道n==1时，递归函数开始往回折返，最终返回一个确定的值）我们以有三个圆盘来举例：

---

四、汉诺塔步骤打印（绝对详细，仔细看就能看懂 ）

先放代码：

#include<stdio.h>void hanoi2(int n,int a,int b,int c)
{if(n==1){printf("%d->%d\n",a,c);}else{hanoi2(n-1,a,c,b);printf("%d->%d\n",a,c);hanoi2(n-1,b,a,c);}
}int main()
{int num = 0;printf("请输入圆盘的个数\n");scanf("%d",&num);hanoi2(num,1,2,3);
}

关于打印步骤的问题困扰了我很久很久，我看了无数篇文章，也搞不清楚作者想表达什么。
如果想当然的看待问题，确实这个代码很容易理解。比如下面这张图，它想表达什么

		hanoi2(n-1,a,c,b);printf("%d->%d\n",a,c);

有的作者是这样表示的：我们把上面的n-1个圆盘通过c，转移到b，最终的n-1个圆盘落在b的位置上。

那么，我想问：printf（"%d->%d\n",a,c） 究竟是把n-1个 a柱子上的圆盘转移到c，还是把a柱子上的圆盘转移到b。如果想表达把a柱子上的n-1个圆盘转移到b，那为什么不写成printf("%d->%d\n",a,b)???

确实，n-1个柱子确实是通过c柱子转移到b柱上，再把最后一个圆盘从A->C。但是，如果这样说，我们将会完全混淆abc到底是柱子，还是柱子上的圆盘这个问题。到底该如何正确看待abc？

---

---

作为初学者，我一度百思不得其解。原来，当我们专注于递归问题时，往往会忽略形参和实参的值传递问题。在此之前，我们先做一个铺垫

铺垫

请看下列C程序：

void test(int a,int b,int c)
{if(a==1){printf("%d->%d\n",a,c);}else{test(a-1,c,b);printf("%d->%d\n",b,c);}}int main()
{test(3,1,2);return 0;
}

请告诉我，这个程序会输出怎样的结果？

---

我们发现，第二行的结果是2->1,也就是当c和b调换位置时，从上一次递归中，b分配到了1，c分配到了2.但是，在输出时，printf中的b依然表示函数定义中的b，而不是函数中显示的b。不懂的人必须在电脑中将程序跑起来，好好理解。

---

换个思路：柱子竟然是可以移动的！我们竟然不能控制圆盘的移动

一、你眼中程序的圆盘移动

二、实际上的圆盘移动

---

从上面两幅图我们可以看到，所谓的printf("%d->%d"a,c);代表的就是从最左边的柱子移到最右边的柱子，而且只能这么移。我们能做的，就是通过变化函数中abc的位置，达到正确移动的目的。这是上面函数代表的真正意思！

以num = 3为例

具体步骤如下图：
通过这个，我想已经攻克了汉诺塔最难的部分，理解了在函数中abc确实属于柱子，但是我们不能改变移动圆盘的路径，只能不断交换柱子的摆放位置，来达到最终的效果。