java中遞歸的示例分析

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

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

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

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

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

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

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

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

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

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

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

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

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

public void recursion(參數(shù)0) {    if (終止條件) {        return;    }
    可能有一些邏輯運(yùn)算    recursion(參數(shù)1)    可能有一些邏輯運(yùn)算    recursion(參數(shù)2)            ……    recursion(參數(shù)n)    可能有一些邏輯運(yùn)算}

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

1，階乘

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

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

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

如果看不清，圖片可點(diǎn)擊放大。

這種遞歸還是很簡單的，我們求f(5)的時(shí)候，只需要求出f(4)即可，如果求f(4)我們要求出f(3)……，一層一層的調(diào)用，當(dāng)n=1的時(shí)候，我們直接返回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個(gè)圓盤借助柱子B成功的從A移動(dòng)到C
2public static void hanoi(int n, char A, char B, char C) {
3    if (n == 1) {
4        //如果只有一個(gè)，直接從A移動(dòng)到C即可
5        System.out.println("從" + A + "移動(dòng)到" + C);
6        return;
7    }
8    這里是遞歸調(diào)用
9}

 1//表示的是把n個(gè)圓盤借助柱子B成功的從A移動(dòng)到C
 2public static void hanoi(int n, char A, char B, char C) {
 3    if (n == 1) {
 4        //如果只有一個(gè)，直接從A移動(dòng)到C即可
 5        System.out.println("從" + A + "移動(dòng)到" + C);
 6        return;
 7    }
 8    //表示先把n-1個(gè)圓盤成功從A移動(dòng)到B
 9    hanoi(n - 1, A, C, B);
10    //把第n個(gè)圓盤從A移動(dòng)到C
11    System.out.println("從" + A + "移動(dòng)到" + C);
12    //表示把n-1個(gè)圓盤再成功從B移動(dòng)到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)用）先打印下一個(gè)
6    printRevers(root.next);
7    //（邏輯處理）把后面的都打印完了在打印當(dāng)前節(jié)點(diǎn)
8    System.out.println(root.val);
9}

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

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

我們先來看一個(gè)例子吧

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

   

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

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    //因?yàn)槭?叉樹，所以這里要調(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<Integer> cur, int sums[], int target) {
 2    //終止條件必須要有
 3    if (終止條件) {
 4        return;
 5    }
 6    //邏輯處理(可有可無，是情況而定)
 7    for (int i = 0; i < sums.length; i++) {
 8        //邏輯處理(可有可無，是情況而定)
 9        //遞歸調(diào)用(遞歸調(diào)用必須要有)
10        //邏輯處理(可有可無，是情況而定)
11    }
12    //邏輯處理(可有可無，是情況而定)
13}

下面我們再來一步一步看

1，終止條件是什么？

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

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

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

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

1        //邏輯處理
2        //如果當(dāng)前值大于target我們就不要選了
3        if (target < sums[i])
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<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        //如果當(dāng)前值大于target我們就不要選了
10        if (target < sums[i])
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}

運(yùn)行結(jié)果如下

   

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

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

再來看下代碼

 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        //如果當(dāng)前值大于target我們就不要選了
10        if (target < sums[i])
11            continue;
12        //由于List是引用傳遞，所以這里要重新創(chuàng)建一個(gè)
13        List<Integer> 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)建了一個(gè)list。再來打印一下看下結(jié)果，結(jié)果完全正確，每一組數(shù)據(jù)的和都是8

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

 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        //如果當(dāng)前值大于target我們就不要選了
10        if (target < sums[i])
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]這個(gè)數(shù)據(jù)你用完了吧，我要把它刪了
17        cur.remove(cur.size() - 1);
18    }
19}

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

分支污染一般會(huì)對結(jié)果造成致命錯(cuò)誤，但也不是絕對的，我們再來看個(gè)例子。生成一個(gè)2^n長的數(shù)組，數(shù)組的值從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}

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}

 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}