426，什么是遞歸，通過這篇文章，讓你徹底搞懂遞歸

tips：文章有點長，可以慢慢看，如果來不及看，也可以先收藏以后有時間在看。

聊遞歸之前先看一下什么叫遞歸。

遞歸，就是在運行的過程中調(diào)用自己。

構(gòu)成遞歸需具備的條件：

1. 子問題須與原始問題為同樣的事，且更為簡單；

2. 不能無限制地調(diào)用本身，須有個出口，化簡為非遞歸狀況處理。

我們用2個故事來闡述一下什么叫遞歸。

1，從前有座山，山里有座廟，廟里有個老和尚，正在給小和尚講故事呢！故事是什么呢？“從前有座山，山里有座廟，廟里有個老和尚，正在給小和尚講故事呢！故事是什么呢？‘從前有座山，山里有座廟，廟里有個老和尚，正在給小和尚講故事呢！故事是什么呢？……’”

2，大雄在房里，用時光電視看著從前的情況。電視畫面中的那個時候，他正在房里，用時光電視，看著從前的情況。電視畫面中的電視畫面的那個時候，他正在房里，用時光電視，看著從前的情況……

我們知道遞歸必須具備兩個條件，一個是調(diào)用自己，一個是有終止條件。這兩個條件必須同時具備，且一個都不能少。并且終止條件必須是在遞歸最開始的地方，也就是下面這樣

public void recursion(參數(shù)0) {    if (終止條件) {        return;    }    recursion(參數(shù)1);}

不能把終止條件寫在遞歸結(jié)束的位置，下面這種寫法是錯誤的

public void recursion(參數(shù)0) {    recursion(參數(shù)1);    if (終止條件) {        return;    }}

如果這樣的話，遞歸永遠(yuǎn)退不出來了，就會出現(xiàn)堆棧溢出異常(StackOverflowError)。

我對遞歸的理解是先往下一層層傳遞，當(dāng)碰到終止條件的時候會反彈，最終會反彈到調(diào)用處。下面我們就以5個最常見的示例來分析下

1，階乘

我們先來看一個最簡單的遞歸調(diào)用-階乘，代碼如下

1public?int?recursion(int?n)?{
2????if?(n?==?1)
3????????return?1;
4????return?n?*?recursion(n?-?1);
5}

這個遞歸在熟悉不過了，第2-3行是終止條件，第4行是調(diào)用自己。我們就用n等于5的時候來畫個圖看一下遞歸究竟是怎么調(diào)用的

如果看不清，圖片可點擊放大。

這種遞歸還是很簡單的，我們求f(5)的時候，只需要求出f(4)即可，如果求f(4)我們要求出f(3)……，一層一層的調(diào)用，當(dāng)n=1的時候，我們直接返回1，然后再一層一層的返回，直到返回f(5)為止。

1public?int?fibonacci(int?n)?{
2????if?(n?==?1?||?n?==?2)
3????????return?1;
4????這里是遞歸調(diào)用；
5}

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}

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????這里是遞歸調(diào)用
9}

 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}

1public?void?preOrder(TreeNode?node)?{
2????if?(終止條件)//?(必須要有)
3????????return;
4????邏輯處理//（不是必須的）
5????遞歸調(diào)用//(必須要有)
6}

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}

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}

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}

1public?void?printRevers(ListNode?root)?{
2????//（終止條件）
3????if?(root?==?null)
4????????return;
5????//（遞歸調(diào)用）先打印下一個
6????printRevers(root.next);
7????//（邏輯處理）把后面的都打印完了在打印當(dāng)前節(jié)點
8????System.out.println(root.val);
9}

