递归

1、递归基本概念

        递归的意思就是不停的调用自己，但是我们要知道的是我们的计算机资源是有限的，一般来说递归的层数不能太深（特别是自己写的程序有问题容易资源耗尽！）。递归通常来说是程序写着简洁但是人的思维量比较大同时计算机的执行效率没有直接写的代码效率高，因为存在函数的不停调用，在计算内部调用函数是开销比较大的。什么是递归什么是自己调用自己，举个简单的例子：

int mul(int x){
    x--;
    mul(x);
}

我们能够清晰的看见上面的程序存在自己调用自己的情况，那么这种就叫做递归，只是上面的递归并不规范！甚至是有问题的，为什么呢？因为我们思考一下这个函数的执行过程如下：

当我们传入x = 5

第一次执行：x--   --------> x变成了4，然后再调用自己，x=4作为参数传入

第二次执行：x--  ---------->x变成了3，然后再调用自己，x=3作为参数传入

。。。

这个程序永远不会结束，

所以从上面的例子我们可以看出来写递归喝循环一样，必须要有个结束条件，我们称之为出口！加入现在我有一道题目是我要求解一个数的阶乘，那么我们的递归程序可以写成：

// 先写一个简单的，这是个全局变量
int result = 1;
 
void mul(int x){
    // 这就是我们说的出口
    if(x==0) return;
    
       
    result *= x;
 
    // 递归
    mul(x-1);
}

你可能会说上面这个例子我用一个循环就很好的解决了，确实是递归大部分能转化成循环（特别是while循环，但是你的思考量将会提高N倍！！！）递归可以让我们不用纠结于中间的复杂过程，你只用专注于分支条件和出口即可！

        现在我们来优化上面的简单的递归程序，通常我们的c语言中不喜欢用全局变量，但是程序再递归的时候，我们需要的有记忆的变量不能直接申请再函数中（有记忆的变量是指函数每次调用自己的时候需要上一次的值，不能被刷新！我还是举例说明吧：），如果上面的程序我写成：

void mul(int x){
 
    if(x == 0) return;
 
    // 不能这么写，每次都被刷新了，
    int result = 1;
 
    result *= x;
 
    mul(x-1);
}

那么对于这种需要有记忆的变量我们递归通常把其作为参数！让参数帮助我们记忆，所以上面的程序可以优化成：

阶乘递归版本1:

void mul(int x, int result){
    if(x == 0) return;
 
    result *= x;
 
    // 这样就每次帮我们记住了乘积并且传入到了下一次
    mul(x-1,result);
}

当然上面的程序是有问题的，不过问题不在递归，就递归这个问题来说上面的程序是比较优秀的写法了。（问题在于c语言是传值的，穿进去的变量在函数里面修改了在外面是看不出来效果的！）

在提供一个上面的递归版本：

阶乘递归版本2:

int mul(int x){
 
    if(x == 1) return 1;
 
    return x* mul(x-1);
}

着两个版本版本2看着好像简单一些，但是版本1的效率要高很多：

版本1:尾递归，递归的程序放在函数的最后面，并且递归不在任何的表达式中，如版本1

版本2：普通递归，递归的程序不在函数肚饿尾部，或者说在一个表达式中，效率不如尾递归。

详细的可以自己百度！！！

 

至此我们知道了递归最重要的东西：

      1、出口

      2、如何记住需要有记忆的变量

2、为什么要有递归？

就像刚才的例子你肯定会说递归很麻烦，但是我想说的是你naive了，递归真正的优点是：

1、缩小问题的规模

2、可以让我们不用思考中间过程</