定義

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

條件

1. 子過程需要與原始問題為同樣的事晦款，且更為簡單炎功。
2. 不能無限調(diào)用本身，需要有個(gè)出口缓溅。

模板

遞歸需要有兩個(gè)條件蛇损，調(diào)用自己以及終止條件，且終止條件要在遞歸最開始的地方坛怪。而且遞歸過程中可能不止調(diào)用自己一次淤齐。

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

    可能有一些邏輯運(yùn)算
    recursion(參數(shù)1)
    可能有一些邏輯運(yùn)算
    recursion(參數(shù)2)
            ……
    recursion(參數(shù)n)
    可能有一些邏輯運(yùn)算
}

實(shí)例

遞歸的目的是把大問題細(xì)分為更小的子問題，我們只需要知道遞歸函數(shù)的功能袜匿，從宏觀上去看床玻，而不要去把遞歸一層一層拆開去想，否則會(huì)進(jìn)入循環(huán)出不來沉帮。
1. 二叉樹遍歷
前序遍歷：順序是根節(jié)點(diǎn)-->左子樹-->右子樹
模板套用一下

public void preOrder(Node node){
    if(終止條件)
        return;
    邏輯處理//不是必須
    遞歸調(diào)用//必須
}

終止條件是node為空锈死，也就是沒有左右子樹。邏輯處理是打印當(dāng)前節(jié)點(diǎn)穆壕。遞歸調(diào)用是先打印左子樹待牵，后打印右子樹。

public static void preOrder(TreeNode node) {
    if (node == null)
        return;
    System.out.printf(node.val + "");
    preOrder(node.left);
    preOrder(node.right);
}

2. 分支污染問題
遞歸問題可以看做是一個(gè)n叉樹喇勋。在遞歸中如果只調(diào)用自己一次缨该，我們可以把它想象為是一棵一叉樹，如果調(diào)用自己2次川背，我們可以把它想象為一棵二叉樹贰拿，如果調(diào)用自己n次，我們可以把它想象為一棵n叉樹……熄云。就像下面這樣膨更，當(dāng)?shù)竭_(dá)葉子節(jié)點(diǎn)的時(shí)候開始往回反彈。

n叉樹

選擇過程

private void combinationSum(List<Integer> cur, int sums[], int target) {
  if (終止條件) {
       return;
   }
   //邏輯處理

   //因?yàn)槭?叉樹溯壶，所以這里要調(diào)用3次
   //遞歸調(diào)用
   //遞歸調(diào)用
   //遞歸調(diào)用
   //邏輯處理
}

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

private void combinationSum(List<Integer> cur, int sums[], int target) {
    //終止條件必須要有
    if (終止條件) {
        return;
    }
    //邏輯處理(可有可無，是情況而定)
    for (int i = 0; i < sums.length; i++) {
        //邏輯處理(可有可無若治，是情況而定)
        //遞歸調(diào)用(遞歸調(diào)用必須要有)
        //邏輯處理(可有可無慨蓝，是情況而定)
    }
    //邏輯處理(可有可無，是情況而定)
}

下面開始填模板
1. 終止條件
當(dāng)target等于0的時(shí)候端幼，說明我們找到了一組組合礼烈，我們就把他打印出來，代碼如下

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

2. 邏輯處理和遞歸調(diào)用
我們一個(gè)個(gè)往下選的時(shí)候如果要選的值比target大婆跑，我們就不要選了此熬，如果不比target大，就把他加入到list中滑进，表示我們選了他犀忱，如果選了他之后在遞歸調(diào)用的時(shí)候target值就要減去選擇的值，代碼如下

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

所以完整代碼如下扶关，用上述的例子測試一下

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class CombinationSum {
    private static void combinationSum(List<Integer> cur, int sums[], int target) {
        //終止條件必須要有
        if (target == 0) {
            System.out.println(Arrays.toString(cur.toArray()));
            return;
        }
        for (int i = 0; i < sums.length; i++) {
            //邏輯處理
            //如果當(dāng)前值大于target我們就不要選了
            if (target < sums[i]) {
                continue;
            }
            //否則我們就把他加入到集合中
            cur.add(sums[i]);
            //遞歸調(diào)用
            combinationSum(cur, sums, target - sums[i]);
        }
    }

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

結(jié)果如下

[2, 2, 2, 2]
[2, 2, 2, 2, 3, 3, 2, 3]
[2, 2, 2, 2, 3, 3, 2, 3, 5, 3, 2, 2, 3]
[2, 2, 2, 2, 3, 3, 2, 3, 5, 3, 2, 2, 3, 3, 2]
[2, 2, 2, 2, 3, 3, 2, 3, 5, 3, 2, 2, 3, 3, 2, 5]
[2, 2, 2, 2, 3, 3, 2, 3, 5, 3, 2, 2, 3, 3, 2, 5, 5, 2, 3]

分析思路沒出錯(cuò)阴汇，那么是什么使得結(jié)果發(fā)生了錯(cuò)誤，這就是分支污染問題

private static void combinationSum(List<Integer> cur, int sums[], int target) {
    //終止條件必須要有
    if (target == 0) {
        System.out.println(Arrays.toString(cur.toArray()));
        return;
    }
    for (int i = 0; i < sums.length; i++) {
        //邏輯處理
        //如果當(dāng)前值大于target我們就不要選了
        if (target < sums[i]) {
            continue;
        }
        //由于List是引用傳遞币绩，所以這里要重新創(chuàng)建一個(gè)
        List<Integer> list = new ArrayList<>(cur);
        //否則我們就把他加入到集合中
        list.add(sums[i]);
        //遞歸調(diào)用
        combinationSum(list, sums, target - sums[i]);
    }
}

結(jié)果是

[2, 2, 2, 2]
[2, 3, 3]
[3, 2, 3]
[3, 3, 2]
[3, 5]
[5, 3]

上面我們每一個(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)常提到的回溯算法

private static void combinationSum(List<Integer> cur, int sums[], int target) {
        //終止條件必須要有
        if (target == 0) {
            System.out.println(Arrays.toString(cur.toArray()));
            return;
        }
        for (int i = 0; i < sums.length; i++) {
            //邏輯處理
            //如果當(dāng)前值大于target我們就不要選了
            if (target < sums[i]) {
                continue;
            }
            //把數(shù)據(jù)sums[i]加入到集合中抄伍，然后參與下一輪的遞歸
            cur.add(sums[i]);
            //遞歸調(diào)用
            combinationSum(cur, sums, target - sums[i]);
           //sums[i]這個(gè)數(shù)據(jù)你用完了吧艘刚，我要把它刪了
            cur.remove(cur.size() - 1);
        }
    }

結(jié)果同樣正確。