关于java:程序员必备的基本算法递归详解

23次阅读

共计 5519 个字符，预计需要花费 14 分钟才能阅读完成。

前言

递归是一种十分重要的算法思维，无论你是前端开发，还是后端开发，都须要把握它。在日常工作中，统计文件夹大小，解析 xml 文件等等，都须要用到递归算法。它太根底太重要了，这也是为什么面试的时候，面试官常常让咱们手写递归算法。本文呢，将跟大家一起学习递归算法~

  • 什么是递归？
  • 递归的特点
  • 递归与栈的关系
  • 递归利用场景
  • 递归解题思路
  • leetcode 案例剖析
  • 递归可能存在的问题以及解决方案

公众号：捡田螺的小男孩

什么是递归？

递归，在计算机科学中是指一种通过反复将问题合成为同类的子问题而解决问题的办法。简略来说，递归体现为函数调用函数自身。在知乎看到一个比喻递归的例子，集体感觉十分形象，大家看一下：

递归最失当的比喻，就是查词典。咱们应用的词典，自身就是递归，为了解释一个词，须要应用更多的词。当你查一个词，发现这个词的解释中某个词依然不懂，于是你开始查这第二个词，惋惜，第二个词里依然有不懂的词，于是查第三个词，这样查上来，直到有一个词的解释是你齐全能看懂的，那么递归走到了止境，而后你开始后退，一一明确之前查过的每一个词，最终，你明确了最开始那个词的意思。

来试试水，看一个递归的代码例子吧，如下：

public int sum(int n) {if (n <= 1) {return 1;} 
    return sum(n - 1) + n; 
}

递归的特点

实际上，递归有两个显著的特色, 终止条件和本身调用:

  • 本身调用：原问题能够合成为子问题，子问题和原问题的求解办法是统一的，即都是调用本身的同一个函数。
  • 终止条件：递归必须有一个终止的条件，即不能有限循环地调用自身。

联合以上 demo 代码例子，看下递归的特点：

递归与栈的关系

其实，递归的过程，能够了解为出入栈的过程的，这个比喻呢，只是为了不便读者敌人更好了解递归哈。以上代码例子计算 sum（n=3）的出入栈图如下：

为了更容易了解一些，咱们来看一下 函数 sum（n=5）的递归执行过程，如下：

  • 计算 sum（5）时，先 sum（5）入栈，而后原问题 sum（5）拆分为子问题 sum（4），再入栈，直到终止条件 sum（n=1）=1，就开始出栈。
  • sum（1）出栈后，sum（2）开始出栈，接着 sum（3）。
  • 最初呢,sum（1）就是后进先出，sum（5）是先进后出，因而递归过程能够了解为栈出入过程啦~

递归的经典利用场景

哪些问题咱们能够思考应用递归来解决呢？即递归的利用场景个别有哪些呢？

  • 阶乘问题
  • 二叉树深度
  • 汉诺塔问题
  • 斐波那契数列
  • 疾速排序、归并排序（分治算法也应用递归实现）
  • 遍历文件，解析 xml 文件

递归解题思路

解决递归问题个别就三步曲，别离是：

  • 第一步，定义函数性能
  • 第二步，寻找递归终止条件
  • 第二步，递推函数的等价关系式

这个递归解题三板斧了解起来有点形象，咱们拿阶乘递归例子来喵喵吧~

1. 定义函数性能

定义函数性能，就是说，你这个函数是干嘛的，做什么事件，换句话说，你要晓得递归原问题是什么呀？比方你须要解决阶乘问题，定义的函数性能就是 n 的阶乘，如下：

// n 的阶乘（n 为大于 0 的自然数）int factorial (int n){}

2. 寻找递归终止条件

递归的一个典型特色就是必须有一个终止的条件，即不能有限循环地调用自身。所以，用递归思路去解决问题的时候，就须要寻找递归终止条件是什么。比方阶乘问题，当 n = 1 的时候，不必再往下递归了，能够跳出循环啦，n= 1 就能够作为递归的终止条件，如下：

// n 的阶乘（n 为大于 0 的自然数）int factorial (int n){if(n==1){return 1;}
}

3. 递推函数的等价关系式

递归的 转义 ，就是原问题能够拆为同类且更容易解决的子问题，即 原问题和子问题都能够用同一个函数关系示意。递推函数的等价关系式，这个步骤就等价于寻找原问题与子问题的关系，如何用一个公式把这个函数表白分明。阶乘的公式就能够示意为 f(n) = n * f(n-1), 因而，阶乘的递归程序代码就能够写成这样，如下：

