01. 递归算法知识

1. 递归简介

递归（Recursion）：指的是一种通过重复将原问题分解为同类的子问题而解决的方法。在绝大数编程语言中，可以通过在函数中再次调用函数自身的方式来实现递归。

举个简单的例子来了解一下递归算法。比如阶乘的计算方法在数学上的定义为：

$fact(n)=\{\begin{array}{ll}1& \text{n = 0}\\ n\times fact(n-1)& \text{n > 0}\end{array}$

根据阶乘计算方法的数学定义，我们可以使用调用函数自身的方式来实现阶乘函数 $fact(n)$ ，其实现代码可以写作：

def fact(n):
    if n == 0:
        return 1
    return n * fact(n - 1)

以 $n=6$ 为例，上述代码中阶乘函数 $fact(6)$ 的计算过程如下：

fact(6)
= 6 * fact(5)
= 6 * (5 * fact(4))
= 6 * (5 * (4 * fact(3)))
= 6 * (5 * (4 * (3 * fact(2))))
= 6 * (5 * (4 * (3 * (2 * fact(1)))))
= 6 * (5 * (4 * (3 * (2 * (1 * fact(0))))))
= 6 * (5 * (4 * (3 * (2 * (1 * 1)))))
= 6 * (5 * (4 * (3 * (2 * 1))))
= 6 * (5 * (4 * (3 * 2)))
= 6 * (5 * (4 * 6))
= 6 * (5 * 24)
= 6 * 120
= 720

上面的例子也可以用语言描述为：

1. 函数从 $fact(6)$ 开始，一层层地调用 $fact(5)$、$fact(4)$、…… 一直调用到最底层的 $fact(0)$。
2. 当 $n==0$ 时，$fact(0)$ 不再继续调用自身，而是直接向上一层返回结果 $1$。
3. $fact(1)$ 通过下一层 $fact(0)$ 的计算结果得出 $fact(1)=1\times 1=1$，从而向上一层返回结果 $1$。
4. $fact(2)$ 通过下一层 $fact(1)$ 的计算结果得出 $fact(2) = 2 \times 1 = 2 $，从而向上一层返回结果 $2$。
5. $fact(3)$ 通过下一层 $fact(2)$ 的计算结果得出 $fact(3) = 3 \times 2 = 6 $，从而向上一层返回结果 $6$。
6. $fact(4)$ 通过下一层 $fact(3)$ 的计算结果得出 $fact(4)=4\times 6=24$，从而向上一层返回结果 $24$。
7. $fact(5)$ 通过下一层 $fact(4)$ 的计算结果得出 $fact(5)=5\times 24=120$，从而向上一层返回结果 $120$。
8. $fact(6)$ 通过下一层 $fact(5)$ 的计算结果得出 $fact(6)=6\times 120=720$，从而返回函数的最终结果 $720$。

这就是阶乘函数的递归计算过程。

根据上面的描述，我们可以把阶乘函数的递归计算过程分为两个部分：

1. 先逐层向下调用自身，直到达到结束条件（即 $n==0$）。
2. 然后再向上逐层返回结果，直到返回原问题的解（即返回 $fact(6)==720$）。

这两个部分也可以叫做「递推过程」和「回归过程」，如下面两幅图所示：

递推过程

回归过程

如上面所说，我们可以把「递归」分为两个部分：「递推过程」和「回归过程」。

• 递推过程：指的是将原问题一层一层地分解为与原问题形式相同、规模更小的子问题，直到达到结束条件时停止，此时返回最底层子问题的解。
• 回归过程：指的是从最底层子问题的解开始，逆向逐一回归，最终达到递推开始时的原问题，返回原问题的解。

「递推过程」和「回归过程」是递归算法的精髓。从这个角度来理解递归，递归的基本思想就是： 把规模大的问题不断分解为子问题来解决。

同时，因为解决原问题和不同规模的小问题往往使用的是相同的方法，所以就产生了函数调用函数自身的情况，这也是递归的定义所在。

2. 递归和数学归纳法

递归的数学模型其实就是「数学归纳法」。这里简单复习一下数学归纳法的证明步骤：

1. 证明当 $n=b$ （$b$ 为基本情况，通常为 $0$ 或者 $1$）时，命题成立。
2. 证明当 $n>b$ 时，假设 $n=k$ 时命题成立，那么可以推导出 $n=k+1$ 时命题成立。这一步不是直接证明的，而是先假设 $n=k$ 时命题成立，利用这个条件，可以推论出 $n=k+1$ 时命题成立。

通过以上两步证明，就可以说：当 $n>=b$ 时，命题都成立。

我们可以从「数学归纳法」的角度来解释递归：

• 递归终止条件：数学归纳法第一步中的 $n=b$，可以直接得出结果。
• 递推过程：数学归纳法第二步中的假设部分（假设 $n=k$ 时命题成立），也就是假设我们当前已经知道了 $n=k$ 时的计算结果。
• 回归过程：数学归纳法第二步中的推论部分（根据 $n=k$ 推论出 $n=k+1$），也就是根据下一层的结果，计算出上一层的结果。

事实上，数学归纳法的思考过程也正是在解决某些数列问题时，可以使用递归算法的原因。比如阶乘、数组前 $n$ 项和、斐波那契数列等等。

3. 递归三步走

上面我们提到，递归的基本思想就是： 把规模大的问题不断分解为子问题来解决。 那么，在写递归的时候，我们可以按照这个思想来书写递归，具体步骤如下：

1. 写出递推公式：找到将原问题分解为子问题的规律，并且根据规律写出递推公式。
2. 明确终止条件：推敲出递归的终止条件，以及递归终止时的处理方法。
3. 将递推公式和终止条件翻译成代码：
   1. 定义递归函数（明确函数意义、传入参数、返回结果等）。
   2. 书写递归主体（提取重复的逻辑，缩小问题规模）。
   3. 明确递归终止条件（给出递归终止条件，以及递归终止时的处理方法）。

3.1 写出递推公式

写出递推公式的关键在于：找到将原问题分解为子问题的规律，并将其抽象成递推公式。

我们在思考递归的逻辑时，没有必要在大脑中将整个递推过程和回归过程一层层地想透彻。很可能还没有递推到栈底呢，脑子就已经先绕晕了。

之前讲解的阶乘例子中，一个问题只需要分解为一个子问题，我们很容易能够想清楚「递推过程」和「回归过程」的每一个步骤，所以写起来和理解起来都不难。

但是当我们面对的是一个问题需要分解为多个子问题的情况时，就没有那么容易想清楚「递推过程」和「回归过程」的每一个步骤了。

那么我们应该如何思考「递推过程」和「回归过程」呢，又该如何写出递归中的递推公式呢？

如果一个问题 $A$，可以分解为若干个规模较小、与原问题形式相同的子问题 $B$、$C$、$D$，那么这些子问题就可以用相同的解题思路来解决。我们可以假设 $B$、$C$、$D$ 已经解决了，然后只需要考虑在这个基础上去思考如何解决问题 $A$ 即可。不需要再一层层往下思考子问题与子子问题、子子问题与子子子问题之间的关系。这样理解起来就简单多了。

从问题 $A$ 到分解为子问题 $B$、$C$、$D$ 的思考过程其实就是递归的「递推过程」。而从子问题 $B$、$C$、$D$ 的解回到问题 $A$ 的解的思考过程其实就是递归的「回归过程」。想清楚了「如何划分子问题」和「如何通过子问题来解决原问题」这两个过程，也就想清楚了递归的「递推过程」和「回归过程」。

然后，我们只需要考虑原问题与子问题之间的关系，就能够在此基础上，写出递推公式了。

3.2 明确终止条件

递归的终止条件也叫做递归出口。在写出了递推公式之后，就要考虑递归的终止条件是什么。如果没有递归的终止条件，函数就会无限地递归下去，程序就会失控崩溃了。通常情况下，递归的终止条件是问题的边界值。

在找到递归的终止条件时，我们应该直接给出该条件下的处理方法。一般地，在这种情境下，问题的解决方案是直观的、容易的。例如阶乘中 $fact(0)=1$。斐波那契数列中 $f(1)=1$，$f(2)=2$。

3.3 将递推公式和终止条件翻译成代码

在写出递推公式和明确终止条件之后，我们就可以将其翻译成代码了。这一步也可以分为 $3$ 步来做：

1. 定义递归函数：明确函数意义、传入参数、返回结果等。
2. 书写递归主体：提取重复的逻辑，缩小问题规模。
3. 明确递归终止条件：给出递归终止条件，以及递归终止时的处理方法。

3.3.1 定义递归函数

在定义递归函数时，一定要明确递归函数的意义，也就是要明白这个问题传入的参数是什么，最终返回的结果是要解决的什么问题。

比如说阶乘函数 $fact(n)$，这个函数的传入参数是问题的规模 $n$，最终返回的结果是 $n$ 的阶乘值。

3.3.2 书写递归主体

在将原问题划分为子问题，并根据原问题和子问题的关系，我们就可以推论出对应的递推公式。然后根据递推公式，就可以将其转换为递归的主体代码。

3.3.3 明确递归终止条件

这一步其实就是将「3.2 明确终止条件」章节中的递归终止条件和终止条件下的处理方法转换为代码中的条件语句和对应的执行语句。

3.3.4 递归伪代码

根据上述递归书写的步骤，我们就可以写出递归算法的代码了。递归算法的伪代码如下：

def recursion(大规模问题):
    if 递归终止条件:
        递归终止时的处理方法
    
    return recursion(小规模问题)

4. 递归的注意点

4.1 避免栈溢出

在程序执行中，递归是利用堆栈来实现的。每一次递推都需要一个栈空间来保存调用记录，每当进入一次函数调用，栈空间就会加一层栈帧。每一次回归，栈空间就会减一层栈帧。由于系统中的栈空间大小不是无限的，所以，如果递归调用的次数过多，会导致栈空间溢出。

为了避免栈溢出，我们可以在代码中限制递归调用的最大深度来解决问题。当递归调用超过一定深度时（比如 100）之后，不再进行递归，而是直接返回报错。

当然这种做法并不能完全避免栈溢出，也无法完全解决问题，因为系统允许的最大递归深度跟当前剩余的占空间有关，事先无法计算。

如果使用递归算法实在无法解决问题，我们可以考虑将递归算法变为非递归算法（即递推算法）来解决栈溢出的问题。

4.2 避免重复运算

在使用递归算法时，还可能会出现重复运算的问题。

比如斐波那契数列的定义是：

$f(n)=\{\begin{array}{ll}0& n=0\\ 1& n=1\\ f(n-2)+f(n-1)& n>1\end{array}$

其对应的递归过程如下图所示：

斐波那契数列的递归过程

从图中可以看出：想要计算 $f(5)$，需要先计算 $f(3)$ 和 $f(4)$，而在计算 $f(4)$ 时还需要计算 $f(3)$，这样 $f(3)$ 就进行了多次计算。同理 $f(0)$、$f(1)$、$f(2)$ 都进行了多次计算，就导致了重复计算问题。

为了避免重复计算，我们可以使用一个缓存（哈希表、集合或数组）来保存已经求解过的 $f(k)$ 的结果，这也是动态规划算法中的做法。当递归调用用到 $f(k)$ 时，先查看一下之前是否已经计算过结果，如果已经计算过，则直接从缓存中取值返回，而不用再递推下去，这样就避免了重复计算问题。

5. 递归的应用

5.1 斐波那契数

5.1.1 题目链接

• 509. 斐波那契数 - 力扣（LeetCode）

5.1.2 题目大意

描述：给定一个整数 $n$。

要求：计算第 $n$ 个斐波那契数。

说明：

• 斐波那契数列的定义如下：
  • $f(0)=0,f(1)=1$。
  • $f(n)=f(n-1)+f(n-2)$，其中 $n>1$。

示例：

• 示例 1：

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

• 示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

5.1.3 解题思路

思路 1：递归算法

根据我们的递推三步走策略，写出对应的递归代码。

1. 写出递推公式：$f(n)=f(n-1)+f(n-2)$。
2. 明确终止条件：$f(0)=0,f(1)=1$。
3. 翻译为递归代码：
   1. 定义递归函数：fib(self, n) 表示输入参数为问题的规模 $n$，返回结果为第 $n$ 个斐波那契数。
   2. 书写递归主体：return self.fib(n - 1) + self.fib(n - 2)。
   3. 明确递归终止条件：
      1. if n == 0: return 0
      2. if n == 1: return 1

思路 1：代码

class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1:
            return 1
        return self.fib(n - 1) + self.fib(n - 2)

思路 1：复杂度分析

• 时间复杂度：$O((\frac{1+\sqrt{5}}{2}{)}^n)$。具体证明方法参考 递归求斐波那契数列的时间复杂度，不要被网上的答案误导了 - 知乎。
• 空间复杂度：$O(n)$。每次递归的空间复杂度是 $O(1)$， 调用栈的深度为 $n$，所以总的空间复杂度就是 $O(n)$。

5.2 二叉树的最大深度

5.2.1 题目链接

• 104. 二叉树的最大深度 - 力扣（LeetCode）

5.2.2 题目大意

描述：给定一个二叉树的根节点 $root$。

要求：找出该二叉树的最大深度。

说明：

• 二叉树的深度：根节点到最远叶子节点的最长路径上的节点数。
• 叶子节点：没有子节点的节点。

示例：

• 示例 1：

输入：[3,9,20,null,null,15,7]
对应二叉树
            3
           / \
          9  20
            /  \
           15   7
输出：3
解释：该二叉树的最大深度为 3

5.2.3 解题思路

思路 1： 递归算法

根据递归三步走策略，写出对应的递归代码。

1. 写出递推公式：当前二叉树的最大深度 = max(当前二叉树左子树的最大深度, 当前二叉树右子树的最大深度) + 1。
   • 即：先得到左右子树的高度，在计算当前节点的高度。
2. 明确终止条件：当前二叉树为空。
3. 翻译为递归代码：
   1. 定义递归函数：maxDepth(self, root) 表示输入参数为二叉树的根节点 $root$，返回结果为该二叉树的最大深度。
   2. 书写递归主体：return max(self.maxDepth(root.left) + self.maxDepth(root.right))。
   3. 明确递归终止条件：if not root: return 0

思路 1：代码

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

思路 1：复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是二叉树的节点数目。
• 空间复杂度：$O(n)$。递归函数需要用到栈空间，栈空间取决于递归深度，最坏情况下递归深度为 $n$，所以空间复杂度为 $O(n)$。

参考资料

• 【书籍】算法竞赛入门经典：训练指南 - 刘汝佳，陈锋 著
• 【书籍】算法训练营 陈小玉 著
• 【书籍】挑战程序设计竞赛 第 2 版 - 秋叶拓哉，岩田阳一，北川宜稔 著，巫泽俊，庄俊元，李津羽 译
• 【问答】对于递归有没有什么好的理解方法？ - 知乎 - 方应杭
• 【问答】对于递归有没有什么好的理解方法？ - 知乎 - 老刘
• 【博文】递归 & 分治 - OI Wiki
• 【博文】递归详解 - labuladong
• 【博文】递归 - 数据结构与算法之美 - 极客时间
• 【视频】清华学长带你从宏观角度看递归

来源：https://github.com/itcharge/LeetCode-Py