（李向东）啥叫递归？聊递归-MTV学习库

在讲递归之前，我们先来看看什么是递归。

递归就是在运行过程中调用自己。

构成递归所需的条件：

1、子问题必须与原问题相同并且更简单；

2、不能无限制地调用自身，必须有出口，可以简化为非递归的情况处理。

递归语言示例

我们用2个故事来解释什么是递归。

1.从前，有一座山，山里有一座寺庙。寺庙里有一个老和尚，他正在给小和尚讲故事！发生了什么？ “从前，有一座山，山里有一座寺庙。寺庙里有一个老和尚，他正在给小和尚讲故事！故事是什么？‘从前，有一座山，山里有一座寺庙。寺庙里有一个老和尚，他正在给小和尚讲故事。给小和尚讲故事！故事是什么？…… .’”

2.大雄在房间里，看着定时电视上过去的情况。当时电视屏幕上，他正在自己的房间里，通过时代电视观看着往日的情况。当电视画面出现在电视屏幕上的时候，他正在自己的房间里，用时代电视观看着往日的情况……

递归模板

我们知道递归必须满足两个条件，一是调用自身，二是有终止条件。这两个条件必须同时满足，一个都不能缺少。并且终止条件必须在递归的最开始处，如下

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

不能将终止条件写在递归的末尾。下面的写法是错误的。

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

如果是这样的话，递归将永远无法退出，并且会出现堆栈溢出异常()。

但实际上，递归可能会多次调用自身，而且很多递归在调用之前或之后都会有一些逻辑处理，比如下面的。

public void recursion(参数0) {
    if (终止条件) {
        return;
    }
    可能有一些逻辑运算
    recursion(参数1)
    可能有一些逻辑运算
    recursion(参数2)
            ……
    recursion(参数n)
    可能有一些逻辑运算
}

案例分析

我对递归的理解是，先一层一层的传递，遇到终止条件就会反弹，最终反弹到调用的地方。下面我们就分析一下最常见的5个例子。

1. 阶乘

我们先来看最简单的递归调用——阶乘。代码如下

