递归

1. 递归的定义

在定义一个函数时出现调用本函数的过程称为递归。

1.1 以下为求 n! 的递归函数，理解一下递归

int fun(int n)
{
    if(n == 1)
        return 1;
    else
        return ( fun(n - 1) * n );
}

1.2 递归的过程（举例求 5 的阶乘 fun(5) ）

递归是代码共享的，也就是用同一个函数的代码，系统会为每一次调用开辟一组储存单元来存放本次调用的返回地址和被中断的函数的参数值。

2. 递归的条件

1.必须是有结束递归的条件

2.必须是有限的调用次数

3.必须是在调用过程中数量规模递减

3. 递归的利弊

利：结构简单，便于阅读

弊：占用内存多，效率低，还可能栈溢出。

补充:

CPU使用栈的方式来支持递归函数的调用操作，进入函数时为局部变量分配存储空间，退出时收回这部分空间。每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出。

4. 递归的应用

4.1 汉诺塔问题

将盘片从 x 移到 z ,且小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘

void Hanoil(int n,char x,char y,char z)
{
    if(n == 1)
        printf("第%d个盘片从%c移到%c",n,x,z);
    else
    {
        Hanoil(n-1,x,z,y);							//将n-1个盘片借助z,从x移动到y
        printf("第%d个盘片从%c移到%c",n,x,y);		   //将第n个盘片从x移动到z
        Hanoil(n-1,y,x,z);							//将剩下的n-1个盘片借助x,从y移动到z
    } 
}

递归