int factorial (int n){if(n==1){return 1;}
    return n * factorial(n-1);
}

留神啦，不是所有递推函数的等价关系都像阶乘这么简略，一下子就能推导进去。须要咱们多接触，多积攒，多思考，多练习递归题目滴~

leetcode 案例剖析

来剖析一道 leetcode 递归的经典题目吧~

原题链接在这里哈：https://leetcode-cn.com/probl…

题目： 翻转一棵二叉树。

输出：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

输入：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

咱们依照以上递归解题的三板斧来：

1. 定义函数性能

函数性能（即这个递归原问题是），给出一颗树，而后翻转它，所以，函数能够定义为：

// 翻转一颗二叉树
public TreeNode invertTree(TreeNode root) {
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) {val = x;}
 * }
 */

2. 寻找递归终止条件

这棵树什么时候不必翻转呢？当然是以后节点为 null 或者以后节点为叶子节点的时候啦。因而，加上终止条件就是：

// 翻转一颗二叉树
public TreeNode invertTree(TreeNode root) {if(root==null || (root.left ==null && root.right ==null)){return root;}
}

3. 递推函数的等价关系式

原问题之你要翻转一颗树，是不是能够拆分为子问题，别离翻转它的左子树和右子树？子问题之翻转它的左子树，是不是又能够拆分为，翻转它左子树的左子树以及它左子树的右子树？而后始终翻转到叶子节点为止。嗯，看图了解一下咯~

