简单的聊一聊递归

递归

基本概念

如果从来没接触过递归，这篇文章是不建议看的，如果之前或多或少接触过一些，那还是可以看下去的。递归的思想还是比较简单的，就是有一个函数，在函数的内部自己调用自己，在碰到某个条件之后退出，这个过程就叫做递归。其实递归在现实中也经常能碰到，比如说一个人需要在全英文字典中查一个单词，如果要查的这个单词的解释中有一个单词他不认识，那么他就需要查这个单词，如此一致反复，直到某个单词的解释他全部认识了。
  我们在写代码的时候，递归经常遇到，最简单的就是计算某个数的阶乘。

f(6)
=> 6 * f(5)
=> 6 * (5 * f(4))
=> 6 * (5 * (4 * f(3)))
=> 6 * (5 * (4 * (3 * f(2))))
=> 6 * (5 * (4 * (3 * (2 * f(1)))))
=> 6 * (5 * (4 * (3 * (2 * 1))))
=> 6 * (5 * (4 * (3 * 2)))
=> 6 * (5 * (4 * 6))
=> 6 * (5 * 24)
=> 6 * 120
=> 720

递归的过程就如下图所示：

递归的三大要素

刚开始接触递归，写起来也不是很容易的，这时候还是需要一些套路的，按着这个套路搞，慢慢的由简单到复杂。

第一要素：明确你这个函数想要干什么

对于递归，首先最重要的一件事就是这个函数的功能是什么，它要完成什么样的一件事。这是完全由自己来决定的。换句话讲，我们先不管函数里面的代码是什么，而是先要搞清楚，这里面的函数是干嘛的。

例如定义了一个函数

//算n的阶乘（假设n > 0）
int func(int n)
{

}

这个函数的功能就是算n的阶乘，接着搞第二要素。
  

第二要素：寻找递归结束条件

  前面说过递归就是在函数内部的代码中，调用这个函数本身。所以很重要的一点就是，我们必须找出递归的结束条件，不然的话，程序就会一直自己调用自己。换句话说，我们需要找出当参数为某个值得时候，递归结束，并且直接把结果返回。也就是说，我们必须能根据这个参数的值，直接得出参数的结果是什么。
  例如上面的例子，当n = 1时，我们知道此时func(1) = 1。接着完善代码。

//算n的阶乘（假设n > 0）
int func(int n)
{
    if (n == 1) {
    return 1;
    }
}

  有同学可能会觉得，当n = 2时也可以直接知道func等于多少，那可以把n = 2当做递归的结束条件吗？这个当然是可以的，只要你觉得参数为什么的时候，你能够直接知道函数的结果，那么就可以直接把这个参数作为结束的条件。所以下面的这段代码也是可以的

//算n的阶乘（假设n > 0）
int func(int n)
{
    if (n <= 2) {
    return n;
    }
}

第三要素：找出函数的等价关系式

   第三要素就是，我们需要不断缩小参数的范围，缩小之后，我们可以通过一些辅助变量或者操作，使得我们可以通过一些辅助变量或者操作，使得原函数的结果不变。
   例如func(n)这个范围比较大，我们可以让func(n) = n func(n - 1)。这样范围就由n变成了n - 1，范围变小了。
其实说白了，就是要找到原函数的一个等价关系式，f(n)的等价关系式就是n f(n - 1)。一般情况下寻找等价关系式是最难的一步，一般找到了等价关系式之后，建议在回头看看递归结束条件，看一下是否所有的情况都有考虑到。我们把之前的代码补全：

//算n的阶乘（假设n > 0）
int func(int n)
{
    if (n <= 2) {
    return n;
    }
    return f(n - 1) * n;
}

这就是递归最重要的三要素，每次做递归的时候，你就强迫自己试着去寻找这三个要素。

例题1:斐波那契数列

   斐波那契数列的是这样一个数列：1、1、2、3、5、8、13、21、34….，即第一项 f(1) = 1,第二项 f(2) = 1…..,第 n 项目为 f(n) = f(n-1) + f(n-2)。求第 n 项的值是多少。

1.函数的功能

假设func(n)就是求第n项的值,代码如下：

int func(n)
{

}

找出递归结束的条件

显然 当n = 1或者n = 2的时候，我们可以轻松知道func(1) = func(2) = 1。所以递归的结束条件可以是n <= 2.代码如下：

int func(n)
{
    if (n <= 2) {
        return 1;
    }
}

第三要素：找出函数的等价关系式

题目已经把等价关系式给我们了，所以我们很容易就能够知道 f(n) = f(n-1) + f(n-2)。最终代码如下：

int f(int n){
    // 1.先写递归结束条件
    if(n <= 2){
        return 1;
    }
    // 2.接着写等价关系式
    return f(n-1) + f(n - 2);
}

例2：小青蛙跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

1、第一递归函数功能

假设func(n)的功能就是求青蛙上一个n级的台阶共有多少种方法，代码如下：

int f(int n)
{

}

2、找出递归结束的条件

求递归结束的条件一般就直接把n压到很小的地方就行了，因为n越小，我们就越容易直接算出func(n)，所以当n = 1时，func(1) = 1.代码如下：