通過上面的分析，我們對遞歸有了更深一層的認(rèn)識。但總覺得還少了點什么，其實遞歸我們還可以通過另一種方式來認(rèn)識他，就是n叉樹。在遞歸中如果只調(diào)用自己一次，我們可以把它想象為是一棵一叉樹（這是我自己想的，我們可以認(rèn)為只有一個子節(jié)點的樹），如果調(diào)用自己2次，我們可以把它想象為一棵二叉樹，如果調(diào)用自己n次，我們可以把它想象為一棵n叉樹……。就像下面這樣，當(dāng)?shù)竭_(dá)葉子節(jié)點的時候開始往回反彈。

遞歸的時候如果處理不當(dāng)可能會出現(xiàn)分支污染導(dǎo)致結(jié)果錯誤。為什么會出現(xiàn)這種情況，我先來解釋一下，因為除了基本類型是值傳遞以外，其他類型基本上很多都是引用傳遞?？匆幌律厦娴膱D，比如我開始調(diào)用的時候傳入一個list對象，在調(diào)用第一個分支之后list中的數(shù)據(jù)修改了，那么后面的所有分支都能感知到，實際上也就是對后面的分支造成了污染。

我們先來看一個例子吧

給定一個數(shù)組nums=[2，3，5]和一個固定的值target=8。找出數(shù)組sums中所有可以使數(shù)字和為target的組合。先來畫個圖看一下

圖中紅色的表示的是選擇成功的組合，這里只畫了選擇2的分支，由于圖太大，所以選擇3和選擇5的分支沒畫。在仔細(xì)一看這不就是一棵3叉樹嗎，OK，我們來使用遞歸的方式，先來看一下函數(shù)的定義

1private?void?combinationSum(List?cur,?int?sums[],?int?target)?{
2
3}

在把遞歸的模板拿出來

 1private?void?combinationSum(List?cur,?int?sums[],?int?target)?{
 2????if?(終止條件)?{
 3????????return;
 4????}
 5????//邏輯處理
 6
 7????//因為是3叉樹，所以這里要調(diào)用3次
 8????//遞歸調(diào)用
 9????//遞歸調(diào)用
10????//遞歸調(diào)用
11
12????//邏輯處理
13}

這種解法靈活性不是很高，如果nums的長度是3，我們3次遞歸調(diào)用，如果nums的長度是n，那么我們就要n次調(diào)用……。所以我們可以直接寫成for循環(huán)的形式，也就是下面這樣

 1private?void?combinationSum(List?cur,?int?sums[],?int?target)?{
 2????//終止條件必須要有
 3????if?(終止條件)?{
 4????????return;
 5????}
 6????//邏輯處理(可有可無，是情況而定)
 7????for?(int?i?=?0;?i? 8????????//邏輯處理(可有可無，是情況而定)
 9????????//遞歸調(diào)用(遞歸調(diào)用必須要有)
10????????//邏輯處理(可有可無，是情況而定)
11????}
12????//邏輯處理(可有可無，是情況而定)
13}

下面我們再來一步一步看

1，終止條件是什么？

當(dāng)target等于0的時候，說明我們找到了一組組合，我們就把他打印出來，所以終止條件很容易寫，代碼如下

1????if?(target?==?0)?{
2????????System.out.println(Arrays.toString(cur.toArray()));
3????????return;
4????}

2，邏輯處理和遞歸調(diào)用

我們一個個往下選的時候如果要選的值比target大，我們就不要選了，如果不比target大，就把他加入到list中，表示我們選了他，如果選了他之后在遞歸調(diào)用的時候target值就要減去選擇的值，代碼如下

