递归

从求阶乘开始

假如现在让你求 $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 方法虽然简单，却已经包含了递归程序设计的基本结构。

一般来说，设计一个递归方法时，可以按照下面四个步骤来思考：

递归方法定义
处理基础情况
递归调用
计算当前层的结果

递归方法定义

首先，我们要明确这个方法究竟要解决什么问题。

对于递归方法来说，更重要的是进一步想清楚：原问题是什么？子问题又是什么？它们能不能用同一个方法来描述？

这往往是递归程序设计中最难也是最关键的一步。

以之前的 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$ 有关的命题，可按下列步骤进行：

归纳奠基：证明当 $n = n_0 \ (n_0 ∈ N⁺)$

归纳步骤：以 “当 $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)⇒⋯ $$

从而完成证明。

这里附一张高中课本中的经典例题截图给你参考，我并不想深入讲解它：

仔细观察数学归纳法的这些步骤，我们会发现，它和递归方法的设计过程存在着非常相似的结构。

归纳奠基就类似于递归方法中的基础情况处理。在数学归纳法中，我们需要验证原命题在基础情况下是否成立；而在递归方法中，我们需要直接给出基础情况下的正确答案。

以 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年提出，是一种典型的分治算法。

归并排序的基本思路是：

如果待排序区间只有一个元素，那么它天然有序，无需排序。
将待排序区间一分为二。
分别对这两个子区间进行归并排序。
将两个已经有序的子区间合并成一个有序区间。

归并排序中最核心的一点，就是如何划分子问题。它运用了“分而治之”的算法思想。然而这个思想我们目前还没有系统学习过，如果感兴趣，可以在理解递归之后再进一步学习。

如果之前没有接触过归并排序，那么仅仅让你根据“排序”这个问题自己去寻找子问题，可能并不容易。这也是为什么这里我直接给出了归并排序的基本思路。

找不到归并排序的子问题对于现在的我们并不重要。重要的是，经过前面几个递归问题的学习，你有没有发现：原来自己已经能够读懂一个已经设计好的递归思路了。

好的，现在我们回过头来。我相信你应该注意到了这句话：分别对这两个子区间进行归并排序。

这句话意味着，原来的排序问题被划分成了两个更小的排序问题，而且这两个子问题仍然可以用归并排序来解决。

现在，我们按照前面学习的递归方法设计流程，重新分析归并排序。