public int recursion(int n) {
    if (n == 1)
        return 1;
    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。代码如下

public int fibonacci(int n) {
    if (n == 1 || n == 2)
        return 1;
    这里是递归调用；
}

递归有两个条件，一个是终止条件，我们找到了。另一个是调用自己。我们知道斐波那契数列的当前值是前两个值的和，即

(n) =(n - 1) + (n - 2)

所以代码很容易写

//1,1,2,3,5,8,13……
public int fibonacci(int n) {
    if (n == 1 || n == 2)
        return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

3. 河内塔

通过前面两个例子的分析，我们对递归有了一个大概的了解。让我们看另一个例子——河内塔。

这里简单提一下河内塔的原理，即有A、B、C三根柱子，A柱上的圆盘从上到下从小到大排列。将A柱上的所有圆盘通过B柱移动到C柱上，移动的过程总是小圆盘在上，大圆盘在下。我们还是用递归来解决这个问题，先定义一个函数

void hanoi(int n, char A, char B, char C)

他的意思是在B的帮助下成功地将n个圆盘从A移动到C。

我们先回顾一下递归的条件，一是终止条件，二是调用自身。我们首先看一下递归的终止条件。当n等于1时，即A柱上只有一个圆盘时，我们可以直接将A柱上的圆盘移动到C柱上。

//表示的是把n个圆盘借助柱子B成功的从A移动到C
public static void hanoi(int n, char A, char B, char C) {
    if (n == 1) {
        //如果只有一个，直接从A移动到C即可
        System.out.println("从" + A + "移动到" + C);
        return;
    }
    这里是递归调用
}

我们再看一下递归调用。如果n不等于1，我们必须将其分为3步。

1、首先在C的帮助下成功地将n-1个圆盘从A移动到B。

2、然后将第n个圆盘从A移动到C

3、最后，在A的帮助下，n-1个磁盘成功从B移动到C。

那么代码怎么写呢？我们知道函数

hanoi(n, 'A', 'B', 'C') 表示在 B 的帮助下，n 个磁盘成功从 A 移动到 C

所以hanoi(n-1, 'A', 'C', 'B')表示n-1个磁盘在C的帮助下成功从A移动到B。

hanoi(n-1, 'B', 'A', 'C') 表示在 A 的帮助下，n-1 个磁盘成功从 B 移动到 C。

所以如果上面3个步骤用在代码中的话，可以这样表达

1、河内(n-1, 'A', 'C', 'B')

2、.out.("从"+A+"移动到"+C);

3. 河内(n-1, 'B', 'A', 'C')

所以最终完整代码如下

//表示的是把n个圆盘借助柱子B成功的从A移动到C
public static void hanoi(int n, char A, char B, char C) {
    if (n == 1) {
        //如果只有一个，直接从A移动到C即可
        System.out.println("从" + A + "移动到" + C);
        return;
    }
    //表示先把n-1个圆盘成功从A移动到B
    hanoi(n - 1, A, C, B);
    //把第n个圆盘从A移动到C
    System.out.println("从" + A + "移动到" + C);
    //表示把n-1个圆盘再成功从B移动到C
    hanoi(n - 1, B, A, C);
}

通过上面的分析，你是不是觉得递归很简单呢？所以我们在写递归的时候，可以套用上面的模板，先写终止条件，然后再写递归逻辑调用。还有很重要的一点就是一定要了解递归函数中各个参数的含义，这样在处理逻辑、调用函数的时候才能得心应手。我们一定不要一步一步去思考函数的调用，这样你就很有可能会崩溃。

4、二叉树遍历

我们来看最后一个常见的例子：二叉树遍历。

1、我们先看前序遍历（根节点从头开始）。他的命令是

根节点→左子树→右子树

我们应用一下模板看看

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

终止条件是节点等于空。对于逻辑处理，直接打印当前节点的值即可。递归调用首先打印左子树，然后打印右子树。让我们来看看。

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

我们直接看中序遍历和后续遍历。

2.中序遍历（根节点在中间）

左子树→根节点→右子树

public static void inOrder(TreeNode node) {
    if (node == null)
        return;
    inOrder(node.left);
    System.out.println(node.val);
    inOrder(node.right);
}

3.后序遍历（根节点在最后）

左子树→右子树→根节点

public static void postOrder(TreeNode tree) {
    if (tree == null)
        return;
    postOrder(tree.left);
    postOrder(tree.right);
    System.out.println(tree.val);
}

5.链表的反向打印

这个我就不说了，大家看一下吧

public void printRevers(ListNode root) {
    //（终止条件）
    if (root == null)
        return;
    //（递归调用）先打印下一个
    printRevers(root.next);
    //（逻辑处理）把后面的都打印完了在打印当前节点
    System.out.println(root.val);
}

支行污染问题

通过上面的分析，我们对递归有了更深入的了解。但我总觉得少了点什么。其实我们可以用另一种方式来理解递归，那就是n叉树。在递归中，如果我们只调用自己一次，我们可以将其视为一棵单向树（这是我自己的想法，我们可以将其视为一棵只有一个子节点的树）。如果我们两次调用自己，我们可以将其视为一棵单向树。将其想象为一棵二叉树。如果你调用自己n次，我们可以把它想象成一棵n叉树……就像下面这样，当它到达叶子节点时就开始反弹。

如果递归过程中处理不当，可能会出现分支污染，导致结果不正确。我解释一下为什么会出现这种情况，因为除了基本类型是按值传递之外，很多其他类型基本上都是按引用传递。看看上面的图片。例如，当我开始调用时，我传入一个列表对象。调用第一个分支后，列表中的数据被修改。然后所有后续分支都可以感知到它。事实上，这意味着后续分支受到影响。造成了污染。

我们先看一个例子

给定一个数组 nums=[2, 3, 5]，固定值 = 8，找出数组 sums 中所有使数字之和等于的组合。我们先画个图看看

图中红色的代表组合成功。这里只画了选择2的分支。由于图片太大，所以没有画出选项3和选项5的分支。仔细一看，这不是一棵三叉树吗？好吧，让我们使用递归。我们先看一下函数的定义。

private void combinationSum(List<Integer> cur, int sums[], int target) {
}

取出递归模板

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. 终止条件是什么？

当它等于0时，表示我们找到了一组组合，我们会将它们打印出来，所以终止条件很容易写。代码如下

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

2.逻辑处理和递归调用

当我们一项一项选择的时候，如果我们要选择的值比该值大的话，我们就不会选择。如果它不大于，我们会将其添加到列表中以表明我们已选择它。如果我们选择它然后递归调用它必须从选择的值中减去该值。代码如下

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

终止条件和递归调用都已经写好了。代码是不是很简单？我们再拼凑一下，看看完整的代码。

private 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) {
    new Recursion().combinationSum(new ArrayList<>(), new int[]{2, 3, 5}, 8);
}

运行结果如下

是不是很奇怪呢？我们的想法并没有错。为什么结果是错误的？其实，这就是典型的分支污染。我们再看一下图片。

当我们选择2时，它是一个分支，当我们选择3时，它是另一个分支。这两个分支的数据不应该互相干扰，但实际上，当我们走选择2的分支时，列表中会携带选择2的分支的数据。当我们选择3的分支时，数据仍然会存在于列表中，因此会污染选择3的分支。一种解决方案是为每个分支创建一个新列表，如下所示，这样对任何分支的修改都不会影响其他分支。

我们再看一下代码

private void combinationSum(List 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 list = new ArrayList<>(cur);
        //把数据加入到集合中
        list.add(sums[i]);
        //递归调用
        combinationSum(list, sums, target - sums[i]);
    }
}

