广州做网站基本流程,营销网站的设计与实现,搜索引擎排名的三大指标,建设部网站危房鉴定标准规定前言递归是一种非常重要的算法思想#xff0c;无论你是前端开发#xff0c;还是后端开发#xff0c;都需要掌握它。在日常工作中#xff0c;统计文件夹大小#xff0c;解析xml文件等等#xff0c;都需要用到递归算法。它太基础太重要了#xff0c;这也是为什么面试的时候… 前言递归是一种非常重要的算法思想无论你是前端开发还是后端开发都需要掌握它。在日常工作中统计文件夹大小解析xml文件等等都需要用到递归算法。它太基础太重要了这也是为什么面试的时候面试官经常让我们手写递归算法。本文呢将跟大家一起学习递归算法~什么是递归递归的特点递归与栈的关系递归应用场景递归解题思路leetcode案例分析递归可能存在的问题以及解决方案什么是递归递归在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。简单来说递归表现为函数调用函数本身。在知乎看到一个比喻递归的例子个人觉得非常形象大家看一下❝递归最恰当的比喻就是查词典。我们使用的词典本身就是递归为了解释一个词需要使用更多的词。当你查一个词发现这个词的解释中某个词仍然不懂于是你开始查这第二个词可惜第二个词里仍然有不懂的词于是查第三个词这样查下去直到有一个词的解释是你完全能看懂的那么递归走到了尽头然后你开始后退逐个明白之前查过的每一个词最终你明白了最开始那个词的意思。❞来试试水看一个递归的代码例子吧如下public int sum(int n) {if (n 1) {return 1;} return sum(n - 1) n;
}
递归的特点实际上递归有两个显著的特征,终止条件和自身调用:自身调用原问题可以分解为子问题子问题和原问题的求解方法是一致的即都是调用自身的同一个函数。终止条件递归必须有一个终止的条件即不能无限循环地调用本身。结合以上demo代码例子看下递归的特点递归与栈的关系其实递归的过程可以理解为出入栈的过程的这个比喻呢只是为了方便读者朋友更好理解递归哈。以上代码例子计算sumn3的出入栈图如下为了更容易理解一些我们来看一下 函数sumn5的递归执行过程如下计算sum5时先sum5入栈然后原问题sum5拆分为子问题sum4再入栈直到终止条件sumn11就开始出栈。sum1出栈后sum2开始出栈接着sum3。最后呢,sum1就是后进先出sum5是先进后出因此递归过程可以理解为栈出入过程啦~递归的经典应用场景哪些问题我们可以考虑使用递归来解决呢即递归的应用场景一般有哪些呢阶乘问题二叉树深度汉诺塔问题斐波那契数列快速排序、归并排序分治算法体现递归遍历文件解析xml文件递归解题思路解决递归问题一般就三步曲分别是第一步定义函数功能第二步寻找递归终止条件第二步递推函数的等价关系式这个递归解题三板斧理解起来有点抽象我们拿阶乘递归例子来喵喵吧~1.定义函数功能定义函数功能就是说你这个函数是干嘛的做什么事情换句话说你要知道递归原问题是什么呀比如你需要解决阶乘问题定义的函数功能就是n的阶乘如下//n的阶乘n为大于0的自然数
int factorial (int n){}
2.寻找递归终止条件递归的一个典型特征就是必须有一个终止的条件即不能无限循环地调用本身。所以用递归思路去解决问题的时候就需要寻找递归终止条件是什么。比如阶乘问题当n1的时候不用再往下递归了可以跳出循环啦n1就可以作为递归的终止条件如下//n的阶乘n为大于0的自然数
int factorial (int n){if(n1){return 1;}
}
3.递推函数的等价关系式递归的「本义」就是原问题可以拆为同类且更容易解决的子问题即「原问题和子问题都可以用同一个函数关系表示。递推函数的等价关系式这个步骤就等价于寻找原问题与子问题的关系如何用一个公式把这个函数表达清楚」。阶乘的公式就可以表示为 f(n) n * f(n-1), 因此阶乘的递归程序代码就可以写成这样如下int factorial (int n){if(n1){return 1;}return n * factorial(n-1);
}
「注意啦」不是所有递推函数的等价关系都像阶乘这么简单一下子就能推导出来。需要我们多接触多积累多思考多练习递归题目滴~leetcode案例分析来分析一道leetcode递归的经典题目吧~❝原题链接在这里哈https://leetcode-cn.com/problems/invert-binary-tree/❞「题目」 翻转一棵二叉树。输入 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(rootnull || (root.left null root.right null)){return root;}
}
「3. 递推函数的等价关系式」原问题之你要翻转一颗树是不是可以拆分为子问题分别翻转它的左子树和右子树子问题之翻转它的左子树是不是又可以拆分为翻转它左子树的左子树以及它左子树的右子树然后一直翻转到叶子节点为止。嗯看图理解一下咯~首先你要翻转根节点为4的树就需要「翻转它的左子树根节点为2和右子树(根节点为7」。这就是递归的「递」的过程啦然后呢根节点为2的树不是叶子节点你需要继续「翻转它的左子树根节点为1和右子树根节点为3」。因为节点1和3都是「叶子节点」了所以就返回啦。这也是递归的「递」的过程~同理根节点为7的树也不是叶子节点你需要翻转「它的左子树根节点为6和右子树根节点为9」。因为节点6和9都是叶子节点了所以也返回啦。左子树根节点为2和右子树(根节点为7都被翻转完后这几个步骤就「归来」即递归的归过程翻转树的任务就完成了~显然「递推关系式」就是invertTreeroot invertTreeroot.left invertTreeroot.right;
于是很容易可以得出以下代码//翻转一颗二叉树
public TreeNode invertTree(TreeNode root) {if(rootnull || (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(rootnull || (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.StackOverflowErrorat 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递归树才终止。我们先来看看这个递归的时间复杂度吧「递归时间复杂度 解决一个子问题时间*子问题个数」一个子问题时间 fn-1fn-2也就是一个加法的操作所以复杂度是 「O(1)」问题个数 递归树节点的总数递归树的总结点 2^n-1所以是复杂度「O(2^n)」。因此青蛙跳阶递归解法的时间复杂度 O(1) * O(2^n) O(2^n)就是指数级别的爆炸增长的「如果n比较大的话超时很正常的了」。回过头来你仔细观察这颗递归树你会发现存在「大量重复计算」比如f8被计算了两次f7被重复计算了3次...所以这个递归算法低效的原因就是存在大量的重复计算「那么怎么解决这个问题呢」既然存在大量重复计算那么我们可以先把计算好的答案存下来即造一个备忘录等到下次需要的话先去「备忘录」查一下如果有就直接取就好了备忘录没有才再计算那就可以省去重新重复计算的耗时啦这就是「带备忘录的解法」我们来看一下「带备忘录的递归解法」吧~一般使用一个数组或者一个哈希map充当这个「备忘录」。假设f(10)求解加上「备忘录」我们再来画一下递归树「第一步」f10 f(9) f(8)f(9) 和f8都需要计算出来然后再加到备忘录中如下「第二步」 f(9) f8 f7f8 f7 f(6), 因为 f(8) 已经在备忘录中啦所以可以省掉f(7),f6都需要计算出来加到备忘录中~「第三步」 f(8) f7 f(6),发现f(8)f(7),f6全部都在备忘录上了所以都可以剪掉。所以呢用了备忘录递归算法递归树变成光秃秃的树干咯如下带「备忘录」的递归算法子问题个数树节点数n解决一个子问题还是O(1),所以「带「备忘录」的递归算法的时间复杂度是O(n)」。接下来呢我们用带「备忘录」的递归算法去撸代码解决这个青蛙跳阶问题的超时问题咯~代码如下public class Solution {//使用哈希map充当备忘录的作用MapInteger, 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/Hew44D8rdXb3pf8mZGk67w)[动态规划详解] (https://mp.weixin.qq.com/s/1V3aHVonWBEXlNUvK3S28w)
往期推荐
算法图解如何用两个栈实现一个队列真不错图解Java中的5大队列一文详解「队列」手撸队列的3种方法关注我每天陪你进步一点点
