数据结构与算法之递归系列

Bug开发工程师

发布于 2019-05-29 00:25:37

7210

发布于 2019-05-29 00:25:37

文章被收录于专栏：码农沉思录码农沉思录

写在前边

几个月之前就想写这样一篇文章分享给大家，由于自己有心而力不足，没有把真正的学到的东西沉淀下来，所以一直在不断的在自学。

然后又用了一个星期的时间去整理、分类，才有了这篇 8000 字有关递归的分享，希望能够帮助正在学习递归的小伙伴们，这篇文章是缩减版，可以点击“阅读原文”查看完整版。

而且有了这篇文章的支撑和动力，往后还会写出关于数据结构与算法一些难懂的概念简单化。如果文章中有错误的地方，希望大家指正，能够为他人分享出更有质量的文章！

接下来分享的文章是关于递归的，这篇文章不单单分享递归的一切，我觉得更重要的是向每位读者传递一个思想。思想？对的，没错！这篇文章不能说包含递归的边边角角，但是通过自己的理论上的学习和实践，有了自己的一套递归思想。

什么问题该用递归，什么问题用递归简洁，什么问题就不能使用递归解决，以及对于特定的问题用递归解决的陷阱，能不能进一步对递归进行二次优化，这些都是今天小鹿分享的内容。

什么是递归

递归，顾名思义，有递有归才叫递归，有递无归，有归无递那叫 “耍流氓” 。

为什么要学习递归

我们学习一门技术也好，编程语言也好，首先学习之前我们知道它将能给我们带来什么，能帮助我们解决什么样的问题，这也是激励我们去学习它的动力所在。

从数组到链表、散列表，再到基本算法等，直到遇到递归之后，感觉非常的难理解。我相信每个人都有这种感觉，一开始觉得非常难，经历了九九八十一难之后，还是没有弄懂递归里边的猫腻，然后就自然而然的跳过了。

后来我就开始刷了一个月的 LeetCode 题，发现递归在数据结构与算法中有着一席之地，统治着江山。大部分的题都可以用递归去解决，如：二叉树的遍历、回溯算法、0-1 背包问题、深度优先遍历、回溯算法等等，我整理了至少二三十到关于递归的题，才发现递归的重要性，所以不得不重新深入递归学习，所有有了今天这篇文章。

如何理解递归

上方我对递归“耍流氓”式的定义并不能让你准确的理解递归是什么，那么我们就来活生生的举个生活中的例子。

1、问题

比如你和小鹿我一样，在大学里喜欢插队打饭（作为一个三好学生，我怎么能干这种事呢？哈哈），那么队伍后边的同学本数着自己前边还有 5 个同学就改轮到自己了，由于前边同学不断的插队，这时他发现，怎么觉得自己离着打饭的窗口越来越远呢？这时如果他想知道自己在队队列中的的第几个（前提是前边不再有人插队），用递归思想来解决，我们怎么做呢？

2、“递”

于是他问前边的同学是第几位，前边的同学也不只到呀，于是前边的同学问他前边的同学是第几位，直到前边第二个同学问到第一个正在打饭的同学是队伍的第几个（有点小尴尬）。打饭的同学不耐烦的说，没看到我是第一个正在打饭吗？这个过程其实是就是一个递归中“递”的过程。

3、“归”

然后前边打饭的第二个同学不耐烦的又告诉第三个同学，我是第二个，没看单我前边有个家伙正在打饭吗？然后第三个传给第四个，以后往后传，直到那位逐渐远离窗口的同学的前一个人告诉他是第几个之后，他知道了自己目前在队伍中的第几个位置。这个过程我们可以理解为递归中“归”的过程。

4、终止条件

“打饭的同学不耐烦的说，没看到我是第一个正在打饭吗？”，在递归中，我们称为终止条件。

5、怎么理解递归

问题虽然是层层递归的分析，但是用程序表示的时候，不要层层的在大脑中调用递归代码去想，这样可能会使你完全陷入到 “递” 的过程中去，“归” 的时候，归不出来了，这些都是我们交给计算机干的事情。

那我们在写程序的时候怎么理解递归呢？我们只找问题之间存在的关系，屏蔽掉递归的细节，具体看（五）分析。

满足递归的条件

什么样的问题才能满足用递归解决呢？具有什么样的特征，有没有判断条件？

