封面画师：Nengoro(ネんごろぅ)     封面ID：69526300

本文参考视频：小马哥教育(SEEMYGO) 2019年 恋上数据结构与算法（第二季）

源码仓库：mofan212/data-structure-and-algorithm (github.com)

1. 递归

1.1 基本含义

递归（Recursion）： 函数（方法）直接或间接调用自身，是一种常见的编程技巧。

直接调用自己：

1
2
3
4
int sun(int n) {
    if (n <= 1) return n;
    return n + sum(n - 1);
}

间接调用自己：

1
2
3
4
5
6
7
void a(int v) {
    if (v < 0) return;
    b(--v);
}
void b(int v) {
    a(--v);
}

1.2 递归现象

其实递归现象很常见，比如：

小时候都会讲这样一个故事，故事是：从前有座山，山里有座庙，庙里有个山再给小和尚讲故事，讲的是【从前有座山，山里有座庙，庙里有个山再给小和尚讲故事，讲的是（从前有座山，山里有座庙，庙里有个山再给小和尚讲故事，讲的是…）】

GNU 是 GNU is Not Unix 的缩写

那么：GNU – > GNU is Not Unix – > GNU is Not Unix is Not Unix – > GNU is Not Unix is Not Unix is Not Unix …

假设 A 在一个电影院，想知道自己坐在哪一排，但是前面人很多，

A 懒得数，于是问前一排的人 B 【你坐在哪一排？】，只要把 B 的答案加一，就是 A 的排数。

B 懒得数，于是问前一排的人 C 【你坐在哪一排？】，只要把 C 的答案加一，就是 B 的排数。

C 懒得数，于是问前一排的人 D 【你坐在哪一排？】，只要把 D 的答案加一，就是 C 的排数。

…

直到问到最前面的一排，最后大家都知道自己在哪一排了。

这些现象都是递归，递归和 套娃 有点相似？

1.3 函数的调用过程

1
2
3
4
5
6
7
8
9
public static void main(String[] args) {
    test1(10);
    test2(20);
}
private static void test1(int v) {}
private static void test2(int v) {
    test3(30);
}
private static void test3(int v) {}

程序一启动，就会执行 main() 函数，那函数调用过程时会发生什么呢？

一个函数一旦被调用，系统就会给这个函数分配一段连续栈空间，栈空间的本质就是内存，内存是拿来保存东西的。那这个栈空间有什么用，又是存放什么东西的呢？

一个函数可能会有参数，栈空间内就会保存参数；一个函数内部还可能存在局部变量，这些局部变量也会保存在栈空间。

一个函数内部调用另外一个函数，会将被调用的函数保存到栈空间中。当被调用的函数执行完成后，回收被调用函数的栈空间。

图示

首次执行 main() 函数，其中调用 test1()：

调用test1

执行完 test1() 后，调用 test2()，并调用 test2() 中的 test3()，test3() 、 test2() 都执行完毕后，main() 函数也执行完毕：

调用test2

对于不同的语言，函数的调用过程基本都和上面给出的图示一致。

1.4 函数的递归调用过程

1
2
3
4
5
6
7
public static void main(String[] args) {
    sum(4);
}
private static int sum(int n) {
    if (n <= 1) return n;
    return n + sum(n - 1);
}

上述 main() 函数在调用 sum(4) 时，存在递归调用，这时栈空间示意图为：

函数的递归调用

在最后调用 sum(1) 后，可以得到该函数的返回值，表示该函数执行完毕，之后回收 sum(1) 函数的栈空间；sum(1) 的栈空间被回收后，执行 sum(2) 得到一个返回值，sum(2) 执行完毕，回收 sum(2) 的栈空间；重复进行执行与回收，直到 main() 函数执行完毕，回收 main() 的栈空间。

sum(4) 程序执行图示：

sum(4)函数执行图示