int f(int n)
{
    if (n == 1) {
        return 1;
    }
}

3：找出函数的等价关系式

每次跳的时候，小青蛙可以跳一个台阶，也可以跳两个台阶，也就是说，每次跳的时候，小青蛙有两种跳法。

第一种跳法：第一次我跳了一个台阶，那么还剩下n-1个台阶还没跳，剩下的n-1个台阶的跳法有f(n-1)种。
第二种跳法：第一次跳了两个台阶，那么还剩下n-2个台阶还没，剩下的n-2个台阶的跳法有f(n-2)种。
所以，小青蛙的全部跳法就是这两种跳法之和了，即 f(n) = f(n-1) + f(n-2)。至此，等价关系式就求出来了。于是写出代码：

int f(int n){
    if(n == 1){
        return 1;
    }
    ruturn f(n-1) + f(n-2);
}

大家觉得上面的代码对不对？
答是不大对，当 n = 2 时，显然会有 f(2) = f(1) + f(0)。我们知道，f(0) = 0，按道理是递归结束，不用继续往下调用的，但我们上面的代码逻辑中，会继续调用 f(0) = f(-1) + f(-2)。这会导致无限调用，进入死循环。
修改一下递归结束条件，代码如下：

int f(int n){
    //经过分析，f(2)=2也是一个临界条件。
    if(n <= 2){
        return n;
    }
    ruturn f(n-1) + f(n-2);
}

有关递归的一些优化思路

1.考虑是否重复计算

如果使用递归不进行优化的话，会有很多很多子问题被重复计算，比如计算斐波那契数列的时候。

看到没有，递归计算的时候，重复计算了两次 f(5)，五次 f(4)。。。。这是非常恐怖的，n 越大，重复计算的就越多，所以我们必须进行优化。
如何优化？一般我们可以把我们计算的结果保存起来，例如把 f(4) 的计算结果保存起来，当再次要计算 f(4) 的时候，我们先判断一下，之前是否计算过，如果计算过，直接把 f(4) 的结果取出来就可以了，没有计算过的话，再递归计算。
那用什么保存呢？一般用数组或者hashmap来保存。我们这次用数组保存，我们那n当做数组的下标，f(n)作为数组的值，这样就可以写成：arr[n] = f(n).由于f(n)还没有计算过，我们先让arr[n]等于一个特殊值，一般我们取-1.
当我们要判断时，如果arr[n] = -1,就说明f(n)没有计算过，否则,f(n)就已经计算过了，直接把值取出来用就行了，代码如下：

int func(int n)
{
    if (n <= 2) {
        return 1;
    }
    if (arr[n] != -1) {
        return arr[n];
    } else {
        arr[n] = f(n - 1) + f(n - 2)
        return arr[n];
    }
}

也就是说，使用递归的时候，必要 须要考虑有没有重复计算，如果重复计算了，一定要把计算过的状态保存起来。

再优化：

int func(int n)
{
    int arr[n] = {-1};
    arr[0] = 1;
    arr[1] = 1;
    
    for (int i = 0; i < n; i++) {
        if (arr[i] == -1) {
            arr[i] = arr[i - 1] + arr[i - 2]
        } 
    }
    return arr[n - 1];
}

例三：有一个M*N的棋盘，一个小兵想要从左下角走到右上角，只能向又或者向上，一共有多少种走法。

1、第一递归函数功能

假设func(n)的功能就是求小兵走到（m,n）这个位置的时候的总走法数，代码如下：

int f(int x, int y)
{
    
}

2、找出递归结束的条件

当x = 0 && y = 0的时候 ， 连棋盘都没有，所以返回的是0，当x = 1 || y =1 只有一个横条或者一个竖条，所以只有1种走法。

int f(int x, int y)
{
    if (x == 0 && y == 0) {
        return 0;
    }
    if (x == 1 || y == 1) {
        return 1;
    }
}

3：找出函数的等价关系式

当小兵想走到(m,n)这个位置的时候，他只能从(m-1,n)或者(m,n-1)这两个地方走过来，所以func(m,n) = func(m-1,n) + func(m,n-1)得出

int f(int x, int y)
{
    if (x == 0 && y == 0) {
        return 0;
    }
    if (x == 1 || y == 1) {
        return 1;
    }
    return func(x-1,y) + func(x,y-1);
}

优化：

int f(int x, int y)
{   
    arr[m][n] = {-1};
    if (x == 0 && y == 0) {
        return 0;
    }
    if (x == 1 || y == 1) {
        return 1;
    }
    if (arr[m][n] == -1) {
        arr[m][n] = func(x-1,y) + func(x,y-1);
    } else {
        return arr[m][n];
    }
}

再优化：

int func(int arr[],int m,int n)
{
    int tmp[m][n] = {0}
    for(int i = 0; i < m; i++) {
        tmp[i][0] = 1;
        tmp[0][i] = 1
    }
    for (int i = 1;i < m; i++) {
        for (int j = 1;j < n;j++) {
            tmp[i][j] = tmp[i - 1][j] + tmp[i][j - 1];
        }
    }
    return tmp[m - 1][n - 1];
}

写完收工，欢度周末晚上~~~~