Update 01.Recursive-Algorithm.md

itcharge · itcharge · commit d867ff702454 · 2023-02-20T23:50:22.000+08:00
diff --git a/Contents/09.Algorithm-Base/02.Recursive-Algorithm/01.Recursive-Algorithm.md b/Contents/09.Algorithm-Base/02.Recursive-Algorithm/01.Recursive-Algorithm.md
@@ -2,9 +2,9 @@
 
 > **递归（Recursion）**：指的是一种通过重复将原问题分解为同类的子问题而解决的方法。在绝大数编程语言中，可以通过在函数中再次调用函数自身的方式来实现递归。
 
-举个例子来说明一下递归算法。比如阶乘的计算方法在数学上的定义为：
+举个简单的例子来了解一下递归算法。比如阶乘的计算方法在数学上的定义为：
 
-$fact(n) =  \begin{cases} 1 & \text{if n = 0} \cr n * fact(n - 1) & \text{if n > 0} \end{cases}$
+$fact(n) =  \begin{cases} 1 & \text{n = 0} \cr n * fact(n - 1) & \text{n > 0} \end{cases}$
 
 根据阶乘计算方法的数学定义，我们可以使用调用函数自身的方式来实现阶乘函数 `fact(n)` ，其实现代码可以写作：
 
@@ -15,7 +15,7 @@ def fact(n):
     return n * fact(n - 1)
 ```
 
-以 `n = 6` 为例，上述代码中阶乘函数 `fact(6)` 的计算过程如下：
+以 `n = 6` 为例，上述代码中阶乘函数 `fact(6):` 的计算过程如下：
 
 ```Python
 fact(6)
@@ -36,7 +36,7 @@ fact(6)
 
 上面的例子也可以用语言描述为：
 
-1. 函数从 `fact(6)` 开始，一层层地调用 `fact(5)`、`fact(4)`、… 一直到最底层的 `fact(0)`。
+1. 函数从 `fact(6)` 开始，一层层地调用 `fact(5)`、`fact(4)`、…… 一直调用到最底层的 `fact(0)`。
 2. 当 `n == 0` 时，`fact(0)` 不再继续调用自身，而是直接向上一层返回结果 `1`。
 3. `fact(1)` 通过下一层 `fact(0)` 的计算结果得出 `fact(1) = 1 * 1 = 1`，从而向上一层返回结果 `1`。
 4. `fact(2)` 通过下一层 `fact(1)` 的计算结果得出 `fact(2) = 2 * 1 = 2 `，从而向上一层返回结果 `2`。
@@ -52,7 +52,7 @@ fact(6)
 1. 先逐层向下调用自身，直到达到结束条件（即 `n == 0`）。
 2. 然后再向上逐层返回结果，直到返回原问题的解（即返回 `fact(6) == 720`）。
 