如果存在函数的递归调用，那么空间复杂度就很有可能不再是 O(1)O(1)，而是需要考虑其他的空间复杂度。对上述调用来说， sum(4) 调用了 4 次 sum() 函数，参数是几就会调用几次，因此其空间复杂度为 O(n)O(n)。

sum()的空间复杂度

如果递归调用一直没有终止，就会一直消耗栈空间，最终导致栈内存溢出（Stack Overflow）。

因此 必须要有一个明确的递归结束条件， 这个递归结束的条件也被叫作边界条件、递归基。

2. 递归的使用

2.1 实例分析

求 1 + 2 + 3 + ··· + (n - 1) + n 的和 (n > 0)，那么有：

1
2
3
4
int sum(int n) {
    if (n <= 1) return n;
    return n + sum(n - 1);
}

总消耗时间 T(n)=T(n−1)+O(1)T(n) = T(n - 1) + O(1)，根据查表得：

常见的递推式与复杂度

时间复杂度为和空间复杂度都是 O(n)O(n)。

上述递归代码可以使用 for 循环进行改写：

1
2
3
4
5
6
7
int sum(int n) {
    int result = 0;
    for (int i = 1; i <= n; i++) {
        result += i;
    }
    return result;
}

改写后，时间复杂度为 O(n)O(n)，但空间复杂度是 O(1)O(1)

然而从 1 开始加到 n 是有计算公式的，因此还可以这样改写：

1
2
3
4
int sum(int n) {
    if (n <= 1) return n;
    return (1 + n) * n >> 1;
}

改写后的时间复杂度和空间复杂度都为 O(1)O(1)。

注意： 使用递归 不是为了求得最优解 ，而是为了简化解决问题的思路，使代码更简洁。

2.2 思想与使用套路

递归的基本思想

  • 拆解问题

    • 把规模大的问题拆解成规模较小的同类型问题
    • 规模较小的问题再拆解成规模更小的问题
    • 直到规模小到一定程度可以直接得出它的解

  • 求解

    • 由最小规模问题的解得出较大规模问题的解
    • 由较大规模问题的解不断得出规模更大问题的解
    • 直到得出原来问题的解

凡是可以利用上述思想来解决的问题，都可以尝试使用递归。

很多链表、二叉树相关的问题都可以使用递归来解决，因为链表、二叉树本身就是递归的结构（链表中包含链表、二叉树中包含二叉树）

递归的使用套路

① 明确函数的功能：先不去思考里面的代码怎么写，首先搞清楚这个函数是干嘛用的，能完成什么功能；

② 明确原问题与子问题的关系：寻找 f(n)f(n) 与 f(n−1)f(n - 1) 的关系；

③ 明确递归基（边界条件）：递归过程中，子问题的规模会不断缩小，当小到一定程度时可以直接得出它的解。寻找递归基，就相当于在思考“问题规模小到什么程度可以直接得出解”。

使用递归时，递归基一般就是递推函数成立的条件。比如递推函数 T(n)=T(n−1)+T(n−2)T(n) = T(n - 1) + T(n - 2) 的递归基就很有可能是 1 和 2 。

2.3 斐波那契数列

在最开始介绍数据结构时以斐波那契数列为例，并使用了递归和非递归两种方式来求得斐波那契数列的第 n 项，两者相比，使用递归不仅跟容易理解，也跟容易使用代码实现，但效率就相对低下了。

忘记了斐波那契数列？没关系，现在复习一下！ 😏

斐波那契数列： 1、1、2、3、5、8、13、21、34、…

从给出的序列可以得出规律：F(1)=1,F(2)=1,F(n)=F(n−1)+F(n−2) (n>=3)F(1) = 1, \quad F(2) = 1, \quad F(n) = F(n - 1) + F(n - 2) \ (n >= 3)

根据规律，可以得出斐波那契数列的递归实现：

1
2
3
4
int fib(int n) {
    if (n <= 2) return 1;
    return fib(n - 1) + fib(n - 2);
}

