前言：什么是递归？
1、递归就是“大事化小，小事化了”
递归是编程中一种非常常用的解决问题的方法，它可以把”大事化小，小事化了“，从而轻松的解决问题。
·
2、什么是 递归
所谓递归：就是大事化小，小事化了。
对于一个大问题，给分解成多个具有相同性质的子问题，子问题再分解成多个子子问题...
最终递归触底，取得结果，然后回溯，取得上一级稍大一点的问题的结果，就这样逐步回溯，最终取得整个大问题的结果。
通常递归涉及到函数调用自身，用循环解决的问题，递归都可以解决。
使用递归，可以让我们的程序变得更优雅简洁，逻辑上可读性更强。
3、详情请看：
https://blog.csdn.net/qq_44750696/article/details/124643587
https://blog.csdn.net/qq_44750696/article/details/124643587
·
深度优先遍历-DFS：
2.1，简介：
主要思路是从图中一个未访问的顶点 V 开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底...，不断递归重复此过程，直到所有的顶点都遍历完成。
它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。
树是图的一种特例(连通无环的图就是树)，接下来我们来看看树用深度优先遍历该怎么遍历。
1、我们从根节点 1 开始遍历，它相邻的节点有 2，3，4，先遍历节点 2，再遍历 2 的子节点 5，然后再遍历 5 的子节点 9。
2、上图中一条路已经走到底了(9是叶子节点，再无可遍历的节点)，此时就从 9 回退到上一个节点 5，看下节点 5 是否还有除 9 以外的节点，没有继续回退到 2，2 也没有除 5 以外的节点，回退到 1，1 有除 2 以外的节点 3，所以从节点 3 开始进行深度优先遍历，如下：
3、同理从 10 开始往上回溯到 6, 6 没有除 10 以外的子节点，再往上回溯，发现 3 有除 6 以外的子点 7，所以此时会遍历 7。
3、从 7 往上回溯到 3， 1，发现 1 还有节点 4 未遍历，所以此时沿着 4， 8 进行遍历,这样就遍历完成了。
完整的节点的遍历顺序如下(节点上的的蓝色数字代表)：
相信大家看到以上的遍历不难发现：
这就是树的前序遍历,实际上不管是前序遍历，还是中序遍历，亦或是后序遍历，都属于深度优先遍历。
递归代码实现
递归实现比较简单，由于是前序遍历，所以我们依次遍历当前节点，左节点，右节点即可，
对于左右节点来说，依次遍历它们的左右节点即可，依此不断递归下去，直到叶节点(递归终止条件)。
代码如下：
public class Solution {
private static class Node {
/**
* 节点值
*/
public int value;
/**
* 左节点
*/
public Node left;
/**
* 右节点
*/
public Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
public static void dfs(Node treeNode) {
if (treeNode == null) {
return;
}
// 遍历节点
process(treeNode)
// 遍历左节点
dfs(treeNode.left);
// 遍历右节点
dfs(treeNode.right);
}
}
模板公式：
写代码的公式就是：先左递归，再右递归；
只不过左递归和右递归的递归条件可能不一样。
其核心就是 for 循环⾥⾯的递归：
在递归调用之前「做选择」，
在递归调用(触底)之后「撤销选择」，