可能很多人在大一的时候, 就已经接触了递归了, 不过, 我敢保证很多人初学者刚开始接触递归的时候, 是一脸懵逼的, 我当初也是, 给我的感觉就是, 递归太神奇了!
可能也有一大部分人知道递归, 也能看的懂递归, 但在实际做题过程中, 却不知道怎么使用, 有时候还容易被递归给搞晕. 也有好几个人来问我有没有快速掌握递归的捷径啊. 说实话, 哪来那么多捷径啊, 不过, 我还是想写一篇文章, 谈谈我的一些经验, 或许, 能够给你带来一些帮助.
为了兼顾初学者, 我会从最简单的题讲起!
递归的三大要素
第一要素: 明确你这个函数想要干什么
对于递归, 我觉得很重要的一个事就是, 这个函数的功能是什么, 他要完成什么样的一件事, 而这个, 是完全由你自己来定义的. 也就是说, 我们先不管函数里面的代码什么, 而是要先明白, 你这个函数是要用来干什么.
例如, 我定义了一个函数
- // 算 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) = 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 1;
- }
- // 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 点赞一波!
最后推广下我的公众号: 苦逼的码农: 戳我即可关注 https://qr.tschangcun.net/q/zsDeBp , 文章都会首发于我的公众号, 期待各路英雄的关注交流.
来源: https://www.cnblogs.com/kubidemanong/p/10538799.html