1、一个问题能不能分解成多个子问题来解决

想知道自己在队伍中的位置，将其问题分解为“每个人所处队伍中的位置”这样的多个子问题。

2、该问题是否和子问题的解决方法相同

想要知道自己当前的位置，就要问前边人所处的位置。那么前边人想要知道自己所处的位置，就要知道他前边人的位置。所以说，该问题和子问题的解决思路相同，满足第二个条件。

3、该问题是否有终止条件

第一个正在打饭的同学说自己是队伍中的第一人，这就是所谓的终止条件，找到终止条件之后就开始进行“归”的过程。

递归的分类

通过做大量的题，根据递归解决不同的问题，引申出来的几种解决和思考的方式。之所以将其分类，是为了能够更好的理解递归在不同的问题下起着什么作用，如：每层递归之间存在的关系、计算，以及递归枚举所有情况和面临选择性问题的递归。虽然分为了几类，但是递归的本质是一成不变的。

※ 分类一：递归计算型

1、层层计算

层层计算，顾名思义，能够用递归解决的问题都可以分为多个子问题，我们把每个子问题可以抽象成一层，子问题之间的关系可以表示为层与层之间的关系。我们通过层与层之间的计算关系用递推公式表达出来做计算，经过层层的递归，最终得到结果值。

▉ 例子：

我们再那上方排队打饭的例子来说明，我们的子问题已经分析出来了，就是我想知道当前在队伍中的位置，就是去问我前边人的位置加一就是我当前队伍的位置，这为一层。而前边这个人想知道当前自己的位置，需要用同样的解决思路，作为另一层。

层与层之间的关系是什么（我当前队伍中的位置与前边人的位置存在什么样的关系）？这时你会说，当前是 +1。这个大部分人都很容易找出，既然关系确定了，然后通过递推公式很容易写出递归代码。

1// f(n) 为我所在的当前层
2// f(n-1) 为我前边的人所在的当前层
3// + 1 是层与层之间的计算关系
4f(n) = f(n-1) + 1

▉ 总结：

我将以上一类递归问题命名为「递归计算型」的「层层计算类型」。

▉ 举一反三：

求年龄的问题也是层层计算类型的问题，自己尝试分析一下（一定要自己尝试的去想，动手编码，才能进一步领悟到递归技巧）。

问题一：有 5 个人坐在一起，问第 5 个人多少岁，他说比第 4 个人大 2 岁。问第 4 个人多少岁，他说比第 3 个人大2岁。问第 3 人多少岁，他说比第 2个人大 2 岁。问第2个人多少岁，他说比第 1 个人大 2 岁。最后问第 1 个人，他说他是 10 岁。编写程序，当输入第几个人时求出其对应的年龄。

问题二：单链表从尾到头一次输出结点值，用递归实现。

2、并列计算

并列计算，顾名思义，问题的解决方式是通过递归的并列计算来得到结果的。层与层之间并没有一定的计算关系，而只是简单的改变输入的参数值。

▉ 例子：

最经典的题型就是斐波那契数列。观察这样一组数据0、 1、1、2、3、5、8、13、21、34...，去除第一个和第二个数据外，其余的数据等于前两个数据之和（如：2 = 1 + 1，8 = 3 + 5，34 = 21 + 13）。你可以尝试着根据「满足递归的三个条件」以及「怎么写出递归代码」的步骤自己动手动脑亲自分析一下。

我也在这里稍微做一个分析。

1）第一步：首先判断能不能将问题分解为多个子问题，上边我也分析过了，除了第一个和第二个数据，其他数据是前两个数据之和。那么前两个数据怎么知道呢？同样的解决方式，是他们前两个数之和。

2）第二步：找到终止条件，如果不断的找到前两个数之和，直到最前边三个数据 0、1、1 。如果递归求第一个 1 时，前边的数据不够，所以这也是我们找到的终止条件。

3）第三步：既然我们终止条件和关系找到了，递推公式也就不难写出 f(n) = f(n-1) + f(n-2)（n 为要求的第几个数字的值）。

4）转化为递归代码如下：

1function f(n) {
2    // 终止条件
3    if(n == 0) return 0;
4    if(n == 1) return 1;
5    // 递推公式
6    return f(n-1) + f(n-2);
7}

