前言递归是一个非常重要的算法思想，无论你是前端开发还是后端开发，都需要掌握它。日常工作中需要递归算法统计文件夹大小，解析xml文件等，太基础太重要，这也是为什么在面试的时候，面试官经常让我们手写递归算法。在这篇文章中，我将和你一起学习递归算法~什么是递归？递归的特点递归与栈的关系递归的应用场景递归是指将一个问题反复分解为同类子问题来求解的方法。简单来说，递归表现为一个函数调用一个函数本身。在知乎看到一个隐喻递归的例子。我个人认为它非常生动。我们来看看：?递归最贴切的比喻就是查字典。我们使用的字典本身就是递归的。为了解释一个词，我们需要使用更多的词。当你查一个字，发现这个字的解释中的某个字还不清楚，于是开始查第二个字。不幸的是，第二个词还有不明白的词，所以你去查第三个词，这样查，直到有一个你完全看懂解释的词，递归就结束了，然后你开始退一步去理解你之前检查的每一个单词，最后，你理解开头的那个单词?下面试水，看一个递归的代码例子，如下：publicintsum(intn){if(n<=1){return1;}returnsum(n-1)+n;}递归的特点其实是，递归有两个显着的特点，终止条件和自调用：自调用：原问题可以分解成子问题问题，子问题和原问题的解法是一样的，就是都调用了自己同一个函数。终止条件：递归必须有一个终止条件，即不能在死循环中调用自己。结合上面的demo代码例子，我们来看一下递归的特点：递归和栈的关系。其实递归的过程可以理解为入栈和出栈的过程。这个比喻只是为了方便读者朋友们更好的理解递归。上面的代码示例计算sum(n=3)的栈图如下：为了更容易理解，我们看一下函数sum(n=5)的递归执行过程，如下：(5)、先sum(5)入栈，然后将原问题sum(5)拆成子问题sum(4)，再入栈，直到终止条件sum(n=1)=1，然后开始出栈。在sum(1)弹出后，sum(2)开始弹出，然后是sum(3)。最后，sum(1)是后进先出，sum(5)是先进后出，所以递归的过程可以理解为入栈出栈的过程~经典应用有哪些问题递归的场景可以考虑用递归来解决吗？即，递归一般的应用场景是什么？阶乘问题二叉树深度汉诺塔问题斐波那契数列快速排序，归并排序（分治算法体现递归）遍历文件，解析xml文件递归解题思路解决递归问题一般分三步曲，分别是：第一步是定义函数。第二步是寻找递归终止条件。第二步是推导函数的等价关系。这个问题的递归解法理解起来有点抽象。让我们以阶乘递归为例。喵～1。定义函数function定义函数function，也就是说，你的函数是干什么的，它是干什么的，换句话说，你要知道递归的原问题是什么？比如需要求解阶乘的问题，定义的函数function是n的阶乘，如下：//factorialofn(n为大于0的自然数)intfactorial(intn){}2.查找递归的终止条件递归的一个典型特征就是必须有一个终止条件，即不能无限循环地调用自身。所以，在用递归思想解决问题的时候，需要搞清楚递归的终止条件是什么。比如阶乘问题，当n=1时，不需要向下递归，可以跳出循环，n=1可以作为递归的终止条件，如下：//n阶乘(n为大于0的自然数)intfactorial(intn){if(n==1){return1;}}3.递归函数的递归等价关系表达式的“本义”是指可以将原问题分解为相似的、更容易求解的子问题，即“本义”既是问题又是子问题问题可以用相同的函数关系来表示。递归函数的等价关系，这一步相当于找到原问题和子问题的关系，如何用公式表达清楚这个函数。”factorial的公式可以表示为f(n)=n*f(n-1)，因此，factorial的递归程序代码可以写成：intfactorial(intn){if(n==1){return1;}returnn*factorial(n-1);}「注意」，并不是所有递归函数的等价关系都像阶乘那么简单，一下子就可以推导出来。我们需要多接触，多积累，多思考，多练习递归题~leetcode案例分析分析一道leetcode递归经典题~?原题链接在这里：https://leetcode-cn.com/problems/invert-binary-tree/?「Title:」反转二叉树。输入：4/\27/\/\1369输出：4/\72/\/\9631我们按照上面的三招解决递归问题：“1.定义函数函数”函数函数（即原题这个递归是)，给一棵树，然后翻转它，所以函数可以定义为：//翻转一棵二叉树*TreeNoderight;*TreeNode(intx){val=x;}*}*/《2.寻找递归终止条件》这棵树什么时候不需要翻转？当然是当前节点为null或者当前节点是叶子节点的时候。因此，加入终止条件为：//InvertabinarytreepublicTreeNodeinvertTree(TreeNoderoot){if(root==null||(root.left==null&&root.right==null)){returnroot;}}”3.等价relationofderivationfunction”原来的问题是你要翻转一棵树，能不能拆分成子问题，分别翻转它的左子树和右子树？子问题是翻转它的左子树，难道不能拆分成，翻转它的左子树的左子树和翻转它的左子树的右子树吗？然后一直翻转到叶节点。嗯，看图就明白了~首先，如果要翻转根节点为4的树，需要“翻转它的左子树（根节点为2）和右子树（根节点为7）”.这就是递归的“交接”过程。那么，根节点为2的树就不是叶节点。需要继续“翻转其左子树（根节点为1）和右子树（根节点为3）”。因为节点1和3都是“叶子节点”，所以返回。这也是一个递归“传”的过程~同理，根节点为7的树不是叶节点，需要翻转“它的左子树（根节点为6）和右子树（根节点为9）”.因为节点6和9都是叶子节点，所以它们也返回。左子树（根节点为2）和右子树（根节点为7）翻转完毕后，这些步骤会“返回”，即递归返回过程，完成翻转树的任务~显然，“递归关系”是：invertTree(root)=invertTree(root.left)+invertTree(root.right);所以，很容易得到下面的代码：theleftsubtreeTreeNodeleft=invertTree(root.left);//反转右子树TreeNoderight=invertTree(root.right);}代码中有一个地方需要注意，翻转一棵树的左右子树后，必须交换左右子树的引用位置root.left=right;root.right=left;所以leetcode的递归经典问题的“终极解法代码”如下：classSolution{publicTreeNodeinvertTree(TreeNoderoot){if(root==null||(root.left==null&&root.right==null)){returnroot;}//反转左子树TreeNodeleft=invertTree(root.left);//反转右子树TreeNoderight=invertTree(root.right);//交换左右子树~root.left=right;root.right=left;returnroot;}}取最终解去leetcode提交代码，并它过去了。递归的问题是递归调用的层次太多，导致栈溢出问题。递归和重复计算导致效率低下。容量有限。当递归调用的层次过多时，会超出栈的容量，从而导致调用栈溢出。事实上，正如我们在上一节中讨论的那样，递归过程类似于出栈和压栈。如果递归次数太多，栈的深度就需要加深。最后，堆栈容量确实不够用。"代码示例如下："/***递归栈溢出测试*/publicclassRecursionTest{publicstaticvoidmain(String[]args){sum(50000);}privatestaticintsum(intn){if(n<=1){return1;}returnsum(n-1)+n;}}"运行结果："Exceptioninthread"main"java.lang.StackOverflowErroratrecursion.RecursionTest.sum(RecursionTest.java:13)如何解决这个堆栈溢出问题？首先，你需要“优化你的递归”，真的需要递归调用那么多次吗？如果真的需要，先“增加JVM的栈空间内存”一点点。如果还是不行，那就需要放弃递归，“优化到其他方案”~重复计算导致程序效率低下。我们再来看一个经典的青蛙跳跃问题：一只青蛙一次最多可以跳1步或2步。求青蛙跳上n级台阶的跳跃方法总数。大多数读者朋友很容易想到下面的递归代码来解决：classSolution{publicintnumWays(intn){if(n==0){return1;}if(n<=2){returnn;}returnnumWays(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)计算了三次……所以这个recursivealgorithm效率低下的原因是有很多重复的计算！“那么，如何解决这个问题呢？”由于重复计算比较多，我们可以先把计算出来的答案保存起来，也就是建立一个备忘录，等下次需要的时候，先去“备忘录”里查看，如果有，就拿直接就可以了，如果没有备忘的话，再计算一遍，就可以省去重新计算的耗时了！这就是“有备忘的解决方案”来看看“有备忘的递归解决方案”吧~一般都是用数组或者hashmap来作为这个“备忘”。假设求解f(10)，加上“备忘录”，我们画一个递归树：“第一步”，f(10)=f(9)+f(8)，f(9)和f(8)两者都需要计算，然后添加到memo中，如下：“步骤2”，f(9)=f(8)+f(7),f(8)=f(7)+f(6)，因为f(8)已经在memo中了，所以可以省略。f(7)和f(6)都需要计算出来，加到memo中~《步骤3》f(8)=f(7)+f(6)，发现f(8),f(7),f(6)都在memo上，可以删掉。所以，使用memo递归算法，递归树就变成了光秃秃的主干，如下：带“memo”的递归算法，子问题数=树节点数=n，求解一个子问题还是O(1),所以“带‘备忘录’的递归算法的时间复杂度是O(n)”。接下来，我们用递归算法加上“memo”来写代码解决青蛙跳问题的超时问题~，代码如下：publicclassSolution{//使用hashmap充当memoMap