我们看到第 13 行重新创建了一个列表。让我们再次打印并查看结果。结果是完全正确的。每组数据之和为8。

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

private 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);
    }
}

我们再看一下打印的结果。这是完全正确的。

递归分支污染对结果的影响

分支污染一般会导致结果出现致命错误，但也不是绝对的。我们来看一个例子。生成一个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]

我们先画一张图来看一下。

这不就是一棵二叉树吗？我已经谈论了很多关于递归的内容。我们直接看代码吧。

private void binary(int[] array, int index) {
    if (index == array.length) {
        System.out.println(Arrays.toString(array));
    } else {
        int temp = array[index];
        array[index] = 0;
        binary(array, index + 1);
        array[index] = 1;
        binary(array, index + 1);
        array[index] = temp;
    }
}

上面的代码很容易理解。首先是终止条件，然后是递归调用。 array[index]的值会在调用前保存，最后恢复。我们来测试一下

new Recursion().binary(new int[]{0, 0, 0}, 0);

查看打印结果

结果完全正确，我们再改一下代码

private void binary(int[] array, int index) {
    if (index == array.length) {
        System.out.println(Arrays.toString(array));
    } else {
        array[index] = 0;
        binary(array, index + 1);
        array[index] = 1;
        binary(array, index + 1);
    }
}

我们再看一下打印结果

结果和上面完全一样。我们一开始并没有保存array[index]的值，最后也没有恢复它，但结果一点也不差。原因是上面代码第5行的array[index]=0。这是因为即使在执行上一个分支时 array[index] 被污染，在下一个分支中它也会被再次修改。即使你将其更改为任意数字，也不会影响最终结果。例如，当我们执行完上一个分支后，我们将其更改为100。您尝试一下吗？

private void binary(int[] array, int index) {
    if (index == array.length) {
        System.out.println(Arrays.toString(array));
    } else {
        array[index] = 0;
        binary(array, index + 1);
        array[index] = 1;
        binary(array, index + 1);
        //注意，这里改成100了
        array[index] = 100;
    }
}

我们看到第10行，array[index]改为100，最终打印的结果不会改变，所以这个分支污染不会导致最终结果出现错误。

给这篇文章的作者打赏

相关文章

整理12款国内外主流任务管理软件，含团队、个人、免费、开源

模仿微信呼叫的示例项目，快速实现呼叫邀请通话场景

win7浏览器禁用引擎导致网页显示不正常的解决方法