# 递归 ## 从求阶乘开始假如现在让你求 $5!$。 > 阶乘的数学定义如下： > $$ > n! =n × (n - 1) × (n - 2) × ... × 2 × 1 > $$ > 特别地，$0!=1$ 你应该会这么去算： $$ 5! = 5 × 4 × 3 × 2 × 1 = 120 $$ 这应该不难，而且也非常符合我们的直觉。但其实，我们还可以换一种思路，**不直接计算 $5!$**。你可能会想：**不直接算，那还能怎么算？** 我先把原来的式子重新写一下： $$ 5! = 5 × (4 × 3 × 2 × 1) $$ 而括号里的这一部分，不就是 $4!$ 吗？于是： $$ 5! = 5 × 4! $$ 这看起来只是一次简单的数学变形，但实际上，我们刚刚做了一件很重要的事情：**没有直接计算 $5!$，而是把它转化成了一个更小的同类问题——计算 $4!$。** 那么 $4!$ 怎么处理呢？同样： $$ 4! = 4 × 3! $$ 按照同样的方法继续拆分问题，直到遇到可以直接得到答案的情况：$0! = 1$ 此时，最底层的子问题已经有了答案，我们就可以从这里开始，一层一层地把答案算回来。现在从 $0!$ 开始往回计算： $$ \begin{aligned} 0! &= 1 \\ 1! &= 1 \times 0! = 1 \\ 2! &= 2 \times 1! = 2 \\ 3! &= 3 \times 2! = 6 \\ &\ \vdots \\ 5! &= 5 \times 4! = 120 \end{aligned} $$ 回头看整个过程，会发现它和我们平时的计算方式很不一样。平时计算 $5!$，我们会直接把 $5、4、3、2、1$ 依次乘起来。而刚才，我们没有直接解决 $5!$，而是不断把它转化成一个更小的同类问题： $5! \rightarrow 4! \rightarrow 3! \rightarrow 2! \rightarrow 1! \rightarrow 0!$ 到达最底层之后，再从这里开始，利用已经得到的结果逐层计算回来。也就是说，我们在不断重复同一个过程：**把一个问题转化成更小的同类问题，直到遇到可以直接解决的情况；然后再从最小的问题开始，逐层得到原问题的答案。** 这种解决问题的方式，就是我们所说的**递归（recursion）**。刚才我们通过观察 $5!$ 的计算过程，得到了：$5! = 5\times4!$ 同样的规律也适用于 $n>0$ 的情况：$n! = n\times(n-1)!$ 再结合：$0! = 1$，于是，我们便可以得到阶乘的递归定义： $$ n! = \begin{cases} 1, & n=0\\ n\times(n-1)!, & n>0 \end{cases} $$ 那么，如果把这个数学定义翻译成代码，会是什么样子？例如： ```java int factorial(int n) { if (n == 0) { return 1; } return n * factorial(n - 1); } ``` 你会发现，`factorial` 方法内部竟然又调用了 `factorial` 方法！在程序中，我们常常通过**方法调用自身**来实现递归。这种调用过程被称为**递归调用**。和我们的直观思路的实现方式比较一下： ```java int factorial(int n) { int result = 1; for (int i = n; i >= 1; i--) { result *= i; } return result; } ``` 你会发现，对于阶乘这个例子来说，递归解决问题的方式不是比直接计算更复杂吗？目前来说是这样的。然而，并不是所有问题都像求阶乘这样容易直接解决。**有些问题换成递归的思路，反而会更加简单。** 后面我们会看到一些更适合用递归解决的问题。 ## 递归方法设计的一般步骤之前实现的 `factorial` 方法虽然简单，却已经包含了递归程序设计的基本结构。一般来说，设计一个递归方法时，可以按照下面四个步骤来思考： 1. 递归方法定义 2. 处理基础情况 3. 递归调用 4. 计算当前层的结果 ### 递归方法定义首先，我们要明确这个方法究竟要解决什么问题。对于递归方法来说，更重要的是进一步想清楚：**原问题是什么？子问题又是什么？它们能不能用同一个方法来描述？** 这往往是递归程序设计中**最难也是最关键**的一步。以之前的 `factorial` 方法为例，原问题是求 $n!$，而根据递归关系，子问题是求 $(n-1)!$。因此，我们可以让方法接收一个 `int` 类型的参数 `n`，表示要求哪个数的阶乘，并返回对应的阶乘结果。这样，原问题和子问题就可以用同一个方法来表示：`factorial(n)`、`factorial(n - 1)`。 ### 处理基础情况递归调用会让问题不断变小，**但问题不可能无限缩小下去**。我们必须明确一个可以直接解决的最小问题，并在递归方法中优先处理这种情况。这个最小问题，就是**基础情况（base case）**。以 `factorial` 为例，每次递归调用都会让 `n` 减少 1。根据阶乘的定义，当 `n` 为 0 时，`0! = 1`，因此我们可以直接返回 1，而不需要继续进行递归调用。 ### 递归调用确定了子问题之后，就需要调用递归方法来解决它。以 `factorial` 为例，当前问题是求 $n!$，子问题是求 $(n-1)!$。因此，可以调用 `factorial(n - 1)` 来求解这个子问题。 ### 计算当前层的结果递归调用得到子问题的答案之后，我们要利用这个答案，结合当前层的信息，得到当前问题的答案。对于 `factorial` 来说，当前问题是 `factorial(n)`，子问题是 `factorial(n - 1)`。我们已经通过递归调用得到了子问题的结果，接下来只需要在这个结果的基础上乘以 `n`，就可以得到当前问题的结果。 ## 如何治疗晕递归我们已经学习了设计递归方法的一般流程，然而当我们真正去理解递归调用的执行过程时，往往还是会感到头晕目眩，甚至忍不住感叹：**递归怎么这么难以理解？** 为什么会这样呢？这是因为**递归方法会不断调用自己。每一次调用，做的又都是类似的事情。** 比如之前的 `factorial` 方法，当你试图把每一层调用都想清楚时，就很容易陷进去： `factorial(5)` 调用了 `factorial(4)`，那 `factorial(4)` 又做了什么？它调用了 `factorial(3)`，那 `factorial(3)` 又做了什么？…… 实际上，递归求阶乘的案例还算比较容易理解。然而面对更为复杂的递归问题时，**如果仍然试图把每一层递归调用都展开、都想清楚，递归就很容易把人绕晕**。可是，**如果我们不深入展开递归调用的执行过程，又怎么知道这个递归调用是正确的呢？** 这种困惑其实很自然。我们之前在验证一个方法的逻辑是否正确时，通常都会深入分析它的执行过程，把每一行代码都追下去。**但递归程序的正确性，并不需要我们采用这种方式去验证。** **对于递归方法来说，请暂时相信递归调用能够正确解决子问题**。我们不去深究子问题是怎么解决的，而是直接利用它返回的结果，继续思考当前层的问题应该如何解决。这就是理解递归本质时非常重要的一种思维方式——**递归的"信任跳跃"**。但新的问题随之而来：**我凭什么相信递归调用能够正确解决子问题？** 要回答这一问题，我们需要了解递归与我们在高中数学课堂上学过的**数学归纳法**之间的相似之处。回顾一下高中课本中定义的数学归纳法： > 一般地，证明一个与正整数 $n$ 有关的命题，可按下列步骤进行： > > 1. 归纳奠基：证明当 $n = n_0 \ (n_0 ∈ N⁺)$ > 2. 归纳步骤：以 “当 $n = k \ (k ∈ N⁺，k ≥ n_0,)$ 时命题成立” 为条件，推出 “当 $n = k + 1$ 时命题也成立”。 > > 只要完成这两个步骤，就可以断定命题对从 $n_0$ 开始的所有正整数 $n$ 都成立，这种证明方法称为**数学归纳法**。 > > > > 记 $P(n)$是一个关于正整数 $n$ 的命题，我们可以吧数学归纳法证明的形式改写如下： > > 条件：（1）$P(n_0)$ 为真；（2）若 $P(k)$ 为真，则 $P(k + 1)$ 也为真。 > > 结论：$P(n)$ 为真。 > > 在数学归纳法的两步中： > > 第一步验证了当 $n = n_0$ 是结论成立，即命题 $P(n_0)$ 为真。 > > 第二步是**证明一种递推关系**，实际上是要证明一个新命题：若 $P(k)$ 为真，则 $P(k + 1)$ 也为真。 > > 只要将这两步交替使用，就有如下关系成立： > $$ > P(n_0)⇒P(n_0 + 1)⇒P(n_0 + 2)⇒⋯ > $$ > > 从而完成证明。 > 这里附一张高中课本中的经典例题截图给你参考，我并不想深入讲解它： ![image.png](https://pic.code-nav.cn/post_picture/1644143521826918401/9jEuDHaMCElYERrS.webp) 仔细观察数学归纳法的这些步骤，我们会发现，它和递归方法的设计过程存在着非常相似的结构。归纳奠基就类似于递归方法中的基础情况处理。在数学归纳法中，我们需要验证原命题在基础情况下是否成立；**而在递归方法中，我们需要直接给出基础情况下的正确答案。** 以 `factorial` 开头的条件判断为例： ```java if (n == 0) { return 1; } ``` 由定义可知 $0! = 1$，所以这个基础情况可以直接验证是正确的。**只要基础情况本身没有问题，递归就有了一个可靠的起点。** 归纳步骤则类似于递归方法中利用子问题结果解决当前问题的过程。在数学归纳法中，我们假设 $P(n-1)$ 成立，然后利用这个假设证明 $P(n)$ 也成立；这里的关键在于 “假设”。类似地，在递归方法中，我们同样**假设递归调用已经正确解决了子问题**，然后利用子问题的结果解决当前问题。以 `factorial` 的这行代码为例： ```java return n * factorial(n - 1); ``` 我们假设递归调用`factorial(n - 1)` 已经正确解决了子问题。那么，我们就不需要继续追踪它内部的执行过程，只需要使用它返回的结果 $(n-1)!$ 。在此基础上，再乘以 `n`，便可以得到当前问题 `factorial(n)` 的结果。实际上，**只要子问题划分合理，并且每一层都能正确利用子问题的结果计算当前问题，递归就能得到正确的结果**。 > 如何划分子问题，是递归方法定义阶段首先需要思考的问题。之前我之所以说这是递归程序设计中**最难也是最关键**的一步，是因为子问题一旦确定，后续的一切工作，实际上都是围绕它展开的。 > 综上所述，现在我们终于可以回答最开始的问题了：**“递归的信任跳跃”为什么是合理的？** 因为在设计递归方法时，我们已经明确了原问题和子问题之间的关系。**数学归纳法中的归纳假设，为“暂时相信子问题已经正确解决”提供了一种很好的思维依据。** 因此，我们不必继续追踪递归调用的内部执行过程，而只需要关注当前层如何利用子问题的结果得到当前问题的答案。所以，在设计和理解递归方法时，请不要深陷递归调用的怪圈，而是把注意力集中在三个问题上： - 原问题和子问题分别是什么？它们之间的关系是否合理？ - 基础情况是否正确？ - 假设子问题已经正确解决，当前层应该如何利用它的结果？这就是递归“信任跳跃”的底气。 ## 一些经典的递归问题到这里，我们已经理解了递归中的两个核心思维： - **将原问题转化为更小的同类子问题；** - **暂时相信递归调用能够正确解决子问题，并在此基础上解决当前问题。** 接下来，我们通过几个经典的递归问题，进一步理解和运用这两种思维。 ### 斐波那契数列斐波那契（Fibonacci）数列是指这样一个数列：1，1，2，3，5，8，13，21，34，55，89…… 它的特点是：从第3项开始，每一项都等于前两项之和。我们可以用如下递推公式来描述这个数列： \[ \begin{cases} F_1=1\\ F_2=1\\ F_n=F_{n-1}+F_{n-2},& n\ge 3 \end{cases} \] 请你实现一个程序，用于求解斐波那契数列中第 `n` 项的值。题目保证结果不超过 `Integer.MAX_VALUE`。我们先不使用递归，而是用最直观的循环迭代来解决这个问题。参考代码如下： ```java public int fibonacci(int n) { if (n == 1 || n == 2) { return 1; } int a = 1, b = 1; for (int i = 3; i <= n; i++) { int c = a + b; a = b; b = c; } return b; } ``` 现在，我们用递归的思维来思考。首先，原问题是求解斐波那契数列的第 `n` 项。这道题的递推公式非常直观，它直接告诉了我们应该如何划分子问题。因此，原问题可以拆分为两个子问题：要得到第 `n` 项，需要先得到第 `n - 1` 项和第 `n - 2` 项，然后将二者相加。因此，我们可以定义 `int fibonacci(int n);` 方法。这样，原问题和两个子问题都可以用同一个方法表示，即 `fibonacci(n)`、`fibonacci(n - 1)` 和 `fibonacci(n - 2)`。接下来确定基础情况。当 `n` 为 1 或 2 时，斐波那契数列的结果都是 1，因此可以直接返回 1。按照这个思路，本题的递归方法可以写成： ```java public int fibonacci(int n) { if (n == 1 || n == 2) { return 1; } return fibonacci(n - 1) + fibonacci(n - 2); } ``` 可以看到，这个递归版本的代码非常简洁。**但代码简单，并不意味着它的执行过程也同样简单。** 这个版本存在大量重复计算，运行效率并不高。我们将在后面的“递归方法的时间复杂度分析”中详细讨论这一问题。 ### 递归版归并排序 **归并排序（Merge Sort）** 由 **约翰·冯·诺依曼（John von Neumann）** 于1945年提出，是一种典型的分治算法。归并排序的基本思路是： 1. 如果待排序区间只有一个元素，那么它天然有序，无需排序。 2. 将待排序区间一分为二。 3. **分别对这两个子区间进行归并排序。** 4. 将两个已经有序的子区间合并成一个有序区间。归并排序中最核心的一点，就是**如何划分子问题**。它运用了“分而治之”的算法思想。然而这个思想我们目前还没有系统学习过，如果感兴趣，可以在理解递归之后再进一步学习。如果之前没有接触过归并排序，那么仅仅让你根据“排序”这个问题自己去寻找子问题，可能并不容易。这也是为什么这里我直接给出了归并排序的基本思路。找不到归并排序的子问题对于现在的我们并不重要。重要的是，经过前面几个递归问题的学习，你有没有发现：**原来自己已经能够读懂一个已经设计好的递归思路了。** 好的，现在我们回过头来。我相信你应该注意到了这句话：**分别对这两个子区间进行归并排序。** 这句话意味着，**原来的排序问题被划分成了两个更小的排序问题，而且这两个子问题仍然可以用归并排序来解决**。现在，我们按照前面学习的递归方法设计流程，重新分析归并排序。首先是递归方法定义。根据前面的分析，我们的递归方法除了需要传入待排序数组，还需要确定当前待排序的区间。这里我采用左闭右开区间 `[l, r)` 来表示待排序范围。归并排序完成后不需要返回一个新的结果，因此方法不需要返回值。综上所述，我们可以将方法定义为 `mergeSort(int[] arr, int l, int r)`，表示对整数数组 `arr` 中 `[l, r)` 范围内的元素进行归并排序。原问题是对整个数组进行排序，而子问题是分别对左半部分和右半部分进行排序。它们虽然待排序的区间不同，但本质上都是“对一个区间进行归并排序”，因此都可以用 `mergeSort(int[] arr, int l, int r)` 来表示。接着是处理基础情况。当区间内的元素数量小于等于 1 时，区间本身就是有序的，无需继续排序。在我们选取的左闭右开区间 `[l, r)` 中，`r - l` 就是区间内的元素数量。因此，当 `r - l <= 1` 时，我们直接结束当前方法。然后是递归调用。在进行递归调用之前，我们首先需要将区间 `[l, r)` 一分为二。我们先求区间中点：`int mid = (r + l) / 2;` 然后将区间分成 `[l, mid)` 和 `[mid, r)` 两部分。随后分别对这两个子区间进行递归调用： ```java mergeSort(arr, l, mid); mergeSort(arr, mid, r); ``` 递归调用完成后，`[l, mid)` 和 `[mid, r)` 这两个子区间中的元素都已经分别有序。接下来，我们将这两个有序子区间合并，使 `[l, r)` 中的所有元素整体有序。按照这个思路，我们不难写出归并排序的代码： ```java public void mergeSort(int[] arr, int l, int r) { // 为了简单考虑，这里不考虑 l, r 输入不合法的情况 if (r - l <= 1) { return; } // 避免 r + l 的整数溢出 int mid = (r - l) / 2 + l; mergeSort(arr, l, mid); mergeSort(arr, mid, r); // 在同一数组中合并两个有序子数组，需要借助临时数组 int[] temp = new int[r - l]; // i、j 分别指向左右两个有序子数组，k 指向临时数组 // 合并结果先暂存在 temp 中，最后再覆盖 [l, r) 范围 int i = l, j = mid, k = 0; while (i < mid && j < r) { if (arr[i] < arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } if (i < mid) { // 左半边区间有剩余 while (i < mid) { temp[k++] = arr[i++]; } } else { // 右半边区间有剩余 while (j < r) { temp[k++] = arr[j++]; } } System.arraycopy(temp, 0, arr, l, r - l); } ``` 就这样，我们就不经意间写出了递归版归并排序的代码。我之所以强调“递归版”，显然是因为归并排序还存在非递归的实现。 **1948 年，Goldstine 与冯·诺依曼在相关报告中详细描述并分析了自底向上的归并排序。** 感兴趣的读者可以自行了解。非递归版可以避免递归调用带来的额外开销，但实现通常更加复杂；对于现在的我们来说，递归版显然更加直观。我们再回到这里的递归调用。现在你应该能体会到前面所说的“递归信任跳跃”有多重要了。对于 `mergeSort(arr, l, mid)` 和 `mergeSort(arr, mid, r)`，我们没有必要继续深入追踪它们内部是如何执行的，只需要相信它们能够正确地将对应的子区间排好序，然后直接利用这两个有序子区间完成合并。**这样一来，我们只需要关注当前层要做什么，就可以顺利写出这个递归方法。** 如果这时候非要“头铁”地深入追踪每一次递归调用的执行细节，那么归并排序的复杂程度，可就远远超过前面的递归求阶乘了。 ### 快速排序 **快速排序（Quick Sort）** 由 **托尼·霍尔（Tony Hoare）** 于1960年提出，同样也是一种典型的分治算法。它和归并排序一样，都是将一个排序问题转化成更小的排序问题，但划分子问题的方式有所不同。快速排序的基本思路是： 1. 从区间中选择一个元素作为基准值（`pivot`）。 2. 通过一次分区操作，将基准值移动到一个合适的位置，使得它左侧的元素都不大于它，右侧的元素都不小于它。此时，基准值已经处于排序后的最终位置。 3. **分别对基准值左侧和右侧的两个子区间进行快速排序。** 和归并排序类似，我们一开始其实也无法自己划分出快速排序的子问题。但是通读完它的基本思路后，我们就能够发现：**原来的排序问题被划分成了两个更小的排序问题，而这两个子问题仍然用快速排序来解决。** 而且，快速排序划分子问题的方式确实很有意思：**它先通过一次分区操作确定一个元素的最终位置，再将剩下的问题交给两个更小的子问题。** 现在，我们按照前面学习的递归方法设计流程，重新分析快速排序。快速排序的方法参数仍然是待排序数组和待排序区间，因此方法签名与归并排序类似，这里我直接给你：`quickSort(int[] arr, int l, int r)`。紧接着就是快速排序中最难也是最关键的一步——分区操作。只有分区结束后，我们才能划分子问题。假设 `pivot` 最后被移动到了下标 `k`，那么数组中除 `pivot` 外，剩下的无序部分就变成了 `[l, k)` 和 `[k + 1, r)` 两个子区间。接下来，我们只需要分别对这两个子区间继续使用快速排序即可。首先，我们要在待排序区间 `[l, r)` 中选出一个 `pivot`。快速排序并没有严格规定 `pivot` 必须选择哪一个元素，因此可以采用不同的选择策略。这里我们采用一种比较常见的策略：随机选择 `pivot`。因此，我们需要使用 JDK 内置的随机数库，在 `[l, r)` 范围内随机生成一个下标。假设随机到的下标为`k`，接下来又该如何分区呢？快速排序的分区操作有多种实现方式，这里我采用其中一种，具体思路参考了这个视频：[【排序算法精华3】快速排序 (上）](https://www.bilibili.com/video/BV1rV411j7f6/?share_source=copy_web&vd_source=5380fa0514d9710134c69943bf7dc51c)。首先，我们先将 `pivot` 元素和最后一个元素交换位置。这样，`pivot` 就被暂时移出了搜索区间，接下来只需要在 `[l, r - 1)` 中进行探索。此时，我们的搜索区间就变为`[l, r - 1)`。视频中的思路运用了双指针技巧，定义两个“指针”，一开始都指向 `l` 处： ```java int i = l, j = l; ``` 这是为了把区间 `[l, r - 1)` 划分成 3 部分： - `[l, i)` 区间内的元素都不大于 `pivot`； - `[i, j)` 区间内的元素都不小于 `pivot`； - `[j, r - 1)` 区间表示尚未探索的区域。结合图来看会更容易理解： ![image.png](https://pic.code-nav.cn/post_picture/1644143521826918401/NohsMBB0KfsCHWWC.webp) `j` 在从左往右探索的过程中： - 若`arr[j] < pivot`，则交换下标 `i` 和 `j` 处的两个元素，然后将 `i` 向右移动一位。这样，`arr[j]` 就被放入了 `[l, i)` 区间。 - 否则，不做任何操作。随着 `j` 向右移动，这个元素就会留在 `[i, j)` 区间中。当 `j` 探索完整个 `[l, r - 1)` 区间后，下标 `i` 处的元素就是第一个不小于 `pivot` 的元素。此时，交换 `i` 和 `r - 1` 处的两个元素，就可以将 `pivot` 放到最终位置。最后，分别对 `[l, i)` 和 `[i + 1, r)` 这两段区间继续进行快速排序。这样，整个区间 `[l, r)` 就排好序了。按照这个思路，我们不难写出快速排序的代码： ```java public class Solution { private static final Random random = new Random(); public void quickSort(int[] arr, int l, int r) { if (r - l <= 1) { return; } // 在 [l, r) 内随机一个下标 k，arr[k] 作为 pivot 。 // random.nextInt(n) 生成一个 [0, n) 之间的一个随机整数 // 所以 random.nextInt(r - l) 得到的是 [0, r - l) // 在此基础上加上 l，将范围平移为 [l, r) int k = random.nextInt(r - l) + l; swap(arr, r - 1, k); int pivot = arr[r - 1]; int i = l, j = l; while (j < r - 1) { if (arr[j] < pivot) { swap(arr, i, j); i++; } j++; } swap(arr, i, r - 1); quickSort(arr, l, i); quickSort(arr, i + 1, r); } /** * 交换 arr[i] 和 arr[j] */ private void swap(int[] arr, int i, int j) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } } ``` 就这样，我们又写出了一个递归版的经典算法——快速排序。回过头来看，快速排序和归并排序虽然都采用了分治的思想，但它们处理当前问题的方式却很不一样。归并排序先划分子问题，再分别解决，最后合并结果；快速排序则先通过分区操作确定 `pivot` 的最终位置，再将剩下的两个子区间交给递归调用。而在这个过程中，我们又一次用到了“递归信任跳跃”：不需要追踪递归调用的内部执行过程，只需要相信它能够正确解决对应的子问题，然后专注于当前层需要完成的工作。到了这里，我们已经可以开始把这种思维迁移到其他问题上：**找到合适的子问题，解决当前层的问题，然后把剩下的工作交给递归。** ### 汉诺塔问题 **汉诺塔（Tower of Hanoi）** 问题是法国数学家 **爱德华·卢卡斯（Édouard Lucas）** 于 1883 年提出的一个经典数学谜题，也是递归中的经典问题。为了给这个谜题增添神秘色彩，他还设计了一个著名的传说故事：传说，在印度贝拿勒斯的梵天寺里，有一块黄铜板，上面竖立着三根金刚石柱。创世时，梵天将 64 片纯金盘按照从大到小的顺序，从下到上套在其中一根柱子上。僧侣们需要将这 64 片金盘全部移动到另一根柱子上，并且必须遵守两条规则： 1. **一次只能移动一片金盘。** 2. **大盘不能压在小盘上面。** 传说还有一个古老的预言：当僧侣们完成这项任务时，世界将在轰鸣中毁灭。 > 为什么会这样？我们最后揭晓。 ![image.png](https://pic.code-nav.cn/post_picture/1644143521826918401/Pxh6JCp2351BOHuq.webp) 我们先去掉故事中的神话色彩，专注于这个问题本身：有 3 根柱子，我们分别称它们为 A、B、C。有 `n` 个大小不同的圆盘，它们按照从大到小的顺序叠放在 A 柱子上。现在，我们需要将这些圆盘全部移动到 C 柱子上，同时遵循两条游戏规则： 1. 一次只能移动一个圆盘。 2. 大圆盘不能放在小圆盘上面。刚开始看到这个问题时，我们可能很难直接看出递归在哪里。**所以这一次，我们先不急着找递归，而是从最简单的情况开始，一步一步自己摸索。** 首先，我们从最简单的情况开始：只有一个圆盘时，该怎么做？ ![image.png](https://pic.code-nav.cn/post_picture/1644143521826918401/ax9cfs8vZrBmWELX.webp) 显然，只有一个圆盘时，我们直接将其从 A 移动到 C 就好了。然后稍微增加一点难度：如果有两个圆盘，该怎么做？ ![image.png](https://pic.code-nav.cn/post_picture/1644143521826918401/zAqo9N5vjFQtZQGo.webp) 这其实也难不到你。我们知道，最终需要先将最底下的大圆盘移动到 C 上。但在这之前，必须先把上面的那个小圆盘移走，否则大圆盘根本没有办法移动。我们先把最上面的圆盘移动到 B 上，给大圆盘腾出空间；然后将大圆盘从 A 移动到 C；最后，再把小圆盘从 B 移动到 C。这样，两个圆盘就都移动到 C 上了。现在难度再上一个台阶：如果有三个圆盘，该怎么做？ ![image.png](https://pic.code-nav.cn/post_picture/1644143521826918401/vbVyTQVsVM5oPnH5.webp) 这次看起来复杂了一些。我们还是先想办法把最下面最大的圆盘移动到 C。但和刚才一样，在移动它之前，必须先把上面的两个圆盘移走。那这两个圆盘应该移动到哪里？显然，我们可以先把它们移动到 B 上。 **至于这两个圆盘具体怎么移动，其实我们刚刚已经解决过了：不就是刚才的“移动两个圆盘问题”吗？只不过这一次，我们需要**借助柱子 C，将这两个圆盘从 A 移动到 B。为便于后续叙述，这里我给盘子从上到下依次编号 1、2、3。首先，我们要将 1 从 A 移动到 C，这样就给 2 腾出了空间。然后将 2 从 A 移动到 B。最后将 1 从 C 移动到 B。 ![image.png](https://pic.code-nav.cn/post_picture/1644143521826918401/HGvF4tsMCEK9EmDA.webp) 这样，3 就可以顺利从 A 移动到 C 了。接下来，就是将 B 上的两个圆盘移动到 C。**不知你有没有发现，我们又遇到了刚才已经解决过的问题。** 这时候，递归的影子就开始出现了。这个问题的步骤我就不继续展开了，相信你也能够自己想明白。现在说递归还为时尚早。我们继续加大难度：如果有四个圆盘，该怎么做？ ![image.png](https://pic.code-nav.cn/post_picture/1644143521826918401/ZLgD1QPX7flwARs5.webp) 这一次，我们还是要先把最下面最大的圆盘移动到 C。在移动它之前，必须先把上面的 3 个圆盘移走。而移动 3 个圆盘的问题，我们刚刚已经解决过了。只不过这次，我们需要**借助 C 柱，将这三个圆盘从 A 移动到 B。** ![image.png](https://pic.code-nav.cn/post_picture/1644143521826918401/0XLm7SKb3p25gOAw.webp) 这样就可以把最大的圆盘顺利移动到 C 上。然后，再**借助 A，将 B 上的 3 个圆盘移动到 C 上**，整个问题就解决了。请仔细回头看一下，我们刚才到底做了什么？为了移动 4 个圆盘，我们先解决了一个“移动 3 个圆盘”的问题；移动完最大的圆盘后，又解决了一次“移动 3 个圆盘”的问题。而移动 3 个圆盘，本身又可以拆成两个“移动 2 个圆盘”的问题。这样继续往下拆，最终都会落到最简单的“移动 1 个圆盘”上。所以，无论有多少个圆盘，解决汉诺塔问题的思路其实都是一样的。我们把这个过程总结一下：假设现在有 `n` 个圆盘，我们需要将它们从 A 移动到 C，那么整个过程就可以分成三步： 1. 借助 C，将前 `n - 1` 个圆盘从 A 移动到 B。 2. 将最大的第 `n` 个圆盘直接从 A 移动到 C。 3. 借助 A，将 B 上的 `n - 1` 个圆盘移动到 C。不过，仔细观察刚才的三步，你会发现，第 1 步和第 3 步其实是在重复做同一件事情。它们都是将 `n - 1` 个圆盘从一根柱子移动到另一根柱子，只不过起点、终点和辅助柱子发生了变化。既然柱子的位置会发生变化，我们就不能把 A、B、C 写死，而应该**描述它们各自的角色**。一根柱子是圆盘开始时所在的位置，我们称它为**起始柱**；一根柱子是圆盘最终要去的位置，我们称它为**目标柱**；剩下的一根，就是帮助我们完成移动的**辅助柱**。有了这三个角色之后，我们再回头看看刚才的问题。如果让一个方法来完成“移动若干个圆盘”这件事情，它需要知道两个方面的信息： 1. 现在有多少个圆盘需要移动？ 2. 这些圆盘要从哪里移动到哪里，中间借助哪根柱子？因此，这个方法需要 4 个参数： - `n`：需要移动的圆盘数量 - `from`：起始柱 - `aux`：辅助柱 - `to`：目标柱而且我们只是移动圆盘，并不需要返回值，因此这个方法的声明可以写成： ```java void hanoi(int n, char from, char aux, char to); ``` 有了这个方法，无论是刚才的第 1 步，还是第 3 步，我们都可以用同一个方法来描述。接着是处理基础情况。当 `n == 1` 时，我们就不需要再继续拆分了，直接将这个圆盘从 `from` 移动到 `to` 即可。这里，我们只需要输出一句移动信息。然后是递归调用。第一次递归调用，是借助 `to`，将 `from` 上的 `n - 1` 个圆盘移动到 `aux`，即`hanoi(n - 1, from, to, aux)`。接着，将 `from` 上最大的那个圆盘移动到 `to`。最后，再借助 `from`，将 `aux` 上的 `n - 1` 个圆盘移动到 `to`，即`hanoi(n - 1, aux, from, to)`。这样，两个规模为 `n - 1` 的子问题都解决了，中间最大的那个圆盘也已经移动到目标柱，原问题自然也就解决了。按照这个思路，我们不难写出汉诺塔的代码： ```java public void hanoi(int n, char from, char aux, char to) { if (n == 1) { System.out.printf("将圆盘从 %c 移动到 %c", from, to); return; } hanoi(n - 1, from, to, aux); System.out.printf("将圆盘从 %c 移动到 %c", from, to); hanoi(n - 1, aux, from, to); } ``` 就这样，汉诺塔这个看起来非常复杂的问题，也被我们用一个很简单的递归方法解决了。这里的关键，依然是我们前面反复强调的“递归信任跳跃”。我们不需要知道 `hanoi(...)` 内部究竟做了什么，**只需要相信它能够正确完成自己的任务，然后专注于当前这一层需要完成的步骤**。还记得前面我说过： > 然而，并不是所有问题都像求阶乘这样容易直接解决。**有些问题换成递归的思路，反而会更加简单。** 汉诺塔就是一个很好的例子。面对这样的问题，你很难直接规划出所有的移动步骤。如果你“头铁”，非要一步一步地把所有移动过程都规划出来，反而很容易陷入繁琐的细节。而换成递归的思路，只需要不断把问题拆成规模更小的相同问题，整个过程就变得清晰起来。当然，对于汉诺塔问题来说，我们要发现这个递归思路本身也费了不少功夫。最终，我们只用了几行代码，就实现了 `hanoi` 的核心逻辑。当你真正掌握了这种思考方式，递归代码中那些一层套一层的调用，就不再需要逐层追踪。站在当前这一层，相信递归能够完成它该完成的事情，剩下的，就交给递归自己。**拨开层层递归调用的迷雾，你真正需要看清的，其实只有眼前这一层。** 还记得文章开头的那个传说吗？ > 当僧侣们完成这 64 个圆盘的移动时，世界将在轰鸣中毁灭。数学家们其实已经推导出了以下结论（当然，你自己去推也费不了多大功夫，就是找规律问题）：对于 $n$ 个圆盘，汉诺塔最少需要移动 $2^n - 1$ 次。那么 64 个圆盘呢？我们代入计算一下： $$ 2^{64}-1 = 18,446,744,073,709,551,615 $$ 如果每秒移动一次，需要的时间将超过 **5800 亿年**！！ 5800 多亿年是什么概念？宇宙至今也不过约 **138 亿年**，地球的年龄更只有约 **45 亿年**。即使从宇宙诞生的那一刻开始，每秒移动一个圆盘，直到今天，这场汉诺塔游戏都还远远没有结束。所以，开头那个“世界毁灭”的传说，离我们实在太遥远了。 **与其为那些遥不可及的事情杞人忧天，不如把时间还给自己，留给眼前真正重要的人和事。毕竟，属于我们的时间可没有 5800 多亿年。珍惜当下，也许才是这个古老谜题留给我们最有意思的启示。** ## 递归方法的时间复杂度分析（学习中）

MBTI小程序 启动 dev:weapp 命令，webpack报错修复

报错信息

修改位置

目录

目录

MBTI小程序启动 dev:weapp 命令，webpack报错修复