根据递推式 T(n)=T(n−1)+T(n−2)+O(1)T(n) = T(n - 1) + T(n - 2) + O(1) 可知上述代码的时间复杂度为 O(n2)O(n^2)，空间复杂度为 O(n)O(n)。

这里递归调用的空间复杂度又是 O(n)O(n)，难道所有递归调用的空间复杂度都是 O(n)O(n)？

当然不是！

那递归调用的空间复杂度应该怎么计算呢？

递归调用的空间复杂度 = 递归深度 * 每次调用所需的辅助空间

辅助空间很好理解，就是有没有调用另外的栈空间，那么递归深度应该怎么求呢？

fib 函数的调用过程

fib函数的调用过程

在上述 fib 函数的调用过程图中发现了许多重复计算，也正是因为这些重复计算，才使得递归的效率变得低下。

从调用过程还可以看出，除调用 fib(1) 或 fib(2) 以外，调用 fib(n) 时都会分别调用 fib(n - 1) 和 fib(n - 2)，一次调用会分解成两次小的调用，这也是该递归调用的时间复杂度是 O(n2)O(n^2) 的原因。

从递归调用代码可以看到，最后返回的是 fib(n - 2) + fib(n - 1)，结合调用过程图可知，会先对左侧 fib 函数进行递归调用，直到左侧的 fib 函数都执行完成后，才开始对右侧的 fib 函数进行递归调用。

递归深度就是栈空间存放元素最多时，递归调用的最长路线长度。以 fib(n) 为例，递归深度是 n ，每次调用所需的辅助空间是 O(1)O(1) 级别的，那么其空间复杂度就是 O(n)O(n)。

fib 函数递归调用过程是一种“自顶向下”的调用过程。

优化一

原递归实现方式效率低下的原因是进行了大量的重复计算，那减少重复计算就可以提升其效率。使用 数组 存储每次的计算结果，当进行重复的计算时直接从数组中获取计算过的结果。😎

1
2
3
4
5
6
7
8
9
10
11
12
13
int fib1(int n) {
    if (n <= 2) return 1;
    int[] array = new int[n + 1];
    array[1] = array[2] = 1;
    return fib1(n, array);
}

int fib1(int n, int[] array) {
    if (array[n] == 0) {
        array[n] = fib1(n - 1, array) + fib1(n - 2, array);
    }
    return array[n];
}

递归深度是 nn ，空间复杂度仍是 O(n)O(n)。

针对 fib(x) 来说，x 是任意整型数据，由于使用数组存储了 fib(x - 1) 和 fib(x - 2) 的计算结果，fib(x) 只会做一次计算。当 x == n 时，会做 n 次计算，因此时间复杂度是 O(n)O(n)。

改进后的空间复杂度没有变化，但是时间复杂度变小了，效率或者说耗时真的会减少吗？

计算一下斐波那契数列中第 44 个数字，比较优化前后的耗时：

fib优化一耗时对比

可以发现优化后几乎不需要什么时间就可以计算出结果，而优化前居然用了 2 秒才计算出结果，如果数据规模继续增大，执行优化前的代码将消耗更多的时间，甚至出现栈溢出。

优化二

在斐波那契数列中，第 i 项等于第 i - 1 项加上第 i - 2 项。因此使用循环也能求出斐波那契数列中某一位置的数。

1
2
3
4
5
6
7
8
9
int fib3(int n){
    if (n <= 2) return 1;
    int[] array = new int[n + 1];
    array[1] = array[2] = 1;
    for (int i = 3; i <= n; i++) {
        array[i] = array[i - 1] + array[i - 2];
    }
    return array[n];
}

虽然没有再使用递归，但时间复杂度和空间复杂度相比于优化一并没有发生改变，仍然是 O(n)O(n)。

这是一种“自底向上”的调用过程。

优化三

每次进行运算时，只用了 array 数组中两个位置的元素进行加法运算，基于这个原因，可以使用 滚动数组 继续优化。

滚动数组是动态规划中的一种编程思想。简单来说就是让数组滚动起来，每次都使用固定的几个存储空间，达到压缩、节省存储空间的目的。

