程序员必备的基本算法：递归详解

前言递归是一种非常重要的算法思想，无论你是前端开发，还是后端开发，都需要掌握它。在日常工作中，统计文件夹大小，解析xml文件等等，都需要用到递归算法。它太基础太重要了，这也是为什么面试的时候，面试官经常让我们手写递归算法。本文呢，将跟大家一起学习递归算法~什么是递归？递归的特点递归与栈的关系递归应用场景递归解题思路leetcode案例分析递归可能存在的问题以及解决方案什么是递归？递归，在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。简单来说，递归表现为函数调用函数本身。在知乎看到一个比喻递归的例子，个人觉得非常形象，大家看一下：递归最恰当的比喻，就是查词典。我们使用的词典，本身就是递归，为了解释一个词，需要使用更多的词。当你查一个词，发现这个词的解释中某个词仍然不懂，于是你开始查这第二个词，可惜，第二个词里仍然有不懂的词，于是查第三个词，这样查下去，直到有一个词的解释是你完全能看懂的，那么递归走到了尽头，然后你开始后退，逐个明白之前查过的每一个词，最终，你明白了最开始那个词的意思。来试试水，看一个递归的代码例子吧，如下： 递归的特点实际上，递归有两个显著的特征,终止条件和自身调用:自身调用：原问题可以分解为子问题，子问题和原问题的求解方法是一致的，即都是调用自身的同一个函数。终止条件：递归必须有一个终止的条件，即不能无限循环地调用本身。结合以上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的阶乘，如下： 2.寻找递归终止条件递归的一个典型特征就是必须有一个终止的条件，即不能无限循环地调用本身。所以，用递归思路去解决问题的时候，就需要寻找递归终止条件是什么。比如阶乘问题，当n=1的时候，不用再往下递归了，可以跳出循环啦，n=1就可以作为递归的终止条件，如下： 3.递推函数的等价关系式递归的本义，就是原问题可以拆为同类且更容易解决的子问题，即原问题和子问题都可以用同一个函数关系表示。递推函数的等价关系式，这个步骤就等价于寻找原问题与子问题的关系，如何用一个公式把这个函数表达清楚。阶乘的公式就可以表示为 f(n) = n * f(n-1), 因此，阶乘的递归程序代码就可以写成这样，如下： 注意啦，不是所有递推函数的等价关系都像阶乘这么简单，一下子就能推导出来。需要我们多接触，多积累，多思考，多练习递归题目滴~leetcode案例分析来分析一道leetcode递归的经典题目吧~原题链接在这里哈：leetcode-cn.com/problems/in…题目：翻转一棵二叉树。 我们按照以上递归解题的三板斧来：1. 定义函数功能函数功能（即这个递归原问题是），给出一颗树，然后翻转它，所以，函数可以定义为： 2.寻找递归终止条件这棵树什么时候不用翻转呢？当然是当前节点为null或者当前节点为叶子节点的时候啦。因此，加上终止条件就是： 3. 递推函数的等价关系式原问题之你要翻转一颗树，是不是可以拆分为子问题，分别翻转它的左子树和右子树？子问题之翻转它的左子树，是不是又可以拆分为，翻转它左子树的左子树以及它左子树的右子树？然后一直翻转到叶子节点为止。嗯，看图理解一下咯~  首先，你要翻转根节点为4的树，就需要翻转它的左子树（根节点为2）和右子树(根节点为7）。这就是递归的递的过程啦 然后呢，根节点为2的树，不是叶子节点，你需要继续翻转它的左子树（根节点为1）和右子树（根节点为3）。因为节点1和3都是叶子节点了，所以就返回啦。这也是递归的递的过程~ 同理，根节点为7的树，也不是叶子节点，你需要翻转它的左子树（根节点为6）和右子树（根节点为9）。因为节点6和9都是叶子节点了，所以也返回啦。 左子树（根节点为2）和右子树(根节点为7）都被翻转完后，这几个步骤就归来，即递归的归过程，翻转树的任务就完成了~ 显然，递推关系式就是： 因此，leetcode这个递归经典题目的终极解决代码如下： 拿终极解决代码去leetcode提交一下，通过啦~ 递归存在的问题递归调用层级太多，导致栈溢出问题递归重复计算，导致效率低下栈溢出问题每一次函数调用在内存栈中分配空间，而每个进程的栈容量是有限的。当递归调用的层级太多时，就会超出栈的容量，从而导致调用栈溢出。其实，我们在前面小节也讨论了，递归过程类似于出栈入栈，如果递归次数过多，栈的深度就需要越深，最后栈容量真的不够咯代码例子如下： 怎么解决这个栈溢出问题？首先需要优化一下你的递归，真的需要递归调用这么多次嘛？如果真的需要，先稍微调大JVM的栈空间内存，如果还是不行，那就需要弃用递归，优化为其他方案咯~重复计算，导致程序效率低下我们再来看一道经典的青蛙跳阶问题：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。绝大多数读者朋友，很容易就想到以下递归代码去解决： 但是呢，去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)。接下来呢，我们用带「备忘录」的递归算法去撸代码，解决这个青蛙跳阶问题的超时问题咯~，代码如下： 去leetcode提交一下，如图，稳了： 还有没有其他方案解决这个问题呢？只有带备忘录的递归解法？其实吧，还可以用动态规划去解决最后IT行业的道路固然是充满了阳光了，一路上充满了美景，但是也充满了艰苦和崎岖，在突破了之后一路的阴霾，云霄之上，必然是一番广阔的云海。整理了一份关于java的系统化资料，从Javase- ssm-springcloud，包括了面试题，PDF电子书，网上商城项目，个人博客项目，分布式项目等都有想学习Java或者转行，大学生都非常实用，无任何套路免费提供,，加我裙697888503下载，有什么问题都可以来问我在这里说一下，因为我是自学出来的，也深知自学的艰苦，如果你现在也在自学Java，在自学的过程当中有遇见任何关于学习方法，学习路线，学习效率等方面的问题，资料都可以评论留言

本文章由javascript技术分享原创和收集