为什么你学不会递归?告别递归,谈谈我的一些经验

可能很多人在大一的时候, 就已经接触了递归了, 不过, 我敢保证很多人初学者刚开始接触递归的时候,是一脸懵逼的,我当初也是,给我的感觉就是,递归太神奇了!

可能也有一大部分人知道递归, 也能看的懂递归, 但在实际做题过程中, 却不知道怎么使用, 有时候还容易被递归给搞晕。也有好几个人来问我有没有快速掌握递归的捷径啊。说实话, 哪来那么多捷径啊, 不过, 我还是想写一篇文章, 谈谈我的一些经验, 或许,能够给你带来一些帮助。

递归的三大要素

 

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

对于递归, 我觉得很重要的一个事就是, 这个函数的功能是什么, 他要完成什么样的一件事, 而这个, 是完全由你自己来定义的。也就是说, 我们先不管函数里面的代码什么,而是要先明白,你这个函数是要用来干什么。

例如,我定义了一个函数

// 算 n 的阶乘(假设n不为0)
int f(int n){

}

这个函数的功能是算 n 的阶乘。好了,我们已经定义了一个函数,并且定义了它的功能是什么,接下来我们看第二要素。

 

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

所谓递归, 就是会在函数内部代码中, 调用这个函数本身, 所以, 我们必须要找出递归的结束条件, 不然的话, 会一直调用自己, 进入无底洞。也就是说, 我们需要找出当参数为啥时, 递归结束, 之后直接把结果返回, 请注意, 这个时候我们必须能根据这个参数的值,能够直接知道函数的结果是什么。

例如,上面那个例子,当 n = 1 时,那你应该能够直接知道 f(n) 是啥吧?此时,f(1) = 1。完善我们函数内部的代码,把第二要素加进代码里面,如下

// 算 n 的阶乘(假设n不为0)
int f(int n){
if(n==1){
return 1;
}
}
有人可能会说,当 n = 2 时,那我们可以直接知道 f(n) 等于多少啊,那我可以把 n = 2 作为递归的结束条件吗?

当然可以, 只要你觉得参数是什么时, 你能够直接知道函数的结果, 那么你就可以把这个参数作为结束的条件,所以下面这段代码也是可以的。

// 算 n 的阶乘(假设n>=2)
int f(int n){
  if(n==2){
    return 2;
  }
}

注意我代码里面写的注释, 假设 n >= 2 , 因为如果 n = 1 时, 会被漏掉, 当 n <= 2 时,f(n) = n,所以为了更加严谨,我们可以写成这样:

// 算 n 的阶乘(假设n不为0)
int f(int n){
  if(n<=2){
    return n;
  }
}

 

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

第三要素就是, 我们要不断缩小参数的范围, 缩小之后, 我们可以通过一些辅助的变量或者操作,使原函数的结果不变。

 

例如,f(n) 这个范围比较大,我们可以让 f(n) = n * f(n-1)。这样,范围就由 n 变成了n-1 了,范围变小了,并且为了原函数f(n) 不变,我们需要让 f(n-1) 乘以 n。

说白了,就是要找到原函数的一个等价关系式,f(n) 的等价关系式为 n * f(n-1),即f(n) = n * f(n-1) 。

这个等价关系式的寻找, 可以说是最难的一步了, 如果你不大懂也没关系, 因为你不是天才, 你还需要多接触几道题, 我会在接下来的文章中, 找 10 道递归题, 让你慢慢熟悉起来

找出了这个等价,继续完善我们的代码,我们把这个等价式写进函数里。如下:

// 算 n 的阶乘(假设n不为0)
int f(intn){
  if(n <= 2){
    return n;
  }
  // 把 f(n) 的等价操作写进去
  return f(n-1) * n;
}

至此, 递归三要素已经都写进代码里了, 所以这个 f(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、第一递归函数功能

假设 f(n) 的功能是求第 n 项的值,代码如下:

int f(int n){
}

2、找出递归结束的条件

显然,当 n = 1 或者 n = 2 ,我们可以轻易着知道结果 f(1) = f(2) = 1。所以递归结束条件可以为 n <= 2。代码如下:

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

3、第三要素:找出函数的等价关系式

题目已经把等价关系式给我们了,所以我们很容易就能够知道 f(n) = f(n-1) + f(n-2)。我说过, 等价关系式是最难找的一个, 而这个题目却把关系式给我们了, 这也太容易, 好吧,我这是为了兼顾几乎零基础的读者。

所以最终代码如下:

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

 

搞定,是不是很简单?

零基础的可能还是不大懂,没关系,之后慢慢按照这个模式练习!好吧,有大佬可能在吐槽 太简单了。

案例2:小青蛙跳台阶

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

1、第一递归函数功能

假设 f(n) 的功能是求青蛙跳上一个n级的台阶总共有多少种跳法,代码如下:

int f(int n){

}

2、找出递归结束的条件

我说了,求递归结束的条件,你直接把 n 压缩到很小很小就行了,因为 n 越小,我们就越容易直观着算出 f(n) 的多少,所以当 n = 1时,你知道 f(1) 为多少吧?够直观吧?即f(1) = 1。代码如下:

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

 

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

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

第一种跳法:第一次我跳了一个台阶,那么还剩下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 == ){
    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)。这会导致无限调用,进入死循环

这也是我要和你们说的, 关于递归结束条件是否够严谨问题, 有很多人在使用递归的时候, 由于结束条件不够严谨, 导致出现死循环。也就是说, 当我们在第二步找出了一个递归结束条件的时候, 可以把结束条件写进代码, 然后进行第三步, 但是请注意, 当我们第三步找出等价函数之后, 还得再返回去第二步, 根据第三步函数的调用关系, 会不会出现一些漏掉的结束条件。就像上面,f(n-2)这个函数的调用,有可能出现 f(0) 的情况,导致死循环,所以我们把它补上。代码如下:

int f(int n){
// f(0) = 0,f(1) = 1,等价于 n<=2时,f(n) = n。
  if(n <= 2){
    return n;
  }
ruturn f(n-1) + f(n-2); }

 

最后总结

其实,递归并不难,难的是不去努力和不细心。