递归是一个非常重要的算法思想，无论是前台开发还是后台开发都需要掌握。 在日常工作中，统计文件夹大小，解析xml文件等。，都需要使用递归算法。 太基础太重要了，这也是为什么面试的时候，面试官经常让我们手写递归算法的原因。 在本文中，我们将和大家一起学习递归算法~什么是递归？递归的特点递归与栈递归的关系应用场景递归问题解决思路leetcode递归案例分析可能出现的问题及解决方案什么是递归？在计算机科学中，递归指的是一种通过将问题反复分解成相似的子问题来处理问题的方法。 简单来说，递归体现在函数调用函数本身。 在知乎上看到过一个比喻递归的例子，个人觉得很形象。让我们来看看:递归最恰当的比喻是在字典中查找。 我们用的字典本身就是递归，需要用更多的词来合理解释一个词。 当你查一个单词的时候，发现一个单词的解释你还是不明白，于是你开始查第二个单词。可惜第二个单词还有你不理解的单词，你就查第三个单词，以此类推，直到有一个单词的解释你能完全理解。然后递归结束，然后你开始后退，理解你之前查过的每个单词。最后，你明白了第一个词的意思。 我们来试水一下，看一个递归的代码例子，如下:递归的特点其实递归有两个明显的特点，终止条件和自调用:自调用:可以将原问题分解为子问题，子问题和原问题的求解方式相同，即都调用同一个函数。 终止条件:递归必须有一个终止条件，即不能无限地调用自己。 结合上面的演示代码例子，看看递归的特点:递归和栈的关系。其实递归的过程可以理解为进出栈的过程。这个比喻只是为了方便读者朋友更好的理解递归。 上面的代码示例展示了sum(n=3)的入口和出口图:为了更容易理解一个小数字，我们来看看函数sum(n=5)的递归执行过程，如下:计算sum(5)时，sum(5)先放入堆栈，然后将原问题sum(5)拆分成子问题sum(4)，再放入堆栈，直到终止条件sum(n) 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-cn.com/problems/in…标题:翻转一棵二叉树。 我们按照上面递归解题的三轴来说:1。定义函数function(也就是递归的原问题是)，给一棵树，然后翻转。因此，函数可以定义为:2。求递归终止条件。什么时候树不需要翻转？当然，当当前节点为空或者当前节点为叶节点时。 因此，终止条件如下:3。如果要翻转递归函数原问题中的一棵树，能否将其拆分成子问题，分别翻转其左右子树？第一个问题是翻转它的左子树。它能被拆分成，翻转它的左子树和右子树吗？然后一直翻转到叶节点。 嗯，看图了解一下~首先，如果要翻转根节点为4的树，需要翻转它的左子树(根节点2)和右子树(根节点7)。 这就是递归的过程。那么，根节点为2的树不是叶节点。您需要继续翻转它的左子树(根节点1)和右子树(根节点3)。 因为节点1和3是叶节点，所以它们被返回。 这也是一个递归的过程~同样，根节点为7的树也不是叶节点，所以你需要翻转它的左子树(根节点6)和右子树(根节点9)。 因为节点6和9是叶节点，所以它们也被返回。 左子树(根节点为2)和右子树(根节点为7)翻转完毕后，这些步骤就会返回，也就是递归回归过程，翻转树的任务就完成了~很明显，递归关系是:因此，经典递归问题leetcode的最终处理代码是这样的:把最终处理代码拿到leetcode上提交，就通过了~递归中递归调用层次太多，导致堆栈溢出的递归。 当递归调用的层次过多时，会超出堆栈的容量，导致调用堆栈溢出。 事实上，我们在上一节中也讨论了递归过程类似于堆栈。如果递归太多，堆栈的深度就需要更深，最后堆栈容量确实不足。代码示例如下:如何处理这个堆栈溢出问题？首先，你需要优化你的递归。真的需要调用递归这么多次吗？如果真的有必要，先稍微增加JVM的堆栈内存。如果还是失败，就要放弃递归，优化到其他方案~重复计算导致程序效率低。我们来看一个经典的青蛙跳跃问题:一只青蛙一次可以跳一步或者两步。 请青蛙跳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)已经重复计算了三次...所以这个递归算法效率低的原因是有大量的重复计算！那么，如何处理这个问题呢？既然有大量的重复计算，那么我们可以先把计算出来的答案保存下来，也就是创建一个备忘录，等到下次需要的时候，先在备忘录里查一下，如果有，直接拿就行了。如果没有备忘录，我们可以再计算一次，这样可以节省重复计算的时间！这是用memo解决的。我们来看看用memo的递归解法~一般用一个数组或者一个hash map作为这个memo。 假设f(10)解完了，加上备忘录，我们再来画递归树:第一步，f(10)= f(9)+f(8)，f(9)和f(8)都需要计算然后加到备忘录上，如下:第二步，F (9) = f(8)+ F(6)需要计算然后加到备忘录上~第三步，f(8) = f(7)+ f(6)。发现f(8)、F (7)、F (6)都在备忘录里，所以都可以截掉。 所以有了memo递归算法，递归树就变成了光杆，如下:有memo的递归算法，子问题个数=树节点个数=n，处理一个子问题还是O(1)，所以有memo的递归算法的时间复杂度是O(n)。 接下来我们用带“memo”的递归算法解决这个青蛙跳问题的超时问题~，代码如下:去leetcode提交，如图，很稳定:有没有其他解决这个问题的方法？只有备忘录的递归解？其实也可以用动态规划来应对IT行业的最终道路。诚然，这条道路充满阳光和美丽的风景，但它也充满了艰辛和崎岖的条件。冲破了一路的阴霾之后，必然是云海之上的茫茫云海。 我从javase- ssm-springcloud整理了一份关于Java的系统资料，包括面试问题、PDF电子书、网上商城项目、个人博客项目、分布式项目等。都想学Java或者转行。大学生很实际，没有免费提供套路。请加我的裙子69788503下载。如果你有任何问题，请在这里问我。由于我是自学的，我也知道自学的艰辛。如果你现在也在自学Java，如果遇到任何关于学习方法、学习路线、学习效率等方面的问题。在自学的过程中，可以对资料进行评论。