1
2
3
4
5
6
7
8
9
int fib3(int n){
    if (n <= 2) return 1;
    int[] array = new int[2];
    array[0] = array[1] = 1;
    for (int i = 3; i <= n; i++) {
        array[i % 2] = array[(i - 1) % 2] + array[(i - 2) % 2];
    }
    return array[n % 2];
}

模运算的效率比较低下，模 2 可以转换成 与运算：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * 6 % 2 = 0 0b110 & 0b001 = 0
 * 5 % 2 = 1 0b101 & 0b001 = 1
 * 4 % 2 = 0 0b100 & 0b001 = 0
 * 3 % 2 = 1 0b011 & 0b001 = 1
 */
int fib3(int n) {
    if (n <= 2) return 1;
    int[] array = new int[2];
    array[0] = array[1] = 1;
    for (int i = 3; i <= n; i++) {
        array[i & 1] = array[(i - 1) & 1] + array[(i - 2) & 1];
    }
    return array[n & 1];
}

什么时候可以使用滚动数组呢？

对数组元素进行计算时，发现每次计算只用到了数组中连续的几个元素进行计算，这时候就可以使用滚动数组。

优化四

在优化三中只用到了数组中的两个元素，其实也没必要使用数组，直接使用两个局部变量就可以了，这样的话还可以减少空间复杂度。

1
2
3
4
5
6
7
8
9
10
int fib4(int n) {
    if (n <= 2) return 1;
    int first = 1;
    int second = 1;
    for (int i = 3; i <= n; i++) {
        second = first + second;
        first = second - first;
    }
    return second;
}

优化后，时间复杂度不会发生改变，仍然是 O(n)O(n)，但空间复杂度变成了 O(1)O(1)。

最终优化

对于斐波那契数列来说， 恰好 有个线性代数解法： 特征方程。

这个特征方程是：

斐波那契数列特征方程

根据这个特征方程，求斐波那契数列的第 n 个位置的数据的实现如下：

1
2
3
4
int fib5(int n) {
    double c = Math.sqrt(5);
    return (int) ((Math.pow((1 + c) / 2, n) - Math.pow((1 - c) / 2, n)) / c);
}

这种解法的时间复杂度和空间复杂度取决于 Math#pow() 函数，这个函数的复杂度至少可以低至 O(logn)O(logn)。

2.4 练习 —— 上楼梯

上楼梯又被叫做跳台阶，指的是： 楼梯有 n 阶台阶，上楼可以一步上 1 阶，也可以一步上 2 阶，走完 n 阶台阶共有多少种不同的走法？

假设 nn 阶台阶有 f(n)f(n) 种走法，第 1 步有 2 种走法：

  • 如果上 11 阶，那还剩 n−1n - 1 阶，共 f(n−1)f(n - 1) 种走法
  • 如果上 22 阶，那还剩 n−2n - 2 阶，共 f(n−2)f(n - 2) 种走法

可得递推公式： f(n)=f(n−1)+f(n−2)f(n) = f(n - 1) + f(n - 2)，这个递推公式和斐波那契的递推公式很像。

1
2
3
4
5
6
7
8
9
/**
 * 假设楼梯有 2 阶，可以很快地计算出上台阶的方式
 * 但如果阶数多了，就没那么容易计算了
 * 根据这个现象，可以考虑使用递归来解决
 */
int climbStairs(int n){
    if (n <= 2) return n;
    return climbStairs(n -1) + climbStairs(n - 2);
}

根据求取斐波那契数列中第 n 项的数值的代码可知，上述实现的复杂度很高，参考前文的优化，那么有：

1
2
3
4
5
6
7
8
9
10
int climbStairs(int n){
    if (n <= 2) return n;
    int first = 1;
    int second = 2;
    for (int i = 3; i <= n; i++){
        second = first + second;
        first = second - first;
    }
    return second;
}