-这两个部分也可以叫做「递推过程」和「归回过程」，如下面两幅图所示：
+这两个部分也可以叫做「递推过程」和「回归过程」，如下面两幅图所示：
 
 ![](https://qcdn.itcharge.cn/images/20220407160648.png)
 
@@ -71,18 +71,18 @@ fact(6)
 
 递归的数学模型其实就是「数学归纳法」。这里简单复习一下数学归纳法的证明步骤：
 
-1. 证明当 `n = b` （`b` 为基本情况，通常为 `0` 或者 `1`）时，命题成立。
-2. 证明当 `n > b` 时，假设 `n = k` 时命题成立，那么可以推导出 `n = k + 1` 时命题成立。这一步不是直接证明的，而是先假设 `n = k` 时命题成立，利用这个条件，可以推论出 `n = k + 1` 时命题成立。
+1. 证明当 $n = b$ （$b$ 为基本情况，通常为 $0$ 或者 $1$）时，命题成立。
+2. 证明当 $n > b$ 时，假设 $n = k$ 时命题成立，那么可以推导出 $n = k + 1$ 时命题成立。这一步不是直接证明的，而是先假设 $n = k$ 时命题成立，利用这个条件，可以推论出 $n = k + 1$ 时命题成立。
 
-通过以上两步证明，就可以说：当 `n >= b` 时，命题都成立。
+通过以上两步证明，就可以说：当 $n >= b$ 时，命题都成立。
 
 我们可以从「数学归纳法」的角度来解释递归：
 
-- **递归终止条件**：数学归纳法第一步中的 `n = b` ，可以直接得出结果。
-- **递推过程**：数学归纳法第二步中的假设部分（假设 `n = k` 时命题成立），也就是假设我们当前已经知道了 `n = k` 时的计算结果。
-- **回归过程**：数学归纳法第二步中的推论部分（根据 `n = k` 推论出 `n = k + 1`），也就是根据下一层的结果，计算出上一层的结果。
+- **递归终止条件**：数学归纳法第一步中的 $n = b$，可以直接得出结果。
+- **递推过程**：数学归纳法第二步中的假设部分（假设 $n = k$ 时命题成立），也就是假设我们当前已经知道了 $n = k$ 时的计算结果。
+- **回归过程**：数学归纳法第二步中的推论部分（根据 $n = k$ 推论出 $n = k + 1$），也就是根据下一层的结果，计算出上一层的结果。
 
-事实上，数学归纳法的思考过程也正是在解决某些数列问题时，可以使用递归算法的原因。比如阶乘、数组前 `n` 项和、斐波那契数列等等。
+事实上，数学归纳法的思考过程也正是在解决某些数列问题时，可以使用递归算法的原因。比如阶乘、数组前 $n$ 项和、斐波那契数列等等。
 
 ## 3. 递归三步走
 
@@ -107,9 +107,9 @@ fact(6)
 
 那么我们应该如何思考「递推过程」和「回归过程」呢，又该如何写出递归中的递推公式呢？
 
-如果一个问题 A，可以分解为若干个规模较小、与原问题形式相同的子问题 B、C、D，那么这些子问题就可以用相同的解题思路来解决。我们可以假设 B、C、D 已经解决了，然后只需要考虑在这个基础上去思考如何解决问题 A 即可。不需要再一层层往下思考子问题与子子问题、子子问题与子子子问题之间的关系。这样理解起来就简单多了。
+如果一个问题 $A$，可以分解为若干个规模较小、与原问题形式相同的子问题 $B$、$C$、$D$，那么这些子问题就可以用相同的解题思路来解决。我们可以假设 $B$、$C$、$D$ 已经解决了，然后只需要考虑在这个基础上去思考如何解决问题 $A$ 即可。不需要再一层层往下思考子问题与子子问题、子子问题与子子子问题之间的关系。这样理解起来就简单多了。
 
-从问题 A 到分解为子问题 B、C、D 的思考过程其实就是递归的「递推过程」。而从子问题 B、C、D 的解到问题 A 的解的思考过程其实就是递归的「回归过程」。想清楚了「如何划分子问题」和「如何通过子问题来解决原问题」这两个过程，也就想清楚了递归的「递推过程」和「回归过程」。
+从问题 $A$ 到分解为子问题 $B$、$C$、$D$ 的思考过程其实就是递归的「递推过程」。而从子问题 $B$、$C$、$D$ 的解回到问题 $A$ 的解的思考过程其实就是递归的「回归过程」。想清楚了「如何划分子问题」和「如何通过子问题来解决原问题」这两个过程，也就想清楚了递归的「递推过程」和「回归过程」。
 
 然后，我们只需要考虑原问题与子问题之间的关系，就能够在此基础上，写出递推公式了。
 
@@ -123,9 +123,9 @@ fact(6)
 
 在写出递推公式和明确终止条件之后，我们就可以将其翻译成代码了。这一步也可以分为 3 步来做：
 
-1. 定义递归函数：明确函数意义、传入参数、返回结果等。
-2. 书写递归主体：提取重复的逻辑，缩小问题规模。
-3. 明确递归终止条件：给出递归终止条件，以及递归终止时的处理方法。
+1. **定义递归函数**：明确函数意义、传入参数、返回结果等。
+2. **书写递归主体**：提取重复的逻辑，缩小问题规模。
+3. **明确递归终止条件**：给出递归终止条件，以及递归终止时的处理方法。
 
 #### 3.3.1 定义递归函数
 
@@ -198,15 +198,27 @@ def recursion(大规模问题):
 
 **示例**：
 
+- 示例 1：
+
 ```Python
-输入    n = 2
-输出    1
-解释    f(2) = f(1) + f(0) = 1 + 0 = 1
+输入：n = 2
+输出：1
+解释：F(2) = F(1) + F(0) = 1 + 0 = 1
+```
+
+- 示例 2：
+
+```Python
+输入：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`。
@@ -217,7 +229,7 @@ def recursion(大规模问题):
       1. `if n == 0: return 0`
       2. `if n == 1: return 1`
 
-#### 5.1.4 代码
+##### 思路 1：代码
 
 ```Python
 class Solution:
@@ -229,6 +241,11 @@ class Solution:
         return self.fib(n - 1) + self.fib(n - 2)
 ```
 
+##### 思路 1：复杂度分析
+
+- **时间复杂度**：$O((\frac{1 + \sqrt{5}}{2})^n)$。具体证明方法参考 [递归求斐波那契数列的时间复杂度，不要被网上的答案误导了 - 知乎](https://zhuanlan.zhihu.com/p/256344121)。
+- **空间复杂度**：$O(n)$。每次递归的空间复杂度是 $O(1)$， 调用栈的深度为 $n$，所以总的空间复杂度就是 $O(n)$。
+
 ### 5.2 二叉树的最大深度
 
 #### 5.2.1 题目链接
@@ -243,25 +260,29 @@ class Solution:
 
 **说明**：
 
-- 二叉树的深度：根节点到最远叶子节点的最长路径上的节点数。
-- 叶子节点：没有子节点的节点。
+- **二叉树的深度**：根节点到最远叶子节点的最长路径上的节点数。
+- **叶子节点**：没有子节点的节点。
 
 **示例**：
 
+- 示例 1：
+
 ```Python
-输入    [3,9,20,null,null,15,7]
+输入：[3,9,20,null,null,15,7]
 对应二叉树
             3
            / \
           9  20
             /  \
            15   7
-输出    3
-解释    该二叉树的最大深度为 3
+输出：3
+解释：该二叉树的最大深度为 3
 ```
 
 #### 5.2.3 解题思路
 
+##### 思路 1： 递归算法
+
 根据递归三步走策略，写出对应的递归代码。
 
 1. 写出递推公式：`当前二叉树的最大深度 = max(当前二叉树左子树的最大深度, 当前二叉树右子树的最大深度) + 1`。
@@ -272,7 +293,7 @@ class Solution:
    2. 书写递归主体：`return max(self.maxDepth(root.left) + self.maxDepth(root.right))`。
    3. 明确递归终止条件：`if not root: return 0`
 
-#### 5.2.4 代码
+##### 思路 1：代码
 
 ```Python
 class Solution:
@@ -283,6 +304,11 @@ class Solution:
         return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
 ```
 
+##### 思路 1：复杂度分析
+
+- **时间复杂度**：$O(n)$，其中 $n$ 是二叉树的节点数目。
+- **空间复杂度**：$O(n)$。递归函数需要用到栈空间，栈空间取决于递归深度，最坏情况下递归深度为 $n$，所以空间复杂度为 $O(n)$。
+
 ## 参考资料
 
 - 【书籍】算法竞赛入门经典：训练指南 - 刘汝佳，陈锋 著