首先，你要翻转根节点为 4 的树，就须要 翻转它的左子树（根节点为 2）和右子树 (根节点为 7）。这就是递归的 递的过程啦

而后呢，根节点为 2 的树，不是叶子节点，你须要持续 翻转它的左子树（根节点为 1）和右子树（根节点为 3）。因为节点 1 和 3 都是 叶子节点 了，所以就返回啦。这也是递归的 递的过程~

同理，根节点为 7 的树，也不是叶子节点，你须要翻转 它的左子树（根节点为 6）和右子树（根节点为 9）。因为节点 6 和 9 都是叶子节点了，所以也返回啦。

左子树（根节点为 2）和右子树 (根节点为 7）都被翻转完后，这几个步骤就 归来，即递归的归过程，翻转树的工作就实现了~

显然，递推关系式 就是：

invertTree（root）= invertTree（root.left）+ invertTree（root.right）;

于是，很容易能够得出以下代码：

// 翻转一颗二叉树
public TreeNode invertTree(TreeNode root) {if(root==null || (root.left ==null && root.right ==null){return root;}
    // 翻转左子树
    TreeNode left = invertTree(root.left);
    // 翻转右子树
    TreeNode right= invertTree(root.right);
}

这里代码有个中央须要留神，翻转完一棵树的左右子树，还要替换它左右子树的援用地位。

 root.left = right;
 root.right = left;

因而，leetcode 这个递归经典题目的 终极解决代码 如下：

class Solution {public TreeNode invertTree(TreeNode root) {if(root==null || (root.left ==null && root.right ==null)){return root;}
         // 翻转左子树
         TreeNode left = invertTree(root.left);
         // 翻转右子树
         TreeNode right= invertTree(root.right);
         // 左右子树替换地位~
         root.left = right;
         root.right = left;
         return root;
    }
}

拿终极解决代码去 leetcode 提交一下，通过啦~

递归存在的问题

  • 递归调用层级太多，导致栈溢出问题
  • 递归反复计算，导致效率低下

栈溢出问题

  • 每一次函数调用在内存栈中调配空间，而每个过程的栈容量是无限的。
  • 当递归调用的层级太多时，就会超出栈的容量，从而导致调用栈溢出。
  • 其实，咱们在后面大节也探讨了，递归过程相似于出栈入栈，如果递归次数过多，栈的深度就须要越深，最初栈容量真的不够咯

代码例子如下：

/**
 * 递归栈溢出测试
 */
public class RecursionTest {public static void main(String[] args) {sum(50000);
    }
    private static int sum(int n) {if (n <= 1) {return 1;}
        return sum(n - 1) + n;
    }
}

运行后果:

Exception in thread "main" java.lang.StackOverflowError
    at recursion.RecursionTest.sum(RecursionTest.java:13)

怎么解决这个栈溢出问题？首先须要 优化一下你的递归 ，真的须要递归调用这么屡次嘛？如果真的须要，先略微 调大 JVM 的栈空间内存 ，如果还是不行，那就须要弃用递归， 优化为其余计划 咯~

反复计算，导致程序效率低下

咱们再来看一道经典的青蛙跳阶问题：一只青蛙一次能够跳上 1 级台阶，也能够跳上 2 级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

绝大多数读者敌人，很容易就想到以下递归代码去解决：

class Solution {public int numWays(int n) {if (n == 0){return 1;}
    if(n <= 2){return n;}
    return numWays(n-1) + numWays(n-2);
    }
}

然而呢，去 leetcode 提交一下，就有问题啦，超出工夫限度了

为什么超时了呢？递归耗时在哪里呢？先画出 递归树 看看：

  • 要计算原问题 f(10)，就须要先计算出子问题 f(9) 和 f(8)
  • 而后要计算 f(9)，又要先算出子问题 f(8) 和 f(7)，以此类推。
  • 始终到 f(2) 和 f(1），递归树才终止。

咱们先来看看这个递归的工夫复杂度吧，递归工夫复杂度 = 解决一个子问题工夫 * 子问题个数

  • 一个子问题工夫 = f（n-1）+f（n-2），也就是一个加法的操作，所以复杂度是 O(1)；
  • 问题个数 = 递归树节点的总数，递归树的总结点 = 2^n-1，所以是复杂度O(2^n)。

因而，青蛙跳阶，递归解法的工夫复杂度 = O(1) * O(2^n) = O(2^n)，就是指数级别的，爆炸增长的，如果 n 比拟大的话，超时很失常的了。

回过头来，你仔细观察这颗递归树，你会发现存在 大量反复计算，比方 f（8）被计算了两次，f（7）被反复计算了 3 次 … 所以这个递归算法低效的起因，就是存在大量的反复计算！

那么，怎么解决这个问题呢？

既然存在大量反复计算，那么咱们能够先把计算好的答案存下来，即造一个备忘录，等到下次需要的话，先去 备忘录 查一下，如果有，就间接取就好了，备忘录没有才再计算，那就能够省去从新反复计算的耗时啦！这就是 带备忘录的解法

咱们来看一下 带备忘录的递归解法 吧~

个别应用一个数组或者一个哈希 map 充当这个 备忘录。

假如 f(10)求解加上 备忘录，咱们再来画一下递归树：

第一步，f（10）= f(9) + f(8)，f(9) 和 f（8）都须要计算出来，而后再加到备忘录中，如下：

第二步， f(9) = f（8）+ f（7），f（8）= f（7）+ f(6), 因为 f(8) 曾经在备忘录中啦，所以能够省掉，f(7),f（6）都须要计算出来，加到备忘录中~

第三步， f(8) = f（7）+ f(6), 发现 f(8)，f(7),f（6）全副都在备忘录上了，所以都能够剪掉。

所以呢，用了备忘录递归算法，递归树变成赤裸裸的树干咯，如下：

带「备忘录」的递归算法，子问题个数 = 树节点数 =n，解决一个子问题还是 O(1), 所以 带「备忘录」的递归算法的工夫复杂度是 O(n)。接下来呢，咱们用带「备忘录」的递归算法去撸代码，解决这个青蛙跳阶问题的超时问题咯~，代码如下：

public class Solution {
    // 应用哈希 map，充当备忘录的作用
    Map<Integer, Integer> tempMap = new HashMap();
    public int numWays(int n) {
        // n = 0 也算 1 种
        if (n == 0) {return 1;}
        if (n <= 2) {return n;}
        // 先判断有没计算过，即看看备忘录有没有
        if (tempMap.containsKey(n)) {
            // 备忘录有，即计算过，间接返回
            return tempMap.get(n);
        } else {
            // 备忘录没有，即没有计算过，执行递归计算, 并且把后果保留到备忘录 map 中，对 1000000007 取余（这个是 leetcode 题目规定的）tempMap.put(n, (numWays(n - 1) + numWays(n - 2)) % 1000000007);
            return tempMap.get(n);
        }
    }
}

去 leetcode 提交一下，如图，稳了：

还有没有其余计划解决这个问题呢？只有 带备忘录的递归解法 ？其实吧，还能够用 动静布局 去解决

动静布局算法思维怎么解题？咱们下期持续~ 谢谢浏览~

参考与感激

  • [一文学会递归解题] (https://mp.weixin.qq.com/s/He…
  • [动静布局详解] (https://mp.weixin.qq.com/s/1V…

集体公众号

  • 更多干货，关注公众号
  • 回复 pdf，获取学习电子书

正文完
java
发表至： java
2020-10-14
 0
关于java:独立产品灵感周刊-DecoHack-017-互联网真有趣
关于java:Java单元测试技巧之PowerMock
Java冷知识finally中的代码一定会执行吗
java-8-实战读书笔记-第九章-默认方法