递归

定义

一个函数自己直接或间接调用自己

递归满足三个条件

1.递归必须得有一个明确的终止条件
2.该函数所处理的数据规模必须在递减
3.这个转化必须是可解的

循环和递归的关系

递归： 易于理解 速度慢 存储空间大
循环：不易理解 速度快 存储空间小

递归的应用

树和森林都是以递归的方式定义的
树和图的很多算法都是以递归来实现的
很多的数学公式都是以递归的方式定义的：斐波拉契序列

函数的调用

当一个函数的运行期间调用另一个函数时，在运行被调函数之前，系统需要完成三件事：
1.将所有的实际参数，返回地址等信息传递给被调函数保存
2.为被调函数的局部变量（也包括形参）分配存储空间
3.将控制转移到被调函数的入口

从被调函数返回主调函数之前，系统也要完成三件事
1.保存被调函数的返回结果
2.释放被调函数所占的存储空间
3.依照被调函数保存的返回地址将控制转移到调用函数

当有多个函数相互调用时，按照“后调用先返回”的原则，上述函数值间信息传递和控制必须借助“栈”来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就在栈顶分配一个存储空间，进行压栈操作，每当一个函数退出时，就释放它的存储区，就进行出栈操作，当前运行的函数永远都在栈顶位置

A函数调用A函数和A函数调用B函数在计算机看来是没有任何区别的，只不过用我们日常的思维方式理解比较怪异而已

汉诺塔代码:

# include<stdio.h>

void hannuota(int n, char A,char B,char C){

    /**
        如果是一个盘子
            直接将A柱子上的盘子从A移到C
        否则
            先将A柱子上的 n - 1个盘子借助C移到B
            直接将A柱子上的盘子从A移到C
            最后将B柱子上的n-1个盘子借助A移到C
      */

    if(1 == n){
        printf("将编号为%d的盘子直接从%c柱子移到%c柱子\n",n,A,C);
    }else{
        hannuota(n-1,A,C,B);
        printf("哈哈哈将编号为%d的盘子直接从%c柱子移到%c柱子\n",n,A,C);
        hannuota(n-1,B,A,C);
    }
}
int main(void){
    char a = 'A',b = 'B',c= 'C';
    hannuota(3,a,b,c);
    return 0;
}