1????????//邏輯處理
2????????//如果當(dāng)前值大于target我們就不要選了
3????????if?(target?4????????????continue;
5????????//否則我們就把他加入到集合中
6????????cur.add(sums[i]);
7????????//遞歸調(diào)用
8????????combinationSum(cur,?sums,?target?-?sums[i]);

終止條件和遞歸調(diào)用都已經(jīng)寫出來了，感覺代碼是不是很簡單，我們再來把它組合起來看下完整代碼

 1private?void?combinationSum(List?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? 8????????//邏輯處理
 9????????//如果當(dāng)前值大于target我們就不要選了
10????????if?(target?11????????????continue;
12????????//否則我們就把他加入到集合中
13????????cur.add(sums[i]);
14????????//遞歸調(diào)用
15????????combinationSum(cur,?sums,?target?-?sums[i]);
16????}

我們還用上面的數(shù)據(jù)打印測試一下

1public?static?void?main(String[]?args)?{
2????new?Recursion().combinationSum(new?ArrayList<>(),?new?int[]{2,?3,?5},?8);
3}

運行結(jié)果如下

是不是很意外，我們思路并沒有出錯，結(jié)果為什么不對呢，其實這就是典型的分支污染，我們再來看一下圖

當(dāng)我們選擇2的時候是一個分支，當(dāng)我們選擇3的時候又是另外一個分支，這兩個分支的數(shù)據(jù)應(yīng)該是互不干涉的，但實際上當(dāng)我們沿著選擇2的分支走下去的時候list中會攜帶選擇2的那個分支的數(shù)據(jù)，當(dāng)我們再選擇3的那個分支的時候這些數(shù)據(jù)還依然存在list中，所以對選擇3的那個分支造成了污染。有一種解決方式就是每個分支都創(chuàng)建一個新的list，也就是下面這樣，這樣任何一個分支的修改都不會影響到其他分支。

再來看下代碼

 1private?void?combinationSum(List?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? 8????????//邏輯處理
 9????????//如果當(dāng)前值大于target我們就不要選了
10????????if?(target?11????????????continue;
12????????//由于List是引用傳遞，所以這里要重新創(chuàng)建一個
13????????List?list?=?new?ArrayList<>(cur);
14????????//把數(shù)據(jù)加入到集合中
15????????list.add(sums[i]);
16????????//遞歸調(diào)用
17????????combinationSum(list,?sums,?target?-?sums[i]);
18????}
19}

我們看到第13行是重新創(chuàng)建了一個list。再來打印一下看下結(jié)果，結(jié)果完全正確，每一組數(shù)據(jù)的和都是8

上面我們每一個分支都創(chuàng)建了一個新的list，所以任何分支修改都只會對當(dāng)前分支有影響，不會影響到其他分支，也算是一種解決方式。但每次都重新創(chuàng)建數(shù)據(jù)，運行效率很差。我們知道當(dāng)執(zhí)行完分支1的時候，list中會攜帶分支1的數(shù)據(jù)，當(dāng)執(zhí)行分支2的時候，實際上我們是不需要分支1的數(shù)據(jù)的，所以有一種方式就是從分支1執(zhí)行到分支2的時候要把分支1的數(shù)據(jù)給刪除，這就是大家經(jīng)常提到的回溯算法，我們來看下

 1private?void?combinationSum(List?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? 8????????//邏輯處理
 9????????//如果當(dāng)前值大于target我們就不要選了
10????????if?(target?11????????????continue;
12????????//把數(shù)據(jù)sums[i]加入到集合中，然后參與下一輪的遞歸
13????????cur.add(sums[i]);
14????????//遞歸調(diào)用
15????????combinationSum(cur,?sums,?target?-?sums[i]);
16????????//sums[i]這個數(shù)據(jù)你用完了吧，我要把它刪了
17????????cur.remove(cur.size()?-?1);
18????}
19}

我們再來看一下打印結(jié)果，完全正確

分支污染一般會對結(jié)果造成致命錯誤，但也不是絕對的，我們再來看個例子。生成一個2^n長的數(shù)組，數(shù)組的值從0到(2^n)-1，比如n是3，那么要生成

 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}

 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}

 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}

對遞歸的理解，看完這篇文章應(yīng)該沒有什么疑問了，記住上面模板，其實代碼很好寫的，后面也會再寫一些關(guān)于遞歸的算法題的，讓你徹底搞懂遞歸。