[栈](1.3)Hanoi塔

说实话刚看到这个程序的时候还不太理解题意，后边看了懒猫老师的视频，才有所理解，其实这比之前接触的回溯算法还简单很多。

我们知道，递归与栈是分不开的，在函数的执行函数中，需多次进行自我调用，与汇编程序所设计中主程序和子程序之间的链接及信息交换相类似，在高级语言编制的程序中，调用函数和被调用函数之间的链接及信息交换需要通过栈来进行。

若在函数A中调用了函数B，则称函数A为调用函数，称函数B为被调用函数

通常，在一个函数的运行期间调用另一个函数时，在运行被调用函数之前，系统需先完成3件事

将所有的实在参数、返回地址等信息传递给被调用函数保存
为被调用函数的局部变量分配存储区
将控制转移到被调函数的入口

，而从被调函数返回调用函数之前，系统也应该完成3件工作
1. 保存被调用函数的计算结果
2. 释放被调用函数的数据区
3. 依照被调函数保存返回地址将控制转移到调用函数

当有多个函数构成嵌套调用，按照“后调用，先返回”的原则，上述函数之间的信息传递和控制转移必须通过栈来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为它在栈顶分配一个存储区，每当从一个函数退出时，就释放它的存储区。

我们可以通过游戏来理解，先去找一个Hanoi塔的游戏。

首先需要定义一个移动函数，这个函数用来理解移动过程，所以只需要一个输出语句即可

void move(char x, int n, char z)
{
    printf("%d次第%d个圆盘从%c->%c", ++c, n, x, z);
}

x和z是柱子，n是盘子。

然后主函数内调用Hanoi函数即可。下面是完整代码：

#include<stdio.h>
#include<stdlib.h>
int c = 0;
void hanoi(int, char, char, char);
void move(char, int, char);
int main()
{
    int n;
    printf("请输入盘子个数：");
    scanf_s("%d", &n);

    hanoi(n, '1', '2', '3');

    system("pause");
    return 0;
}
void hanoi(int n, char x, char y, char z)
/*将塔座x上按直径由小到大且自上而下编号为1至n的n个圆盘按规则搬到
塔座z上，y可用作辅助塔座
搬动操作move(x,n,z)可定义为(c是初值0的全局变量，对搬动计数)
printf("%i.Move disk %i from %c to %c\n",++c,n,x,z)
*/
{
    if (n == 1)
    {
        move(x, 1, z);//将编号为1的圆盘从x移到z
    }
    else
    {
        hanoi(n - 1, x, z, y);//将x上编号为1至n-1的圆盘移到y，z作辅助塔
        move(x, n, z);//将编号为n的圆盘从x移到z
        hanoi(n - 1, y, x, z);//将y上编号为1至n-1的圆盘移到z，x作辅助塔
    }
}
void move(char x, int n, char z)
{
    printf("%d次第%d个圆盘从%c柱->%c柱\n", ++c, n, x, z);
}

我们通过游戏来剖析下此段程序

从上述我们知道，递归函数是不断将函数场景压入栈顶，知道达到出口开始出栈，通过程序可知，函数出口条件是：N=1

我们将x，y，z栈取个代号叫1,2,3，盘子从上到下分别为