递归：

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

(不要写成死递归)

举例：

1. 1+2+3+4+...+100的和

1. 求阶乘
2. 汉诺塔
3. 走迷宫

 

函数的调用（以C语言为例）

当一个函数的运行期间调用另一个函数时，在运行被调用函数之前，系统需要完成三件事：

1. 将所有的实际参数，返回地址（即调用函数的位置，等到调用函数执行完毕后返回这个位置，继续执行下面的代码）等信息传递给被调函数保存
2. 为被调函数的局部变量（也包括形参）分配存储空间
3. 将控制转移到被调函数的入口

从被调函数返回主调函数之前，系统也要完成三件事：

1. 保存被调函数的返回结果
2. 释放被调函数所占的空间（指静态空间，不包括malloc动态分配的空间）
3. 依照被调函数保存的返回地址将控制转移到调用函数

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

 

递归必须满足的条件

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

 

循环和递归

递归

易于理解

速度慢

存储空间大

循环

不以理解

速度快

存储空间小

汉诺塔伪算法

if(n > 1)

{

先把A柱子上的前n-1个盘子从A借助C移到B

将A柱子上的第n个盘子直接移到C

再将B柱子上的n-1个盘子借助A移动到C

}

 

#include 
     
      // Hanoi 汉诺塔void hanoi(int n, char A, char B, char C){    /*    如果是1个盘子        直接将A柱子上的盘子从A移到C    否则        先将A柱子上的n-1个盘子借助C移到B        直接将A柱子上的盘子从A移到C        最后将B柱子上的n-1个盘子借助A移到C    */    if(n == 1)    {        printf("将编号为%d的盘子直接从%c柱子移到%c柱子\n", n, A, C);    }    else    {        hanoi(n - 1, A, C, B);        printf("将编号为%d的盘子直接从%c柱子移到%c柱子\n", n, A, C);        hanoi(n - 1, B, A, C);    }}int main(void){    char ch1 = 'A';    char ch2 = 'B';    char ch3 = 'C';    int n;        printf("请输入要移动盘子的个数：");    scanf("%d", &n);    hanoi(n, 'A', 'B', 'C');    return 0;}
     

 

递归的应用：

数和森林

数和图的很多算法都是递归实现的

很多数学公式