内容简介:可能很多人在大一的时候,就已经接触了递归了,不过,我敢保证很多人初学者刚开始接触递归的时候,是一脸懵逼的,我当初也是,给我的感觉就是,递归太神奇了!可能也有一大部分人知道递归,也能看的懂递归,但在实际做题过程中,却不知道怎么使用,有时候还容易被递归给搞晕。也有好几个人来问我有没有快速掌握递归的捷径啊。说实话,哪来那么多捷径啊,不过,我还是想写一篇文章,谈谈我的一些经验,或许,能够给你带来一些帮助。为了兼顾初学者,我会从最简单的题讲起!
可能很多人在大一的时候,就已经接触了递归了,不过,我敢保证很多人初学者刚开始接触递归的时候,是一脸懵逼的,我当初也是,给我的感觉就是,递归太神奇了!
可能也有一大部分人知道递归,也能看的懂递归,但在实际做题过程中,却不知道怎么使用,有时候还容易被递归给搞晕。也有好几个人来问我有没有快速掌握递归的捷径啊。说实话,哪来那么多捷径啊,不过,我还是想写一篇文章,谈谈我的一些经验,或许,能够给你带来一些帮助。
为了兼顾初学者,我会从最简单的题讲起!
递归的三大要素
第一要素:明确你这个函数想要干什么
对于递归,我觉得很重要的一个事就是, 这个函数的功能是什么 ,他要完成什么样的一件事,而这个,是完全由你自己来定义的。也就是说,我们先不管函数里面的代码什么,而是要先明白,你这个函数是要用来干什么。
例如,我定义了一个函数
// 算 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(int n){ 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) =1, f(2) = 1。所以递归结束条件可以为 n <= 2。代码如下:
int f(int n){ if(n <= 2){ return 1; } } 复制代码
第三要素:找出函数的等价关系式
题目已经把等价关系式给我们了,所以我们很容易就能够知道 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(int n){ 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 == 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)。这会导致无限调用,进入 死循环 。
这也是我要和你们说的,关于 递归结束条件是否够严谨问题 ,有很多人在使用递归的时候,由于结束条件不够严谨,导致出现死循环。也就是说,当我们在第二步找出了一个递归结束条件的时候,可以把结束条件写进代码,然后进行第三步,但是 请注意 ,当我们第三步找出等价函数之后,还得再返回去第二步,根据第三步函数的调用关系,会不会出现一些漏掉的结束条件。就像上面,f(n-2)这个函数的调用,有可能出现 f(0) 的情况,导致死循环,所以我们把它补上。代码如下:
int f(int n){ //f(0) = 0,f(1) = 1,等价于 n<=1时,f(n) = n。 if(n <= 1){ return n; } ruturn f(n-1) + f(n-2); } 复制代码
有人可能会说,我不知道我的结束条件有没有漏掉怎么办?别怕,多练几道就知道怎么办了。
看到这里有人可能要吐槽了,这两道题也太容易了吧??能不能被这么敷衍。少侠,别走啊,下面出道难一点的。
下面其实也不难了,就比上面的题目难一点点而已,特别是第三步等价的寻找。
案例3:反转单链表。
反转单链表。例如链表为:1->2->3->4。反转后为 4->3->2->1
链表的节点定义如下:
class Node{ int date; Node next; } 复制代码
虽然是 Java 语言,但就算你没学过 Java,我觉得也是影响不大,能看懂。
还是老套路,三要素一步一步来。
1、定义递归函数功能
假设函数 reverseList(head) 的功能是反转但链表,其中 head 表示链表的头节点。代码如下:
Node reverseList(Node head){ } 复制代码
2. 寻找结束条件
当链表只有一个节点,或者如果是空表的话,你应该知道结果吧?直接啥也不用干,直接把 head 返回呗。代码如下:
Node reverseList(Node head){ if(head == null || head.next == null){ return head; } } 复制代码
3. 寻找等价关系
这个的等价关系不像 n 是个数值那样,比较容易寻找。但是我告诉你,它的等价条件中,一定是范围不断在缩小,对于链表来说,就是链表的节点个数不断在变小,所以,如果你实在找不出,你就先对 reverseList(head.next) 递归走一遍,看看结果是咋样的。例如链表节点如下
我们就缩小范围,先对 2->3->4递归下试试,即代码如下
Node reverseList(Node head){ if(head == null || head.next == null){ return head; } // 我们先把递归的结果保存起来,先不返回,因为我们还不清楚这样递归是对还是错。, Node newList = reverseList(head.next); } 复制代码
我们在第一步的时候,就已经定义了 reverseLis t函数的功能可以把一个单链表反转,所以,我们对 2->3->4反转之后的结果应该是这样:
我们把 2->3->4 递归成 4->3->2。不过,1 这个节点我们并没有去碰它,所以 1 的 next 节点仍然是连接这 2。
接下来呢?该怎么办?
其实,接下来就简单了,我们接下来只需要 把节点 2 的 next 指向 1,然后把 1 的 next 指向 null,不就行了? ,即通过改变 newList 链表之后的结果如下:
也就是说,reverseList(head) 等价于 ** reverseList(head.next)** + 改变一下1,2两个节点的指向 。好了,等价关系找出来了,代码如下(有详细的解释):
//用递归的方法反转链表 public static Node reverseList2(Node head){ // 1.递归结束条件 if (head == null || head.next == null) { return head; } // 递归反转 子链表 Node newList = reverseList2(head.next); // 改变 1,2节点的指向。 // 通过 head.next获取节点2 Node t1 = head.next; // 让 2 的 next 指向 2 t1.next = head; // 1 的 next 指向 null. head.next = null; // 把调整之后的链表返回。 return newList; } 复制代码
这道题的第三步看的很懵?正常,因为你做的太少了,可能没有想到还可以这样,多练几道就可以了。但是,我希望通过这三道题,给了你以后用递归做题时的一些思路,你以后做题可以按照我这个模式去想。通过一篇文章是不可能掌握递归的,还得多练,我相信,只要你认真看我的这篇文章,多看几次,一定能找到一些思路!!
我已经强调了好多次,多练几道了,所以呢,后面我也会找大概 10 道递归的练习题供大家学习,不过,我找的可能会有一定的难度。不会像今天这样,比较简单,所以呢,初学者还得自己多去找题练练,相信我,掌握了递归,你的思维抽象能力会更强!
接下来我讲讲有关递归的一些优化。
有关递归的一些优化思路
1. 考虑是否重复计算
告诉你吧,如果你使用递归的时候不进行优化,是有非常非常非常多的 子问题 被重复计算的。
啥是子问题? f(n-1),f(n-2)....就是 f(n) 的子问题了。
例如对于案例2那道题,f(n) = f(n-1) + f(n-2)。递归调用的状态图如下:
看到没有,递归计算的时候,重复计算了两次 f(5),五次 f(4)。。。。这是非常恐怖的,n 越大,重复计算的就越多,所以我们必须进行优化。
如何优化?一般我们可以把我们计算的结果保证起来,例如把 f(4) 的计算结果保证起来,当再次要计算 f(4) 的时候,我们先判断一下,之前是否计算过,如果计算过,直接把 f(4) 的结果取出来就可以了,没有计算过的话,再递归计算。
用什么保存呢?可以用数组或者 HashMap 保存,我们用数组来保存把,把 n 作为我们的数组下标,f(n) 作为值,例如 arr[n] = f(n)。f(n) 还没有计算过的时候,我们让 arr[n] 等于一个特殊值,例如 arr[n] = -1。
当我们要判断的时候,如果 arr[n] = -1,则证明 f(n) 没有计算过,否则, f(n) 就已经计算过了,且 f(n) = arr[n]。直接把值取出来就行了。代码如下:
// 我们实现假定 arr 数组已经初始化好的了。 int f(int n){ if(n <= 1){ return n; } //先判断有没计算过 if(arr[n] != -1){ //计算过,直接返回 return arr[n]; }else{ // 没有计算过,递归计算,并且把结果保存到 arr数组里 arr[n] = f(n-1) + f(n-1); reutrn arr[n]; } } 复制代码
也就是说,使用递归的时候,必要 须要考虑有没有重复计算,如果重复计算了,一定要把计算过的状态保存起来。
2. 考虑是否可以自底向上
对于递归的问题,我们一般都是 从上往下递归 的,直到递归到最底,再一层一层着把值返回。
不过,有时候当 n 比较大的时候,例如当 n = 10000 时,那么必须要往下递归10000层直到 n <=1 才将结果慢慢返回,如果n太大的话,可能栈空间会不够用。
对于这种情况,其实我们是可以考虑自底向上的做法的。例如我知道
f(1) = 1;
f(2) = 2;
那么我们就可以推出 f(3) = f(2) + f(1) = 3。从而可以推出f(4),f(5)等直到f(n)。因此,我们可以考虑使用自底向上的方法来取代递归,代码如下:
public int f(int n) { if(n <= 2) return n; int f1 = 1; int f2 = 2; int sum = 0; for (int i = 3; i <= n; i++) { sum = f1 + f2; f1 = f2; f2 = sum; } return sum; } 复制代码
这种方法,其实也被称之为 递推 。
最后总结
其实,递归不一定总是从上往下,也是有很多是从下往上的,例如 n = 1 开始,一直递归到 n = 1000,例如一些 排序 组合。对于这种从下往上的,也是有对应的优化技巧,不过,我就先不写了,后面再慢慢写。这篇文章写了很久了,脖子有点受不了了,,,,颈椎病?害怕。。。。
说实话,对于递归这种比较抽象的思想,要把他讲明白,特别是讲给初学者听,还是挺难的,这也是我这篇文章用了很长时间的原因,不过,只要能让你们看完,有所收获,我觉得值得!有些人可能觉得讲的有点简单,没事,我后面会找一些不怎么简单的题。最后如果觉得不错,还请给我转发 or 点赞一波!
如果你觉得这篇内容对你挺有启发,我想邀请你帮我三个忙,让更多的人看到这篇文章:
1、 点赞 ,让更多的人也能看到这篇内容(收藏不点赞,都是耍流氓 -_-)
2、 关注我和专栏 ,让我们成为长期关系
3、关注公众号「 苦逼的码农 」,里面已有100多篇原创文章,我也分享了很多视频、书籍的资源,以及开发工具,欢迎各位的关注,第一时间阅读我的文章。
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 为什么你学不会递归?告别递归,谈谈我的一些经验
- 告别调参,AutoML新书发布
- 学习单元测试,告别祈祷式编程
- 告别AJAX实现无刷新提交表单
- 告别 Postman,拥抱 Http Client
- 最简单爬虫rvest_告别复制粘贴
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Data Structures and Algorithm Analysis in Java
Mark A. Weiss / Pearson / 2006-3-3 / USD 143.00
As the speed and power of computers increases, so does the need for effective programming and algorithm analysis. By approaching these skills in tandem, Mark Allen Weiss teaches readers to develop wel......一起来看看 《Data Structures and Algorithm Analysis in Java》 这本书的介绍吧!