▉ 总结：

我将上方的问题总结为并列计算型。也可以归属为层层计算的一种，只不过是 + 1 改成了加一个 f 函数自身的递归（说白了，递归的结果也是一个确切的数值）。

之所谓并列计算 f(n-1) 和 f(n-2) 互不打扰，各自递归计算各的值。最后我们将其计算的结果值相加是我们最想要的结果。

▉ 举一反三：

问题：一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法。

※ 分类二：递归枚举型

递归枚举型最多的应用就是回溯算法，枚举出所有可能的情况，怎么枚举所有情况呢？通过递归编程技巧进行枚举。那什么是回溯算法？比如走迷宫，从入口走到出口，如果遇到死胡同，需要回退，退回上一个路口，然后走另一岔路口，重复上述方式，直到找到出口。

回溯算法最经典的问题又深度优先遍历、八皇后问题等，应用非常广泛，下边以八皇后问题为例子，展开分析，其他利用递归枚举型的回溯算法就很简单了。

八皇后问题

在 8 X 8 的网格中，放入八个皇后（棋子），满足的条件是，任意两个皇后（棋子）都不能处于同一行、同一列或同一斜线上，问有多少种摆放方式？

图（1）正确情况

图（2）错误情况

▉ 问题分析：

要想满足任意两个皇后（棋子）都不能处于同一行、同一列或同一斜线上，需要一一枚举皇后（棋子）的所有摆放情况，然后设定条件，筛选出满足条件的情况。

▉ 算法思路：

我们把问题分析清楚了之后，怎么通过递归实现回溯算法枚举八个皇后（棋子）出现的所有情况呢？

1）我们在 8 X 8 的网格中，先将第一枚皇后（棋子）摆放到第一行的第一列的位置（也就是坐标: (0,0)）。

2）然后我们在第二行安置第二个皇后（棋子），先放到第一列的位置，然后判断同一行、同一列、同一斜线是否存在另一个皇后？如果存在，则该位置不合适，然后放到下一列的位置，然后在判断是否满足我们设定的条件。

3）第二个皇后（棋子）找到合适的位置之后，然后在第三行放置第三枚棋子，依次将八个皇后放到合适的位置。

4）这只是一种可能，因为我设定的第一个皇后是固定位置的，在网格坐标的（0,0）位置，那么怎么枚举所有的情况呢？然后我们不断的改变第一个皇后位置，第二个皇后位置...... ，就可以枚举出所有的情况。如果你和我一样，看了这个题之后，如果还有点懵懵懂懂，那么直接分析代码吧。

▉ 代码实现：

虽然是用 javascript 实现的代码，相信学过编程的小伙伴基本的代码逻辑都可以看懂。根据上方总结的递归分析满足的三个条件以及怎么写出递归代码的步骤，一步步来分析八皇后问题。

1、将问题分解为多个子问题

在上述的代码分析和算法思路分析中，我们可以大体知道怎么分解该问题了，枚举出八个皇后（棋子）所有的满足情况可以分解为，先寻找每一种满足的情况这种子问题。比如，每个子问题的算法思路就是上方列出的四个步骤。

2、找出终止条件

当遍历到第八行的时候，递归结束。

1// 终止条件
2if(row === 8){
3    // 打印第 n 种满足的情况
4    console.log(result)
5    n++;
6    return;
7}

3、写出递推公式

isOkCulomn() 函数判断找到的该位置是否满足条件（不能处于同一行、同一列或同一斜线上）。如果满足条件，我们返回 true，进入 if 判断，row行数加一传入进行递归下一行的皇后位置。直至递归遇到终止条件位置，column ++，将第一行的皇后放到下一位置，进行继续递归，枚举出所有可能的摆放情况。

 1// 每一列的判断
 2for(let column = 0; column < 8; column++){
 3    // 判断当前的列位置是否合适
 4    if(isOkCulomn(row,column)){
 5        // 保存皇后的位置
 6        result[row] = column;
 7        // 对下一行寻找数据
 8        cal8queens(row + 1);
 9    }
10    // 此循环结束后,继续遍历下一种情况,就会形成一种枚举所有可能性
11}

 1// 判断当前列是否合适
 2const isOkCulomn = (row,column) =>{
 3    // 左上角列的位置
 4    let leftcolumn = column - 1;
 5    // 右上角列的位置
 6    let rightcolumn = column + 1;
 7
 8    for(let i = row - 1;i >= 0; i--){
 9        // 判断当前格子正上方是否有重复
10        if(result[i] === column) return false;
11
12        // 判断当前格子左上角是否有重复
13        if(leftcolumn >= 0){
14            if(result[i] === leftcolumn) return false;
15        }
16
17        // 判断当前格式右上角是否有重复
18        if(leftcolumn < 8){
19            if(result[i] === rightcolumn) return false;
20        }
21
22        // 继续遍历
23        leftcolumn --;
24        rightcolumn ++;
25    }
26    return true;
27}