2.5 练习 —— 汉诺塔（Hanoi）

任务需求

实现把 A 上的 n 个盘子移动到 C （盘子的编号范围是[1, n]）

要求：

  • 每次只能移动 1 个盘子
  • 大盘子只能放在小盘子下面

汉诺塔示意图

针对这种不定量的问题，可以先考虑简单的情况。

当只有一个盘子时：

汉诺塔只有一个盘子时

当有两个盘子时：

汉诺塔有两个盘子时

有三个盘子时：

汉诺塔有三个盘子时-1

汉诺塔有三个盘子时-2

实现思路

汉诺塔分成两种情况讨论即可。

当 n == 1 时，直接将盘子从 A 移动到 C 即可；

当 n > 1 时，可以拆分成 3 大步骤：

① 将 n - 1 个盘子从 A 移动到 B；

② 将编号为 n 的盘子从 A 移动到 C；

③ 将 n - 1 个盘子从 B 移动到 C；

汉诺塔第二种情况图示

很容易能发现，步骤 ① ③ 是个递归调用。

编码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * @author 默烦
 * 2020/9/3
 */
public class Hanoi {

    public static void main(String[] args) {
        new Hanoi().hanoi(3, "A", "B", "C");
    }

    /**
     * 将 n 个碟子从 p1 移动到 p3
     *
     * @param p2 中间的柱子
     */
    void hanoi(int n, String p1, String p2, String p3) {
        if (n == 1) {
            move(n, p1, p3);
            return;
        }
        hanoi(n - 1, p1, p3, p2);
        move(n, p1, p3);
        hanoi(n - 1, p2, p1, p3);
    }

    /**
     * 将 no 号盘子从 from 移动到 to
     *
     * @param no   盘子的编号
     * @param from 起始柱子
     * @param to   终点柱子
     */
    void move(int no, String from, String to) {
        System.out.println("将" + no + "号盘子从" + from + "移动到" + to);
    }
}

打印结果是：

三层汉诺塔打印结果

根据实现思路中给出的步骤图可知，打印结果和步骤图描述的步骤是一样的，侧面证明编写的代码是正确的。

那么这个递归调用方法可以被优化吗？

是不能被优化的，因为它不像前文中编写的递归调用，这个递归调用方法每一步都是必要的，也没有重复的步骤，没有可以省略的步骤，加之还有多个参数，就更不好优化了。

根据代码的实现可知递推公式是 T(n)=2×T(n−1)+O(1)T(n) = 2 \times T(n - 1) + O(1)，因此时间复杂度是 O(2n)O(2^n)，空间复杂度是 O(n)O(n)。

2.6 递归转非递归

递归调用的过程中，会将每一次调用的参数、局部变量都保存在对应的栈帧（Stack Frame）中。

现有一递归调用如下：

1
2
3
4
5
6
7
8
9
10
public static void main(String[] args) {
    log(4);
}
// 从 11 打印到 10 + n
static void log(int n){
    if (n < 1) return;
    log(n -1);
    int v = n + 10;
    System.out.println(v);
}

那么栈空间中的栈帧图示如下：

栈帧图示

若递归调用深度较大，会占用比较多的栈空间，甚至导致栈溢出。

在有些时候，递归会存在大量的重复计算，性能非常差，这个时候可以考虑将递归转换为非递归（递归 100% 可以转换成非递归，只不过有些好转，有些不好转）。

转换方法

递归转非递归的万能方法： 自己维护一个栈，来保存参数、局部变量。尽管如此，转成非递归后空间复杂度依然没有得到优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
static class Frame {
    int n;
    int v;

    public Frame(int n, int v) {
        this.n = n;
        this.v = v;
    }
}

static void log2(int n) {
    Stack<Frame> frames = new Stack<>();
    while (n > 0) {
        frames.push(new Frame(n, n + 10));
        n--;
    }
    while (!frames.isEmpty()) {
        Frame frame = frames.pop();
        System.out.println(frame.v);
    }
}

