递归
是一种非常重要的
算法思想
，无论你是前端开发，还是后端开发，都需要掌握它。在日常工作中，统计文件夹大小，解析xml文件等等，都需要用到递归算法。它太基础
太重要了
，这也是为什么面试的时候，面试官经常让我们手写递归算法。本文呢，将跟大家一起深入挖掘一下递归算法~
什么是递归？
递归，在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。简单来说，递归表现为函数调用函数本身。在知乎看到一个比喻递归的例子，个人觉得非常形象，大家看一下：
❝
递归最恰当的比喻，就是查词典。我们使用的词典，本身就是递归，为了解释一个词，需要使用更多的词。当你查一个词，发现这个词的解释中某个词仍然不懂，于是你开始查这第二个词，可惜，第二个词里仍然有不懂的词，于是查第三个词，这样查下去，直到有一个词的解释是你完全能看懂的，那么递归走到了尽头，然后你开始后退，逐个明白之前查过的每一个词，最终，你明白了最开始那个词的意思。
❞
来试试水，看一个递归的代码例子吧，如下：
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）是先进后出，因此递归过程可以理解为栈出入过程啦~
递归的经典应用场景
哪些问题我们可以考虑使用递归来解决呢？即递归的应用场景一般有哪些呢？
递归解题思路
解决递归问题一般就三步曲，分别是：
这个递归解题三板斧理解起来有点抽象，我们拿阶乘递归例子来喵喵吧~
1.定义函数功能
定义函数功能，就是说，你这个函数是干嘛的，做什么事情，换句话说，你要知道递归原问题是什么呀？比如你需要解决阶乘问题，定义的函数功能就是n的阶乘，如下：
2.寻找递归终止条件
递归的一个典型特征就是必须有一个终止的条件，即不能无限循环地调用本身。所以，用递归思路去解决问题的时候，就需要寻找递归终止条件是什么。比如阶乘问题，当n=1的时候，不用再往下递归了，可以跳出循环啦，n=1就可以作为递归的终止条件，如下：
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/problems/invert-binary-tree/
❞
「题目：」
翻转一棵二叉树。
输入：
4
/ \
2 7
/ \ / \
1 3 6 9
输出：
4
/ \
7 2
/ \ / \
9 6 3 1
我们按照以上递归解题的三板斧来：
「1. 定义函数功能」
函数功能（即这个递归原问题是），给出一颗树，然后翻转它，所以，函数可以定义为：
public TreeNode invertTree(TreeNode root) {}
「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提交一下，就有问题啦，超出时间限制了
