龍進
汉诺单塔问题是一个很经典的递归问题（当然也可以用迭代的方式解决，但是就复杂很多）
本题的英文版是这样的：
（出自C++大学教程英文版第226页）
The Towers of Hanoi is one of the most famous classic problems every budding computer scientist must grapple with . Legend has it that in a temple in the Far East , priests are attempting to move a stack of golden disks from one diamond peg to another . The initial stack has 64 disks threaded onto one peg and arranged from bottom to top by decreasing size . The priests are attempting to move the stack from one peg to another under the constraints that exactly one disk is moved at a time and at no time may a larger disk be placed above a smaller disk . Three pegs are provided , one being used for temporarily holding disks . Supposedly , the world will end when the priests complete their task , so there is little incentive for us to facilitate their efforts .
Let’s assume that the priests are attempting to move the disks from peg1 to peg3. We wish to develop an algorithm that prints the precise sequence of peg-topeg disk transfers.
Display the precise instructions for moving the disks from starting peg to the destination peg. To move a stack of three disks from peg1 to peg3, the program displays the following moves:
1->3
1->2
3->2
1->3
2->1
2->3
1->3
问题翻译及思路分析
简单来说，就是有三个柱子，最左边的柱子上有N个碟子，大小从下往上依次减小。大碟子不能放在小碟子上面。张三想把碟子从第一个柱子移到第三个柱子。要我们开发一个算法去帮助它去实现这个功能。并且我们要打印出每一步的操作。
这道题目难就难在它需要我们把每一步的操作都要输出。（要是不用输出每一步的操作的话，咱们就可以尝试不完备归纳法了，直接算出碟子数量较少时所需要的步数，然后盲猜一波规律，直接写公式下去就好了）
那咋办呢？
这个问题看起来有点复杂，但是我们可以发现，当n=1时，只要1步操作，即把碟子从1柱移动到3柱就可以了。n=2时，需要借助第二根柱子来进行操作，先把一个碟子移到2柱，再从1柱移一个碟子到3柱，最后把二柱的碟子移动到3柱。
三个碟子的话，思路也是类似的，也就是先借助2柱为临时柱子，把前两个碟子移动到2柱，再把第3个碟子移到3柱，接着把剩下两个碟子移动到3柱。
接着往下思考，会发现这些操作都有着类似性。就是最终他们都可以被分解为从一个柱子移动到另一个柱子的操作。
再继续分析，得出思路，只要先把n-1个碟子移动到2柱，再把第n个碟子从1柱移动到3柱，最后把n-1个碟子从2柱移动到3柱。就完成了。那么接下来对于这n-1个碟子的操作，就类似于把第2个柱子看成1柱，把1柱看成2柱，再继续操作就可以了。如此循环就会发现，不管是多少个柱子，问题都能被分解为最小的单位——从一个柱子移动到另一个柱子的问题。
那么我们会发现，这个汉诺单塔问题可以每一步的操作都是一样的，都能往下细分直至分解为n=1时的情景。那么就选用递归算法。
再接下去分析，就发现我们在每次递归的时候，需要传入4个参数，即要本次目标要移动的碟子的数量、从哪里移、到哪里去、临时柱子是哪根。
并且，调用递归的函数不需要用到被调用的函数传回来的数值，所以，我们void函数即可实现功能。
C++代码实现
#include<cstdio>
using namespace std;
int js=0;
void calculate(int num, int from, int to,int tmp )
{
if (num == 1)
{
printf("%d->%d\n", from, to);
js++;
}
else
{
calculate(num - 1,from, tmp,to);
calculate(1, from, to, tmp);
calculate(num - 1, tmp, to, from);
}
}
int main()
{
int n;
scanf_s("%d", &n);
calculate(n, 1, 3, 2);
printf("\nSTEPS=%d", js);
}思考
在递归问题中，关键点在于判断问题是否可以被分解为更简单的相同的单元，就是说每一次其实执行的是类似的操作，复杂问题是否可以被分解为若干相同的简单问题。递归一定要有递归终点，否则运行的时候就会无限执行下去或者异常报错退出。
