数据结构基础（6）–递归和函数调用–汉诺塔问题C语言实现
最后更新于：2022-04-01 11:18:52
## 函数调用
通常，当一个函数运行期间调用另一个函数时，在运行被调函数之前，系统需要完成3件事：
（1）将所有的实参，返回地址（个人理解是调用被调函数时的下一个语句的地址）等信息传递给被调函数保存。
（2）为被调函数的局部变量分配存储空间。
（3）将控制转移到被调函数入口。
从被调函数返回调用函数之前，系统完成3件事：
（1）保存被调函数的计算结果。
（2）释放被调函数的数据区。
（3）依照被调函数保存的返回地址，将控制转移到调用函数。
## 递归：
一个函数自己直接或间接调用自己。
思想就是：将问题规模不断缩小，化繁为简，求n！转化成（n-1）!,再转换成(n-2)！.......最后转换成(1)!.
有如汉诺塔问题，如果初始有10个砝码，要从A移动到C，这个看起来比较复杂。只要把前9个移动到B，然后移动第10个到Ｃ。那这9个怎么移动呢，也用这种方式。。。这就是递归实现汉诺塔详细代码见最下方
### 循环和递归比较：
递归：
易于理解
速度慢
存储空间大
循环
不易于理解
速度快
存储空间小
### 递归应用：
1.求阶乘
2.1+2+3+4+。。。+100的和
3.汉诺塔
4.走迷宫(CS的实现)
递归的运用：
树和森林就是以递归的方式定义的
树和图的很多算法都是以递归来实现的
很多数学公式就是以递归的方式定义的
斐波拉契序列
12 3 5 8 13 21 34。。。
C语言实现汉诺塔：
~~~
#include<stdio.h>
void hanota(int num,char A,char B,char C)
{
//如果只有一个元素，那么直接把这个元素，移动到C
if(1==num)
{
printf("把第%d个元素从%c移动到%c\n",num,A,C);
}else{
//如果不是第一个元素，先把前n-1个元素，借助C移动到B
hanota(num-1,A,C,B);
//然后把A最下面的元素移动到C
printf("把第%d个元素从%c移动到%c\n",num,A,C);
//然后再把B上的元素借助A移动到C
hanota(num-1,B,A,C);
}
}
int main()
{
char A='A';
char B='B';
char C='C';
hanota(3,A,B,C);
return 0;
}
~~~
现实生活中，如果我们解决的问题比较繁琐，不妨把问题规模减小考虑。