前言：什麼是遞歸？
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 循環⾥⾯的遞歸：
在遞歸調用之前「做選擇」，
在遞歸調用(觸底)之後「撤銷選擇」，