4、转换为递归代码

 1// 变量
 2// result 为数组，下标为行，数组中存储的是每一行中皇后的存储的列的位置。
 3// row 行  
 4// column 列
 5// n 计数满足条件的多少种
 6var result = [];
 7let n = 0
 8const cal8queens = (row) =>{
 9    // 终止条件
10    if(row === 8){
11        console.log(result)
12        n++;
13        return;
14    }
15    // 每一列的判断
16    for(let column = 0; column < 8; column++){
17        // 判断当前的列位置是否合适
18        if(isOkCulomn(row,column)){
19            // 保存皇后的位置
20            result[row] = column;
21            // 对下一行寻找数据
22            cal8queens(row + 1);
23        }
24        // 此循环结束后,继续遍历下一种情况,就会形成一种枚举所有可能性
25    }
26}
27
28// 判断当前列是否合适
29const isOkCulomn = (row,column) =>{
30    // 设置左上角
31    let leftcolumn = column - 1;
32    let rightcolumn = column + 1;
33
34    for(let i = row - 1;i >= 0; i--){
35        // 判断当前格子正上方是否有重复
36        if(result[i] === column) return false;
37
38        // 判断当前格子左上角是否有重复
39        if(leftcolumn >= 0){
40            if(result[i] === leftcolumn) return false;
41        }
42
43        // 判断当前格式右上角是否有重复
44        if(leftcolumn < 8){
45            if(result[i] === rightcolumn) return false;
46        }
47
48        // 继续遍历
49        leftcolumn --;
50        rightcolumn ++;
51    }
52    return true;
53}
54
55// 递归打印所有情况
56const print = (result)=>{
57    for(let i = 0;i < 8; i++){
58        for(let j = 0;j < 8; j++){
59            if(result[i] === j){
60                console.log('Q' + ' ')
61            }else{
62                console.log('*' + ' ')
63            }
64        }
65    }
66}
67
68// 测试
69cal8queens(0);
70console.log(n)

▉ 总结

上述八皇后的问题就是用递归来枚举所有情况，然后再从中设置条件，只筛选满足条件的选项。上述代码建议多看几遍，亲自动手实践一下。一开始解决八皇后问题，我自己看了好长时间才明白的，以及递归如何发挥技巧作用的。

▉ 举一反三：

如果你想练练手，可以自己实现以下图的深度优先遍历，这个理解起来并不难，可以自己动手尝试着写一写，我把代码传到我的 Github 上了。

※ 分类三：递归选择型

所谓的递归选择型，每个子问题都要面临选择，求最优解的情况。有的小伙伴会说，求最优解动态规划最适合，对的，没错，但是递归通过选择型枚举所有情况，设置条件，求得问题的最优解也是可以实现的，所有我呢将其这一类问题归为递归选择型问题。

0 -1 背包问题

0 - 1 背包问题，了解过的小伙伴也是很熟悉的了。其实这个问题也属于回溯算法的一种，废话不多说，直接上问题。有一个背包，背包总的承载重量是 Wkg。现在我们有 n 个物品，每个物品的重量不等，并且不可分割。我们现在期望选择几件物品，装载到背包中。在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大？

▉ 问题分析：

如果你对该问题看懵了，没关系，我们一点点的分析。假如每个物品我们有两种状态，总的装法就有 2^n种，怎么才能不重复的穷举这些可能呢？

▉ 算法思路：

我们可以把物品依次排列，整个问题就分解为了 n 个阶段，每个阶段对应一个物品怎么选择。先对第一个物品进行处理，选择装进去或者不装进去，然后再递归地处理剩下的物品。

