递归 - 简书

定义

所谓递归，就是在运行的过程中调用自己。

条件

1. 子过程需要与原始问题为同样的事，且更为简单。
2. 不能无限调用本身，需要有个出口。

模板

递归需要有两个条件，调用自己以及终止条件，且终止条件要在递归最开始的地方。而且递归过程中可能不止调用自己一次。

public void recursion(参数0) {
    if (终止条件) {
        return;
    }

    可能有一些逻辑运算
    recursion(参数1)
    可能有一些逻辑运算
    recursion(参数2)
            ……
    recursion(参数n)
    可能有一些逻辑运算
}

实例

递归的目的是把大问题细分为更小的子问题，我们只需要知道递归函数的功能，从宏观上去看，而不要去把递归一层一层拆开去想，否则会进入循环出不来。
1. 二叉树遍历
前序遍历：顺序是根节点-->左子树-->右子树
模板套用一下

public void preOrder(Node node){
    if(终止条件)
        return;
    逻辑处理//不是必须
    递归调用//必须
}

终止条件是node为空，也就是没有左右子树。逻辑处理是打印当前节点。递归调用是先打印左子树，后打印右子树。

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

2. 分支污染问题
递归问题可以看做是一个n叉树。在递归中如果只调用自己一次，我们可以把它想象为是一棵一叉树，如果调用自己2次，我们可以把它想象为一棵二叉树，如果调用自己n次，我们可以把它想象为一棵n叉树……。就像下面这样，当到达叶子节点的时候开始往回反弹。

n叉树

递归的时候如果处理不当可能会出现分支污染导致结果错误。因为除了基本类型是值传递以外，其他类型基本上很多都是引用传递。看一下上面的图，比如我开始调用的时候传入一个list对象，在调用第一个分支之后list中的数据修改了，那么后面的所有分支都能感知到，实际上也就是对后面的分支造成了污染。
例子：给定一个数组nums=[2，3，5]和一个固定的值target=8。找出数组sums中所有可以使数字和为target的组合。

选择过程

图中红色的表示的是选择成功的组合，这里只画了选择2的分支，如图相当于是一棵三叉树，于是使用递归来解决。
模板套用一下

private void combinationSum(List<Integer> cur, int sums[], int target) {
  if (终止条件) {
       return;
   }
   //逻辑处理

   //因为是3叉树，所以这里要调用3次
   //递归调用
   //递归调用
   //递归调用
   //逻辑处理
}

这种解法灵活性不是很高，如果nums的长度是3，我们3次递归调用，如果nums的长度是n，那么我们就要n次调用……。所以我们可以直接写成for循环的形式，也就是下面这样

private void combinationSum(List<Integer> cur, int sums[], int target) {
    //终止条件必须要有
    if (终止条件) {
        return;
    }
    //逻辑处理(可有可无，是情况而定)
    for (int i = 0; i < sums.length; i++) {
        //逻辑处理(可有可无，是情况而定)
        //递归调用(递归调用必须要有)
        //逻辑处理(可有可无，是情况而定)
    }
    //逻辑处理(可有可无，是情况而定)
}

下面开始填模板
1. 终止条件
当target等于0的时候，说明我们找到了一组组合，我们就把他打印出来，代码如下

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

2. 逻辑处理和递归调用
我们一个个往下选的时候如果要选的值比target大，我们就不要选了，如果不比target大，就把他加入到list中，表示我们选了他，如果选了他之后在递归调用的时候target值就要减去选择的值，代码如下

//逻辑处理
//如果当前值大于target我们就不要选了
if (target < sums[i])
   continue;
//否则我们就把他加入到集合中
cur.add(sums[i]);
//递归调用
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++) {
            //逻辑处理
            //如果当前值大于target我们就不要选了
            if (target < sums[i]) {
                continue;
            }
            //否则我们就把他加入到集合中
            cur.add(sums[i]);
            //递归调用
            combinationSum(cur, sums, target - sums[i]);
        }
    }

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

结果如下

[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]

分析思路没出错，那么是什么使得结果发生了错误，这就是分支污染问题

当我们选择2的时候是一个分支，当我们选择3的时候又是另外一个分支，这两个分支的数据应该是互不干涉的，但实际上当我们沿着选择2的分支走下去的时候list中会携带选择2的那个分支的数据，当我们再选择3的那个分支的时候这些数据还依然存在list中，所以对选择3的那个分支造成了污染。有一种解决方式就是每个分支都创建一个新的list，也就是下面这样，这样任何一个分支的修改都不会影响到其他分支。

这样代码就变成了

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++) {
        //逻辑处理
        //如果当前值大于target我们就不要选了
        if (target < sums[i]) {
            continue;
        }
        //由于List是引用传递，所以这里要重新创建一个
        List<Integer> list = new ArrayList<>(cur);
        //否则我们就把他加入到集合中
        list.add(sums[i]);
        //递归调用
        combinationSum(list, sums, target - sums[i]);
    }
}

结果是

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

上面我们每一个分支都创建了一个新的list，所以任何分支修改都只会对当前分支有影响，不会影响到其他分支，也算是一种解决方式。但每次都重新创建数据，运行效率很差。我们知道当执行完分支1的时候，list中会携带分支1的数据，当执行分支2的时候，实际上我们是不需要分支1的数据的，所以有一种方式就是从分支1执行到分支2的时候要把分支1的数据给删除，这就是大家经常提到的回溯算法

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++) {
            //逻辑处理
            //如果当前值大于target我们就不要选了
            if (target < sums[i]) {
                continue;
            }
            //把数据sums[i]加入到集合中，然后参与下一轮的递归
            cur.add(sums[i]);
            //递归调用
            combinationSum(cur, sums, target - sums[i]);
           //sums[i]这个数据你用完了吧，我要把它删了
            cur.remove(cur.size() - 1);
        }
    }

结果同样正确。