递归的含义就是一个函数自己直接或间接调用自己（是用栈来实现的），这个思想很重要，在后面的图以及树的算法部分还需要用到该思想

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

1.将所有的实参，返回地址等信息传递给被调用函数保存
2.为被调用函数的局部变量分配存储区
3.将控制转移到被调函数的入口
被调用函数返回函数之前，也需要完成三件事：

1.保存被调函数的计算结果，
2.释放被调函数的数据区
3.依照被调函数保存的返回地址将控制转移到调用函数
—–严蔚敏《数据结构（C语言版）》

这个递归操作完成所需要的数据结构就是栈，调用一个函数，就为它在栈顶给分配一个存储区，

函数调用

函数循环调用，如果循环写死，那就是死递归,最终在调取一定数量后终止，因为找不到出口
调用的时候遵循后调用先返回

void f(int n)
{
      n+=2;
    return n;
}
int main (void)
{
    int val;
    val = f(5);
    printf("val = %d",val)
    return 0;
}
//调用前：
//1.main执行到第9行,发现要调用f(),然后会把val=5(实参)还有第10行要执行的地址全部传给f(),
//2.为f()的局部变量n(形参)分配存储空间 --3.执行f()
//调用后：
//1.f()保存运算值，--2.释放形参的空间--3.转到第10行指针指向的地址

写一个递归，应该满足三个条件
1.规模需要递减
2.递归有一个明确的中止条件
3.这种转化必须是可解的（数学问题）（例如循环和递归的使用，不同环境下这个可能并不能通用）

递归和循环的优缺点（比如下面的阶乘）
循环相对不易理解，速度快，占用存储空间小
递归容易理解，速度慢，占用空间大

代码部分写了阶乘，1+…100 汉诺塔等

阶乘

• 循环实现

int main(void)
{
    int val;
    int mult=1;
    printf("please type a number: ");
    printf("val = ");
    scanf("%d",&val);

    for (int i = 1; i <=val; ++i)
        mult = mult*i;
    printf("%d factorial is :%d\n",val,mult);

    return 0;
}

• 递归实现

long f(long n)
{
    if (1==n)
        return 1;
    else
        return f(n-1)*n;
}

int main (void)
{
    printf("%d\n",f(5));

    return 0;
}

上面两个方法还是有漏洞的，对于取值并没有做出精准的考虑

汉诺塔

void hanoi(int n,char one ,char two,char three)
{
    if(n==1)
        move(one,three);
    else
    {
        hanoi(n-1,one,three,two);  //放n-1---从A借助C到B
        move(one,three);//搬空A---最后一个到C
        hanoi(n-1,two,one,three); //放n-1---从B借助A到C
    }
}

void move(char x ,char y)
{
    printf("%c----->%c \n",x,y);
}
//这个输入的数字不能太大，若为n 则需要执行2^n-1,比如三个盘子要移动8-1=7次，你可以试试64个盘子😏  --->2^63
//(这里我粗略算了一下，每秒移动10万次，大约要计算机计算200万年)
//汉诺塔是一个非线性递归，复杂度是2^n-1

机器人在地图寻路也是用递归实现的（A*算法）
树和图的很多算法都是用递归来实现的

最终的代码存放在Github仓库 Recursion部分