首先是递归方法定义。根据前面的分析，我们的递归方法除了需要传入待排序数组，还需要确定当前待排序的区间。这里我采用左闭右开区间 [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年提出，同样也是一种典型的分治算法。它和归并排序一样，都是将一个排序问题转化成更小的排序问题，但划分子问题的方式有所不同。

快速排序的基本思路是：

从区间中选择一个元素作为基准值（pivot）。
通过一次分区操作，将基准值移动到一个合适的位置，使得它左侧的元素都不大于它，右侧的元素都不小于它。此时，基准值已经处于排序后的最终位置。
分别对基准值左侧和右侧的两个子区间进行快速排序。

和归并排序类似，我们一开始其实也无法自己划分出快速排序的子问题。但是通读完它的基本思路后，我们就能够发现：原来的排序问题被划分成了两个更小的排序问题，而这两个子问题仍然用快速排序来解决。

而且，快速排序划分子问题的方式确实很有意思：它先通过一次分区操作确定一个元素的最终位置，再将剩下的问题交给两个更小的子问题。

现在，我们按照前面学习的递归方法设计流程，重新分析快速排序。

快速排序的方法参数仍然是待排序数组和待排序区间，因此方法签名与归并排序类似，这里我直接给你：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】快速排序 (上）。

首先，我们先将 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) 区间表示尚未探索的区域。

结合图来看会更容易理解：

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 片金盘全部移动到另一根柱子上，并且必须遵守两条规则：

一次只能移动一片金盘。
大盘不能压在小盘上面。

传说还有一个古老的预言：当僧侣们完成这项任务时，世界将在轰鸣中毁灭。

为什么会这样？我们最后揭晓。

我们先去掉故事中的神话色彩，专注于这个问题本身：

有 3 根柱子，我们分别称它们为 A、B、C。有 n 个大小不同的圆盘，它们按照从大到小的顺序叠放在 A 柱子上。

现在，我们需要将这些圆盘全部移动到 C 柱子上，同时遵循两条游戏规则：

一次只能移动一个圆盘。
大圆盘不能放在小圆盘上面。

刚开始看到这个问题时，我们可能很难直接看出递归在哪里。所以这一次，我们先不急着找递归，而是从最简单的情况开始，一步一步自己摸索。

首先，我们从最简单的情况开始：只有一个圆盘时，该怎么做？

显然，只有一个圆盘时，我们直接将其从 A 移动到 C 就好了。

然后稍微增加一点难度：如果有两个圆盘，该怎么做？

这其实也难不到你。

我们知道，最终需要先将最底下的大圆盘移动到 C 上。但在这之前，必须先把上面的那个小圆盘移走，否则大圆盘根本没有办法移动。

我们先把最上面的圆盘移动到 B 上，给大圆盘腾出空间；然后将大圆盘从 A 移动到 C；最后，再把小圆盘从 B 移动到 C。这样，两个圆盘就都移动到 C 上了。

现在难度再上一个台阶：如果有三个圆盘，该怎么做？

这次看起来复杂了一些。我们还是先想办法把最下面最大的圆盘移动到 C。

但和刚才一样，在移动它之前，必须先把上面的两个圆盘移走。那这两个圆盘应该移动到哪里？显然，我们可以先把它们移动到 B 上。

至于这两个圆盘具体怎么移动，其实我们刚刚已经解决过了：不就是刚才的“移动两个圆盘问题”吗？只不过这一次，我们需要借助柱子 C，将这两个圆盘从 A 移动到 B。

为便于后续叙述，这里我给盘子从上到下依次编号 1、2、3。

首先，我们要将 1 从 A 移动到 C，这样就给 2 腾出了空间。

然后将 2 从 A 移动到 B。

最后将 1 从 C 移动到 B。

这样，3 就可以顺利从 A 移动到 C 了。

接下来，就是将 B 上的两个圆盘移动到 C。不知你有没有发现，我们又遇到了刚才已经解决过的问题。

这时候，递归的影子就开始出现了。

这个问题的步骤我就不继续展开了，相信你也能够自己想明白。

现在说递归还为时尚早。我们继续加大难度：如果有四个圆盘，该怎么做？

这一次，我们还是要先把最下面最大的圆盘移动到 C。在移动它之前，必须先把上面的 3 个圆盘移走。

而移动 3 个圆盘的问题，我们刚刚已经解决过了。只不过这次，我们需要借助 C 柱，将这三个圆盘从 A 移动到 B。

这样就可以把最大的圆盘顺利移动到 C 上。然后，再借助 A，将 B 上的 3 个圆盘移动到 C 上，整个问题就解决了。

请仔细回头看一下，我们刚才到底做了什么？

为了移动 4 个圆盘，我们先解决了一个“移动 3 个圆盘”的问题；移动完最大的圆盘后，又解决了一次“移动 3 个圆盘”的问题。

而移动 3 个圆盘，本身又可以拆成两个“移动 2 个圆盘”的问题。

这样继续往下拆，最终都会落到最简单的“移动 1 个圆盘”上。

所以，无论有多少个圆盘，解决汉诺塔问题的思路其实都是一样的。我们把这个过程总结一下：

假设现在有 n 个圆盘，我们需要将它们从 A 移动到 C，那么整个过程就可以分成三步：

借助 C，将前 n - 1 个圆盘从 A 移动到 B。
将最大的第 n 个圆盘直接从 A 移动到 C。
借助 A，将 B 上的 n - 1 个圆盘移动到 C。

不过，仔细观察刚才的三步，你会发现，第 1 步和第 3 步其实是在重复做同一件事情。

它们都是将 n - 1 个圆盘从一根柱子移动到另一根柱子，只不过起点、终点和辅助柱子发生了变化。

既然柱子的位置会发生变化，我们就不能把 A、B、C 写死，而应该描述它们各自的角色。

一根柱子是圆盘开始时所在的位置，我们称它为起始柱；一根柱子是圆盘最终要去的位置，我们称它为目标柱；剩下的一根，就是帮助我们完成移动的辅助柱。

有了这三个角色之后，我们再回头看看刚才的问题。

如果让一个方法来完成“移动若干个圆盘”这件事情，它需要知道两个方面的信息：

现在有多少个圆盘需要移动？
这些圆盘要从哪里移动到哪里，中间借助哪根柱子？

因此，这个方法需要 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 多亿年。珍惜当下，也许才是这个古老谜题留给我们最有意思的启示。

9千字硬核长文——递归基础

递归