在某些时候 ，还可以重复使用一组相同的变量来保存每个栈帧的内容：

1
2
3
4
5
static void log(int n) {
    for (int i = 1; i <= n; i++) {
        System.out.println(i + 10);
    }
}

这里重复使用变量 i 保存原来栈帧中的参数，空间复杂度从 O(n)O(n) 降到了 O(1)O(1)。

3. 尾调用

3.1 基本含义

尾调用（Tail Call）：一个函数的最后一个动作是调用函数。

如果最后一个动作是调用自身，称之为尾递归（Tail Recursion），是尾调用的特殊情况。

比如：

1
2
3
4
5
6
7
8
9
10
11
12
// 尾调用
void test1() {
    int a = 10;
    int b = a + 20;
    test2(b);
}

// 尾递归
void test2(int n) {
    if (n < 10) return;
    test2(n - 1);
}

一些编译器能够对尾调用进行优化，以达到节约栈空间的目的，但 Java 编译器（或者说 Java 语言）并不能对尾调用进行优化。垃圾 Java 🤣

下述代码不是尾调用：

1
2
3
4
int factorial(int n) {
    if (n <= 1) return n;
    return n * factorial(n - 1);
}

因为它最后一个动作是乘法，并不是调用函数。

3.2 尾调用优化

尾调用优化（Tail Call Optimization）也叫作 尾调用消除（Tail Call Elimination）

如果当前栈帧上的局部变量等内容都不需要使用了，当前栈帧经过适当的改变后可以直接当作被尾调用的函数的栈帧使用，然后程序可以 jump 到被尾调用的函数代码中。

如果一个函数有尾调用，就可以对这个函数进行优化，这又是为什么呢？

一个函数有尾调用时，当前栈帧经过适当改变后可以直接被当做尾调用的函数的栈帧使用，因为最后一个动作是调用一个函数，存在于所在函数中的一些局部变量已经没啥用了，那么进行这个操作也是可以的。

生成栈帧改变代码与 jump 的过程称为尾调用优化或尾调用消除

尾调用优化让位于尾位置的函数调用跟 goto 语句性能一样高。

消除尾递归里的尾调用比消除一般的尾调用容易很多。两个不同的函数所使用的栈帧很可能不一样 ，但是递归调用的方法使用的栈帧一定是一样的。

尾递归优化

比如 Java 虚拟机（JVM）会消除尾递归里的尾调用，但不会消除一般的尾调用（因为改变不了栈帧），所以尾递归优化相对普遍， 平时的递归代码可以尽量考虑使用尾递归的形式 。

3.3 尾递归示例

阶乘

求 n 的阶乘，就是计算 1 * 2 * 3 * ··· * (n - 1) * n （n > 1）的值，可以初步得到如下代码：

1
2
3
4
int factorial(int n) {
    if (n <= 1) return n;
    return n * factorial(n - 1);
}

但是上述代码并不是尾递归，它最后一步动作是乘法，而不是调用自身。

可以对上述代码进行修改，让它变成尾递归：

1
2
3
4
5
6
7
8
static int factorial(int n) {
    return factorial(n, 1);
}

static int factorial(int n, int result) {
    if (n <= 1) return result;
    return factorial(n - 1, n * result);
}

将结果存入参数中，使用逆反思想，就可以携带结果进入每次递归中，从而使其变成尾递归。

斐波那契数列

最开始编写的求斐波那契数列指定位置的函数是：

1
2
3
4
int fib(int n) {
    if (n <= 2) return 1;
    return fib0(n - 2) + fib0(n - 1);
}

这显然也不是尾递归，可以将其改写成尾递归：

1
2
3
4
5
6
7
8
9
// 尾递归
int fib(int n) {
    return fib(n, 1, 1);
}

public int fib(int n, int first, int second) {
    if (n <= 1) return first;
    return fib(n - 1, second, first + second);
}

这也是将结果存入参数中。

如果要使用递归，尽量将其改写成尾递归的方式。