溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文將為大家詳細介紹“java中遞歸的示例分析”，內容步驟清晰詳細，細節處理妥當，而小編每天都會更新不同的知識點，希望這篇“java中遞歸的示例分析”能夠給你意想不到的收獲，請大家跟著小編的思路慢慢深入，具體內容如下，一起去收獲新知識吧。
啥叫遞歸
聊遞歸之前先看一下什么叫遞歸。
遞歸，就是在運行的過程中調用自己。
構成遞歸需具備的條件：
1. 子問題須與原始問題為同樣的事，且更為簡單；
2. 不能無限制地調用本身，須有個出口，化簡為非遞歸狀況處理。
遞歸語言例子
我們用2個故事來闡述一下什么叫遞歸。
1，從前有座山，山里有座廟，廟里有個老和尚，正在給小和尚講故事呢！故事是什么呢？“從前有座山，山里有座廟，廟里有個老和尚，正在給小和尚講故事呢！故事是什么呢？‘從前有座山，山里有座廟，廟里有個老和尚，正在給小和尚講故事呢！故事是什么呢？……’”
2，大雄在房里，用時光電視看著從前的情況。電視畫面中的那個時候，他正在房里，用時光電視，看著從前的情況。電視畫面中的電視畫面的那個時候，他正在房里，用時光電視，看著從前的情況……
遞歸模板
我們知道遞歸必須具備兩個條件，一個是調用自己，一個是有終止條件。這兩個條件必須同時具備，且一個都不能少。并且終止條件必須是在遞歸最開始的地方，也就是下面這樣
public void recursion(參數0) { if (終止條件) { return; } recursion(參數1);}
不能把終止條件寫在遞歸結束的位置，下面這種寫法是錯誤的
public void recursion(參數0) { recursion(參數1); if (終止條件) { return; }}
如果這樣的話，遞歸永遠退不出來了，就會出現堆棧溢出異常(StackOverflowError)。
但實際上遞歸可能調用自己不止一次，并且很多遞歸在調用之前或調用之后都會有一些邏輯上的處理，比如下面這樣。
public void recursion(參數0) {if (終止條件) {return;}可能有一些邏輯運算recursion(參數1)可能有一些邏輯運算recursion(參數2)……recursion(參數n)可能有一些邏輯運算}
實例分析
我對遞歸的理解是先往下一層層傳遞，當碰到終止條件的時候會反彈，最終會反彈到調用處。下面我們就以5個最常見的示例來分析下
1，階乘
我們先來看一個最簡單的遞歸調用-階乘，代碼如下
1public int recursion(int n) {
2 if (n == 1)
3 return 1;
4 return n * recursion(n - 1);
5}
這個遞歸在熟悉不過了，第2-3行是終止條件，第4行是調用自己。我們就用n等于5的時候來畫個圖看一下遞歸究竟是怎么調用的
如果看不清，圖片可點擊放大。
這種遞歸還是很簡單的，我們求f(5)的時候，只需要求出f(4)即可，如果求f(4)我們要求出f(3)……，一層一層的調用，當n=1的時候，我們直接返回1，然后再一層一層的返回，直到返回f(5)為止。
遞歸的目的是把一個大的問題細分為更小的子問題，我們只需要知道遞歸函數的功能即可，不要把遞歸一層一層的拆開來想，如果同時調用多次的話這樣你很可能會陷入循環而出不來。比如上面的題中要求f(5)，我們只需要計算f(4)即可，即f(5)=5*f(4)；至于f(4)是怎么計算的，我們就不要管了。因為我們知道f(n)中的n可以代表任何正整數，我們只需要傳入4就可以計算f(4)。
2，斐波那契數列
我們再來看另一道經典的遞歸題，就是斐波那契數列，數列的前幾項如下所示
[1，1，2，3，5，8，13……]
我們參照遞歸的模板來寫下，首先終止條件是當n等于1或者2的時候返回1，也就是數列的前兩個值是1，代碼如下
1public int fibonacci(int n) {
2 if (n == 1 || n == 2)
3 return 1;
4 這里是遞歸調用；
5}
遞歸的兩個條件，一個是終止條件，我們找到了。還一個是調用自己，我們知道斐波那契數列當前的值是前兩個值的和，也就是
fibonacci(n) =fibonacci(n - 1) + fibonacci(n - 2)
所以代碼很容易就寫出來了
1//1,1,2,3,5,8,13……
2public int fibonacci(int n) {
3 if (n == 1 || n == 2)
4 return 1;
5 return fibonacci(n - 1) + fibonacci(n - 2);
6}
3，漢諾塔
通過前面兩個示例的分析，我們對遞歸有一個大概的了解，下面我們再來看另一個示例-漢諾塔，這個其實前面講過，有興趣的可以看下362，漢諾塔
漢諾塔的原理這里再簡單提一下，就是有3根柱子A，B，C。A柱子上由上至下依次由小至大排列的圓盤。把A柱子上的圓盤借B柱子全部移動到C柱子上，并且移動的過程始終是小的圓盤在上，大的在下。我們還是用遞歸的方式來解這道題，先來定義一個函數
public void hanoi(int n, char A, char B, char C)
他表示的是把n個圓盤從A借助B成功的移動到C。
我們先來回顧一下遞歸的條件，一個是終止條件，一個是調用自己。我們先來看下遞歸的終止條件就是當n等于1的時候，也就是A柱子上只有一個圓盤的時候，我們直接把A柱子上的圓盤移動到C柱子上即可。
1//表示的是把n個圓盤借助柱子B成功的從A移動到C
2public static void hanoi(int n, char A, char B, char C) {
3 if (n == 1) {
4 //如果只有一個，直接從A移動到C即可
5 System.out.println("從" + A + "移動到" + C);
6 return;
7 }
8 這里是遞歸調用
9}
再來看一下遞歸調用，如果n不等于1，我們要分3步，
1，先把n-1個圓盤從A借助C成功的移動到B
2，然后再把第n個圓盤從A移動到C
3，最后再把n-1個圓盤從B借助A成功的移動到C。
那代碼該怎么寫呢，我們知道函數
hanoi(n, 'A', 'B', 'C')表示的是把n個圓盤從A借助B成功的移動到C
所以hanoi(n-1, 'A', 'C', 'B')就表示的是把n-1個圓盤從A借助C成功的移動到B
hanoi(n-1, 'B', 'A', 'C')就表示的是把n-1個圓盤從B借助A成功的移動到C
所以上面3步如果用代碼就可以這樣來表示
1，hanoi(n-1, 'A', 'C', 'B')
2，System.out.println("從" + A + "移動到" + C);
3，hanoi(n-1, 'B', 'A', 'C')
所以最終完整代碼如下
1//表示的是把n個圓盤借助柱子B成功的從A移動到C
2public static void hanoi(int n, char A, char B, char C) {
3 if (n == 1) {
4 //如果只有一個，直接從A移動到C即可
5 System.out.println("從" + A + "移動到" + C);
6 return;
7 }
8 //表示先把n-1個圓盤成功從A移動到B
9 hanoi(n - 1, A, C, B);
10 //把第n個圓盤從A移動到C
11 System.out.println("從" + A + "移動到" + C);
12 //表示把n-1個圓盤再成功從B移動到C
13 hanoi(n - 1, B, A, C);
14}
通過上面的分析，是不是感覺遞歸很簡單。所以我們寫遞歸的時候完全可以套用上面的模板，先寫出終止條件，然后在寫遞歸的邏輯調用。還有一點非常重要，就是一定要明白遞歸函數中每個參數的含義，這樣在邏輯處理和函數調用的時候才能得心應手，函數的調用我們一定不要去一步步拆開去想，這樣很有可能你會奔潰的。
4，二叉樹的遍歷
再來看最后一個常見的示例就是二叉樹的遍歷，在前面也講過，如果有興趣的話可以看下373，數據結構-6,樹，我們主要來看一下二叉樹的前中后3種遍歷方式，
1，先看一下前序遍歷（根節點最開始），他的順序是
根節點→左子樹→右子樹
我們來套用模板看一下
1public void preOrder(TreeNode node) {
2 if (終止條件)// (必須要有)
3 return;
4 邏輯處理//（不是必須的）
5 遞歸調用//(必須要有)
6}
終止條件是node等于空，邏輯處理這塊直接打印當前節點的值即可，遞歸調用是先打印左子樹在打印右子樹，我們來看下
1public static void preOrder(TreeNode node) {
2 if (node == null)
3 return;
4 System.out.printf(node.val + "");
5 preOrder(node.left);
6 preOrder(node.right);
7}
中序遍歷和后續遍歷直接看下
2，中序遍歷（根節點在中間）
左子樹→根節點→右子樹
1public static void inOrder(TreeNode node) {
2 if (node == null)
3 return;
4 inOrder(node.left);
5 System.out.println(node.val);
6 inOrder(node.right);
7}
3，后序遍歷（根節點在最后）
左子樹→右子樹→根節點
1public static void postOrder(TreeNode tree) {
2 if (tree == null)
3 return;
4 postOrder(tree.left);
5 postOrder(tree.right);
6 System.out.println(tree.val);
7}
5，鏈表的逆序打印
這個就不在說了，直接看下
1public void printRevers(ListNode root) {
2 //（終止條件）
3 if (root == null)
4 return;
5 //（遞歸調用）先打印下一個
6 printRevers(root.next);
7 //（邏輯處理）把后面的都打印完了在打印當前節點
8 System.out.println(root.val);
9}
分支污染問題
通過上面的分析，我們對遞歸有了更深一層的認識。但總覺得還少了點什么，其實遞歸我們還可以通過另一種方式來認識他，就是n叉樹。在遞歸中如果只調用自己一次，我們可以把它想象為是一棵一叉樹（這是我自己想的，我們可以認為只有一個子節點的樹），如果調用自己2次，我們可以把它想象為一棵二叉樹，如果調用自己n次，我們可以把它想象為一棵n叉樹……。就像下面這樣，當到達葉子節點的時候開始往回反彈。
遞歸的時候如果處理不當可能會出現分支污染導致結果錯誤。為什么會出現這種情況，我先來解釋一下，因為除了基本類型是值傳遞以外，其他類型基本上很多都是引用傳遞。看一下上面的圖，比如我開始調用的時候傳入一個list對象，在調用第一個分支之后list中的數據修改了，那么后面的所有分支都能感知到，實際上也就是對后面的分支造成了污染。
我們先來看一個例子吧
給定一個數組nums=[2，3，5]和一個固定的值target=8。找出數組sums中所有可以使數字和為target的組合。先來畫個圖看一下
圖中紅色的表示的是選擇成功的組合，這里只畫了選擇2的分支，由于圖太大，所以選擇3和選擇5的分支沒畫。在仔細一看這不就是一棵3叉樹嗎，OK，我們來使用遞歸的方式，先來看一下函數的定義
1private void combinationSum(List<Integer> cur, int sums[], int target) {
2
3}
在把遞歸的模板拿出來
1private void combinationSum(List<Integer> cur, int sums[], int target) {
2 if (終止條件) {
3 return;
4 }
5 //邏輯處理
6
7 //因為是3叉樹，所以這里要調用3次
8 //遞歸調用
9 //遞歸調用
10 //遞歸調用
11
12 //邏輯處理
13}
這種解法靈活性不是很高，如果nums的長度是3，我們3次遞歸調用，如果nums的長度是n，那么我們就要n次調用……。所以我們可以直接寫成for循環的形式，也就是下面這樣
1private void combinationSum(List<Integer> cur, int sums[], int target) {
2 //終止條件必須要有
3 if (終止條件) {
4 return;
5 }
6 //邏輯處理(可有可無，是情況而定)
7 for (int i = 0; i < sums.length; i++) {
8 //邏輯處理(可有可無，是情況而定)
9 //遞歸調用(遞歸調用必須要有)
10 //邏輯處理(可有可無，是情況而定)
11 }
12 //邏輯處理(可有可無，是情況而定)
13}
下面我們再來一步一步看
1，終止條件是什么？
當target等于0的時候，說明我們找到了一組組合，我們就把他打印出來，所以終止條件很容易寫，代碼如下
1 if (target == 0) {
2 System.out.println(Arrays.toString(cur.toArray()));
3 return;
4 }
2，邏輯處理和遞歸調用
我們一個個往下選的時候如果要選的值比target大，我們就不要選了，如果不比target大，就把他加入到list中，表示我們選了他，如果選了他之后在遞歸調用的時候target值就要減去選擇的值，代碼如下
1 //邏輯處理
2 //如果當前值大于target我們就不要選了
3 if (target < sums[i])
4 continue;
5 //否則我們就把他加入到集合中
6 cur.add(sums[i]);
7 //遞歸調用
8 combinationSum(cur, sums, target - sums[i]);
終止條件和遞歸調用都已經寫出來了，感覺代碼是不是很簡單，我們再來把它組合起來看下完整代碼
1private void combinationSum(List<Integer> cur, int sums[], int target) {
2 //終止條件必須要有
3 if (target == 0) {
4 System.out.println(Arrays.toString(cur.toArray()));
5 return;
6 }
7 for (int i = 0; i < sums.length; i++) {
8 //邏輯處理
9 //如果當前值大于target我們就不要選了
10 if (target < sums[i])
11 continue;
12 //否則我們就把他加入到集合中
13 cur.add(sums[i]);
14 //遞歸調用
15 combinationSum(cur, sums, target - sums[i]);
16 }
我們還用上面的數據打印測試一下
1public static void main(String[] args) {
2 new Recursion().combinationSum(new ArrayList<>(), new int[]{2, 3, 5}, 8);
3}
運行結果如下
是不是很意外，我們思路并沒有出錯，結果為什么不對呢，其實這就是典型的分支污染，我們再來看一下圖
當我們選擇2的時候是一個分支，當我們選擇3的時候又是另外一個分支，這兩個分支的數據應該是互不干涉的，但實際上當我們沿著選擇2的分支走下去的時候list中會攜帶選擇2的那個分支的數據，當我們再選擇3的那個分支的時候這些數據還依然存在list中，所以對選擇3的那個分支造成了污染。有一種解決方式就是每個分支都創建一個新的list，也就是下面這樣，這樣任何一個分支的修改都不會影響到其他分支。
再來看下代碼
1private void combinationSum(List<Integer> cur, int sums[], int target) {
2 //終止條件必須要有
3 if (target == 0) {
4 System.out.println(Arrays.toString(cur.toArray()));
5 return;
6 }
7 for (int i = 0; i < sums.length; i++) {
8 //邏輯處理
9 //如果當前值大于target我們就不要選了
10 if (target < sums[i])
11 continue;
12 //由于List是引用傳遞，所以這里要重新創建一個
13 List<Integer> list = new ArrayList<>(cur);
14 //把數據加入到集合中
15 list.add(sums[i]);
16 //遞歸調用
17 combinationSum(list, sums, target - sums[i]);
18 }
19}
我們看到第13行是重新創建了一個list。再來打印一下看下結果，結果完全正確，每一組數據的和都是8
上面我們每一個分支都創建了一個新的list，所以任何分支修改都只會對當前分支有影響，不會影響到其他分支，也算是一種解決方式。但每次都重新創建數據，運行效率很差。我們知道當執行完分支1的時候，list中會攜帶分支1的數據，當執行分支2的時候，實際上我們是不需要分支1的數據的，所以有一種方式就是從分支1執行到分支2的時候要把分支1的數據給刪除，這就是大家經常提到的回溯算法，我們來看下
1private void combinationSum(List<Integer> cur, int sums[], int target) {
2 //終止條件必須要有
3 if (target == 0) {
4 System.out.println(Arrays.toString(cur.toArray()));
5 return;
6 }
7 for (int i = 0; i < sums.length; i++) {
8 //邏輯處理
9 //如果當前值大于target我們就不要選了
10 if (target < sums[i])
11 continue;
12 //把數據sums[i]加入到集合中，然后參與下一輪的遞歸
13 cur.add(sums[i]);
14 //遞歸調用
15 combinationSum(cur, sums, target - sums[i]);
16 //sums[i]這個數據你用完了吧，我要把它刪了
17 cur.remove(cur.size() - 1);
18 }
19}
我們再來看一下打印結果，完全正確
遞歸分支污染對結果的影響
分支污染一般會對結果造成致命錯誤，但也不是絕對的，我們再來看個例子。生成一個2^n長的數組，數組的值從0到(2^n)-1，比如n是3，那么要生成
[0, 0, 0][0, 0, 1][0, 1, 0][0, 1, 1][1, 0, 0][1, 0, 1][1, 1, 0][1, 1, 1]
我們先來畫個圖看一下
這不就是個二叉樹嗎，對于遞歸前面已經講的很多了，我們來直接看代碼
1private void binary(int[] array, int index) {
2 if (index == array.length) {
3 System.out.println(Arrays.toString(array));
4 } else {
5 int temp = array[index];
6 array[index] = 0;
7 binary(array, index + 1);
8 array[index] = 1;
9 binary(array, index + 1);
10 array[index] = temp;
11 }
12}
上面代碼很好理解，首先是終止條件，然后是遞歸調用，在調用之前會把array[index]的值保存下來，最后再還原。我們來測試一下
new Recursion().binary(new int[]{0, 0, 0}, 0); 看下打印結果
結果完全正確，我們再來改一下代碼
1private void binary(int[] array, int index) {
2 if (index == array.length) {
3 System.out.println(Arrays.toString(array));
4 } else {
5 array[index] = 0;
6 binary(array, index + 1);
7 array[index] = 1;
8 binary(array, index + 1);
9 }
10}
再來看一下打印結果
和上面結果一模一樣，開始的時候我們沒有把array[index]的值保存下來，最后也沒有對他進行復原，但結果絲毫不差。原因就在上面代碼第5行array[index]=0，這是因為，上一分支執行的時候即使對array[index]造成了污染，在下一分支又會對他進行重新修改。即使你把它改為任何數字也都不會影響到最終結果，比如我們在上一分支執行完了時候我們把它改為100，你在試試
1private void binary(int[] array, int index) {
2 if (index == array.length) {
3 System.out.println(Arrays.toString(array));
4 } else {
5 array[index] = 0;
6 binary(array, index + 1);
7 array[index] = 1;
8 binary(array, index + 1);
9 //注意，這里改成100了
10 array[index] = 100;
11 }
12}
我們看到第10行，把array[index]改為100了，最終打印結果也是不會變的，所以這種分支污染并不會造成最終的結果錯誤。
Java中的集合主要分為四類：1、List列表：有序的，可重復的；2、Queue隊列：有序，可重復的；3、Set集合：不可重復；4、Map映射：無序，鍵唯一，值不唯一。
感謝您能讀到這里，小編希望您對“java中遞歸的示例分析”這一關鍵問題有了從實踐層面最深刻的體會，具體使用情況還需要大家自己動手實踐使用過才能領會，如果想閱讀更多相關內容的文章，歡迎關注億速云行業資訊頻道！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