▉ 代码实现：

 1// 用来存储背包中承受的最大重量
 2var max = Number.MIN_VALUE;
 3// i: 对第 i 个物品做出选择
 4// currentw: 当前背包的总重量
 5// goods：数组，存储每个物品的质量
 6// n: 物品的数量
 7// weight: 背包应承受的重量
 8const f = (i, currentw, goods, n, weight) => {
 9    // 终止条件
10    if(currentw === weight || i === n){
11        if(currentw > max){
12            // 保存满足条件的最大值
13            max = currentw;
14        }
15        return ;
16    }
17
18    // 选择跳过当前物品不装入背包
19    f(i+1, currentw, goods, n, weight)
20
21    // 将当前物品装入背包
22    // 判断当前物品装入背包之前是否超过背包的重量,如果已经超过当前背包重量，就不要就继续装了
23    if(currentw + goods[i] <= weight){
24        f(i+1 ,currentw + goods[i], goods, n, weight)
25    }
26}
27
28let a = [2,2,4,6,3]
29f(0,0,a,5,10)
30console.log(max)

递归的缺点

虽然递归的使用非常的简洁，但是也有很多缺点，也是我们在使用中需要额外注意的地方和优化的地方。

1、递归堆栈溢出

▉ 理解堆栈溢出

1）递归的本质就是重复调用本身的过程，本身是什么？当然是一个函数，那好，函数中有参数以及一些局部的声明的变量，相信很多小伙伴只会用函数，而不知道函数中的变量是怎么存储的吧。没关系，等你听我分析完，你就会了。

2）函数中变量是存储到系统中的栈中的，栈数据结构的特点就是先进后出，后进先出。一个函数中的变量的使用情况就是随函数的声明周期变化的。当我们执行一个函数时，该函数的变量就会一直不断的压入栈中，当函数执行完毕销毁的时候，栈内的元素依次出栈。还是不懂，没关系，看下方示意图。

3）我们理解了上述过程之后，回到递归上来，我们的递归调用是在函数里调用自身，且当前函数并没有销毁，因为当前函数在执行自身层层递归进去了，所以递归的过程，函数中的变量一直不断的压栈，由于我们系统栈或虚拟机栈空间是非常小的，当栈压满之后，再压时，就会导致堆栈溢出。

1// 函数
2function f(n){
3    var a = 1;
4    var b = 2;
5    return a + b;
6}

▉ 解决办法

那么遇到这种情况，我们怎么解决呢？

通常我们设置递归深度，简单的理解就是，如果递归超过我们设置的深度，我们就退出，不再递归下去。还是那排队打饭的例子，如下：

 1// 表示递归深度变量
 2let depth = 0;
 3
 4function f(n){
 5    depth++；
 6    // 如果超过递归深度，抛出错误
 7    if(depth > 1000) throw 'error';
 8    // 终止条件
 9    if(n == 1) retun 1;
10    // 递推公式
11    return f(n-1) + 1;
12}

2、递归重复元素

有些递归问题中，存在重复计算问题，比如求斐波那契数列，我们画一下递归树如下图，我们会发现有很多重复递归计算的值，重复计算会导致程序的时间复杂度很高，而且是指数级别的，导致我们的程序效率低下。

▉ 解决办法

重复计算问题，我们应该怎么解决？有的小伙伴想到了，我们把已经计算过的值保存起来，每次递归计算之前先检查一下保存的数据有没有该数据，如果有，我们拿出来直接用。如果没有，我们计算出来保存起来。一般我们用散列表来保存。（所谓的散列表就是键值对的形式，如 map ）

 1// 斐波那契数列改进后
 2let map = new Map();
 3function f(n) {
 4    // 终止条件
 5    if(n == 0) return 0;
 6    if(n == 1) return 1;
 7
 8    // 如果散列表中存在当前计算的值，就直接返回，不再进行递归计算
 9    if(map.has(n)){
10        return map.get(n);
11     }
12
13    // 递推公式
14    let num = f(n-1) + f(n-2);
15    // 将当前的值保存到散列表中
16    map.set(n,num)
17    return num;
18}

3、递归高空间复杂度

因为递归时函数的变量的存储需要额外的栈空间，当递归深度很深时，需要额外的内存占空间就会很多，所以递归有非常高的空间复杂度。

最后想说的话