一、重新认识递归

你在学习到编程语言中函数/方法这个概念时，肯定听过“递归”这个概念。但是你真的理解它吗？

大多数教程一般只会跟你说：递归函数就是“自己调用自己的函数”。

然后呢？好像懂了，又好像没懂。。。

其实这并不是你一个人的问题，而是一个普遍的现象！

因为递归的核心，其实是一种 “反直觉”的思维方式——它不符合我们线性的常规思维，这正是理解上的难点所在。

别担心！下面我将用一个简单的例子，告诉你递归思维的难点。

1.从求阶乘开始

我们曾在高中阶段学过阶乘这个概念，其定义式如下：

$$ n! =1\times2\times3\times...\times n $$ 特别地，$0!=1$

如果让你去计算$5!$，你会怎么去算？你应该会按照定义式进行计算，例如：$5!=1\times2\times3\times4\times5=120$

现在我们换一个视角来看待阶乘的定义。观察 1 乘到 n-1 这一串式子，结合阶乘的定义，它是不是 (n-1)! 呢？

正是如此，阶乘的定义还有另外一个表现形式（递归定义）：

$$ n! = \begin{cases} 1 & \text{if } n = 0 \ n \times (n-1)! & \text{if } n > 0 \end{cases} $$

这便是阶乘的递归定义，即用自身来定义自身。

那这个递归定义具体是如何计算 $5!$的呢？接下来我们来看一下：

要求$5!$，得先求 $5 \times 4!$，但 $4!$ 未知，所以要先求它；

要求$4!$，得先求 $4 \times 3!$，但 $3!$ 未知，所以要先求它； 如此循环往复。。。

一直求到 $1!$ 时，此时要求 $1 \times 0!$。注意看，此时 $0!$ 已经是递归定义中的最小已知项了（$0! = 1$）于是我们便可以逐层往上回溯，最终绕一大圈，总算求出了 $5!$ 的值 ！

从上面的叙述中，其实已经体现了递归思维解决问题的三大核心步骤：

1. 逐层分解同类子问题：原问题 $n!$被分解为同类且规模更小的子问题(n-1)!，层层向下递进。
2. 分解到最小子问题：问题分解是有尽头的。分解到 $0!$时触底，此时必须返回一个确切的结果（即 $0! = 1$），作为递归链条的终点（基准条件）。
3. 自底向上回溯，逐层合并出答案：从最小子问题 $0!$ 开始，逐层回溯，将子问题的解代入父问题，最终求出原问题 $n!$ 的解。

看到这里，你可能会产生一个疑问：为什么说递归思维是“反直觉”的？

其实根本原因在于思考方向的对立。

先说我们人类的常规思维。我们更习惯于从已知到未知，例如我们本能地会想到直接从 1 开始累乘到 n，这是正向推导的体现。

然而，递归思维是反过来的。它一般是从未知到已知，例如从 $n!$ 出发，逆向分解到 $0!$，最后求得结果，这是逆向推导的体现。

2.扫清对递归思维的误解

看到这，你可能有如下的感受：

“用递归思维来求解阶乘问题真的好麻烦呀！绕这么一大圈，还不如前一个定义直观！”

现在看来的确如此！用递归思维解决这类问题有种“杀鸡用牛刀”的笨拙感。不过别急，我在这里大费周章地铺垫，是为了带你重新认识递归。在接下来的章节中，你会真切感受到递归在解决某些特定复杂问题时的精妙与优雅！

在正式进入递归思维的学习之前，我想给你一些温馨提醒：

1. 每当遇到递归问题时，不要被常规思维束缚住，要勇于跳出常规思维的舒适圈。
2. 一步一个脚印，从易到难的积累用递归思维解决问题的经验。学习递归时要先模仿，积累到一定量后自然会产生质变，后续才有创新的可能性。
3. 不要滥用递归思维，它不是万金油，它有自己专门的适用场景，切忌为了用而用！

请铭记这些提醒！接下来我们就正式开始进入递归思维的实际运用环节！

二、设计合格的递归函数

1.四要素

一个合格的递归函数应该具备以下的四要素：

1. 明确的函数契约：你需要明确这个函数的定义、输入输出。

2. 优先处理最小子问题：这是递归函数的终止条件，我们必须优先处理！

3. 缩小规模，递归求解：递归调用函数自身以解决子问题。

4. 组合结果，向上返回：基于子问题的答案计算当前层结果。

2.实战：完成阶乘案例的递归函数设计

接下来我将带着你一起，基于上面的四要素来完成阶乘案例的递归函数。

第一步：定义函数声明

首先这个用于求阶乘的函数定义其实非常简单，输入就是一个整数n呗（为了简单、方便起见，这里就不处理输入为负整数的边界判断了）。

返回结果也是一个整数（这里暂时不考虑可能的整数溢出隐患）

因此我们可以定义这样的函数声明：

▼
java
复制代码
int factorial(int n);

第二步：优先处理最小子问题

由阶乘的递归定义我们知道，n为0的时候就是阶乘函数的最小子问题，因此我们直接返回1即可。

相关的代码片段如下：

▼
java
复制代码
if(n == 0){
    return 1;
}

第三步：缩小规模，递归求解

由阶乘的递归定义我们知道，要求解n的阶乘，首先要求解n - 1的阶乘。

相关的代码片段如下：

▼
java
复制代码
factorial(n - 1);

第四步：组合结果，向上返回

由阶乘的递归定义我们知道，我们只需要在$n - 1!$这个子问题结果的基础上乘以n就是$n!$的结果了！

相关代码片段如下：

▼
java
复制代码
return n * factorial(n - 1);

最后把上述的代码片段合并，即可得到一个完整的递归函数。

▼
java
复制代码
int factorial(int n){
    if(n == 0){
        return 1;
    }
    return n * factorial(n - 1);
}

练习：斐波那契数列

斐波那契（Fibonacci）数列是指这样一个数列：0，1，1，2，3，5，8，13，21，34，55，89……

这个数列有一个最大的特点，就是从第3项开始，每一项都是前两项之和！

其递归定义如下： $$ fibonacci(n) = \begin{cases} 0 & \text{if } n = 1 \ 1 & \text{if } n = 2 \ fibonacci(n-1)+fibonacci(n-2) & \text{if } n > 2 \end{cases} $$

你的任务：设计一个用于求解斐波那契数列第n项的函数，请分别用递归和非递归实现，你可以暂时不考虑负数输入和整数溢出问题。

答案：

递归版实现：

▼
java
复制代码
int fibonacci(int n){
 if(n == 1){
     return 0;
 }
 if(n == 2){
     return 1;
 }
 return fibonacci(n - 1) + fibonacci(n - 2);
}

非递归版实现：

▼
java
复制代码
int fibonacci(int n){
 if(n == 1){
     return 0;
 }
 if(n == 2){
     return 1;
 }
 int a = 0, b = 1, result = 0;
 
 for(int i = 3; i <= n; i++){
     result = a + b;
     a = b;
     b = result;
 }
 return result;
}

对比这两种方式的实现，你会发现递归函数写起来尽然会如此简洁，这也是递归函数的特点之一。但是从运行速度上，递归版实现会遥遥落后与非递归实现，我们将在后面介绍具体原因。

三、递归树

递归树并不是什么高大上的玩意，它仅仅只是一个用于辅助我们理解和分析递归函数执行过程的可视化工具！

递归树中各元素的含义：

【结点】表示递归函数的一次调用，我们一般在里面标注当前递归函数的参数。

【边】表示递归调用关系，孩子结点是双亲结点的子问题。

接下来我们画一画前面的斐波那契数列练习中，n为5时的递归树。

为方便，我就把函数名简写为f了。

递归树不仅可以直观地体现子问题分解的过程，它有时还可以帮我们分析出递归函数可能存在的性能问题。

还记得我之前说过“采用递归实现的斐波那契函数执行速度遥遥落后”么？接下来请你重点观察一下上面的递归树，看看你发现了什么问题？

你应该会注意到递归树中存在一些重复计算，比如f(3)这个子问题就被重复计算了两次。而且在当 n 更大的时候，会出现更多的重复计算！这就是效率低下的原因之一。

还有一个原因就是递归函数会产生多次自我调用，每一次调用都需要创建栈帧。相比非递归版本，递归函数往往需要占用更多的栈内存。

这里不会介绍如何优化，感兴趣的同学可以自行搜索关键词：斐波那契 递归 备忘录优化。

四、理解递归的核心：信任跳跃

一般我们想深入了解某个函数的功能具体是如何实现时，我们往往会亲自模拟一遍它的执行流程。

这对于普通函数是有效的，但是对于复杂一些的递归函数来说，这种方式往往会把你拖向一个看不见的“深渊”。

不少人觉得递归函数难以理解的核心原因是他们都想通过模拟执行来理解递归函数，最终却迷失于深不可测的递归调用链中。

我们其实不应该深入到递归调用的细节中去，这不是我们人脑擅长的事情，这是计算机最擅长的事情。

因此请你之后在学习一个递归函数时，请不要再追问“子问题是如何被解决的”，而是转而去相信递归调用后子问题已经被解决了。这种思维方式的转变，就是信任跳跃。

一旦你完成这个跳跃，你的思路就会从“递归是怎样一层层展开的”中解放出来，转而专注于真正重要的问题：如何利用子问题的解，组合出当前问题的解。

带着这个视角，你再回头看前面的递归函数——忽略递归调用的底层细节，只关心当前层在做什么。有没有觉得，它们突然清晰了很多？

五、凭什么可以信任跳跃？

信任跳跃听起来像是一种心理暗示，但它背后有坚实的数学基础：数学归纳法。

1.回顾数学归纳法

我记得我是在高中的数学课堂中学过的数学归纳法。

数学归纳法有三个重要步骤：

1. 归纳奠基：验证命题在最小情况是否成立（如 n=1时）
2. 归纳假设：假设 n = k时，命题成立。
3. 归纳递推：基于归纳假设推出 n = k + 1时命题也成立。

只要这三步满足，就能证明这个命题对任意正整数都成立。

举个例子：用数学归纳法证明如下的等差数列公式成立

求证： $$ 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} $$

一、归纳奠基

n = 1 时，左边为 1，右边代入得 1。验证通过。

二、归纳假设

假设 n = k （k 是 任意一个正整数）时命题成立，即：

$$ 1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2} $$

这一步，就类似于递归函数中我们假设子问题已经被解决！

三、归纳递推

考虑前 k + 1 项和： $$ 1 + 2 + 3 + \cdots + k + (k + 1) $$

利用归纳假设，将前 k 项替换为 $\frac{k(k+1)}{2}$ 得到：

$$ \frac{k(k+1)}{2}+ (k + 1) $$

通分化简：

$$ \frac{(k + 1)[(k+1)+1]}{2} $$

这正是原公式在 n = k + 1 时的结果，因此归纳递推成立。

综上，命题对所有正整数成立。

2.递归函数和数学归纳法的关系

递归函数的各个要素，恰好可以一一对应到数学归纳法的步骤上：

递归函数要素	数学归纳法步骤	批注
明确的函数契约	命题定义	你得先清楚递归函数是解决什么问题的
优先处理最小子问题	归纳奠基	最小情况的处理必须正确，地基不牢，整栋楼都危险
缩小问题规模，递归求解	归纳假设	假设递归调用能正确解决子问题——对应归纳假设中“假设 n = k 时成立”
组合结果，向上返回	归纳递推	不负责证明，而是利用子问题的解，正确组合出当前问题的解

这个对应关系说明了一件事：递归函数本质上就是对数学归纳法的程序化表达。

3.信任跳跃的坚实依据

此时我终于可以回答 “凭什么可以信任跳跃”了！

递归函数能正确工作的保障，在于它严格遵循了数学归纳法的逻辑：

1. 我们亲自确保了最小子问题的解法是正确的。（归纳奠基）
2. 我们假设递归调用能正确解决子问题（归纳假设）。这不是盲目自信，而是归纳逻辑中的标准操作。
3. 在此基础上，我们专注于如何利用子问题的解正确组合出当前问题的解，并保证这个组合的逻辑是严谨、正确的（归纳递推）。

所以说，只要 1、3 这两步正确，那么根据数学归纳原理，这个递归函数对于所有有效输入都必然正确。

因此，我们不需要、也不应该去模拟递归过程。信任跳跃不是放弃思考，而是把你有限的注意力从“验证过程”转移到“设计当前层逻辑”上——这是人脑最擅长的事，也是递归函数设计的核心所在。

最后我还需要提醒你的一点是，上述的第 2 步看似简单，但是却隐含这一个大前提——你得先能找到规模为 n 的问题的子问题。这对新手来说往往是最大的难点。但别担心，遇到新问题时卡在这一步完全正常。我的建议还是：先模仿，再创新，当你积累的大量的练习之后，你自然会习得找到子问题的切入点这个能力。

六、趁热打铁

不知道前面的叙述有没有刷新你对于递归的认知，如果暂时还不能接受可以多看几次。

在确保你已经理解我想表达的核心观点之后，接下来你便可以在不知不觉中理解两个经典的递归问题——归并排序和汉诺塔问题。

1.归并排序

归并排序的函数声明如下：

▼
java
复制代码
void mergeSort(int[] arr, int l, int r);

其含义是：对int数组arr中[l,r)这个范围内的元素进行归并排序。

归并排序的流程如下：

先考虑基准情况。可见，当[l,r)内的元素个数小于等于1时，无需排序。

然后再是一般情况：

1. 将待排序区间一分为二。以 int mid = (l + r) / 2 为界，将待排序区间划分为[l,mid)和[mid,r)这两部分。
2. 分别对这两部分进行归并排序（递归调用）。
3. 递归调用完成之后，[l,mid)和[mid,r)这两部分的元素分别就是有序的了。最后我们只需要考虑合并两个有序子数组的元素，这样便完成了对 [l,r) 范围内的元素的排序。

说到这，我相信你应该有思路了，接下来赶快去试试吧！

参考答案：

▼
java
复制代码
void mergeSort(int[] arr, int l, int r) {
    if (r - l <= 1) {
        return;
    }
    int mid = (l + r) / 2;

    // 对左半边归并排序
    mergeSort(arr, l, mid);
    // 对右半边归并排序
    mergeSort(arr, mid, r);

    // 合并两个有序数组
    
    // 先用额外空间存储这两段区间内的元素
    int[] left = Arrays.copyOfRange(arr, l, mid);
    int[] right = Arrays.copyOfRange(arr, mid, r);

    // i指向left，j指向right，k指向arr当前排序区间的开始
    int i = 0, j = 0, k = l;

    // 合并两个有序数组
    while (i < left.length && j < right.length) {
        int next;
        if (left[i] < right[j]) {
            next = left[i++];
        } else {
            next = right[j++];
        }
        arr[k++] = next;
    }
    if (i == left.length) {
        while (j < right.length) {
            arr[k++] = right[j++];
        }
    } else {
        while (i < left.length) {
            arr[k++] = left[i++];
        }
    }
}

2.汉诺塔

问题背景：

你需要遵循如下规则，将柱子A上的所有圆盘移动到柱子C上，并且保持原来的顺序。

1. 每次只能移动一个盘子
2. 移动过程大盘不能叠在小盘上
3. 可借助 B柱 暂存盘子

解决汉诺塔问题的函数声明如下：

▼
java
复制代码
void hanoi(int n, char from, char aux, char to);

参数说明：

• from、aux、to代表三根柱子的名称。其中from表示起始柱子，aux表示用于辅助的柱子，to表示目标柱子。
• n是起始柱子上待移动的圆盘数量。

这个函数的使命是：将 from 上的前 n 个圆盘借助 aux 移动到 to 上。

从最简单的情况开始：

当 n = 1 时，只有一个盘子，直接从 from 移到 to 即可。这是基准情况。

现在考虑 n = 2：

你应该很快能想到：先把小盘子从 from 移到 aux，再把大盘子从 from 移到 to，最后把小盘子从 aux 移到 to。三步完成，不算难。

仔细观察这个过程，你会发现核心思路就三步：腾空间（把小盘子移开）、落定（移动最底下的大盘子）、盖上去（把小盘子放回来）。

再来看 n = 3：

步骤虽然变多了，但是思路和 n = 2 时完全一致：

1. 先把 from 上面的两个盘子借助 to 移动到 aux 。——腾空间
2. 再把最底下的大盘子直接从 from 移动到 to。——落定
3. 最后再把 aux 上的两个盘子借助 from 移动到 to。——盖上去

到这里你会发现：第 1 步和第 3 步，其实就是 hanoi(2, ...) 在做的事情！

这个模式完全可以应用到任意数量的盘子：

1. 先把 from 上面的n-1个盘子借助 to 移动到 aux 。——腾空间
2. 再把最底下的大盘子直接从 from 移动到 to。——落定
3. 最后再把 aux 上的n-1个盘子借助 from 移动到 to。——盖上去

第1步和第3步就是两个递归调用，我们相信它能够完成，至于这 n-1 个盘子具体怎么移动的，我们也无需关心。

说到这，你应该已经清楚hanoi函数具体该怎么实现了，快去试试吧！

参考答案：

▼
java
复制代码
void hanoi(int n, char from, char aux, char to){
 if (n == 1){
     System.out.println("将圆盘从" + from + "挪动到" + to);
     return;
 }
 // 将前n - 1个圆盘借助to移动到aux上
 hanoi(n - 1,from,to,aux);
 // 将最底下的圆盘从 from 移到 to
 System.out.println("将圆盘从" + from + "挪动到" + to);
 // 将aux上的所有圆盘借助from移动到to上
 hanoi(n - 1,aux,from,to);
}

测试代码：

▼
java
复制代码
hanoi(3,'A','B','C');

七、致谢

感谢B站UP主：五点七边分享的递归系列视频彻底刷新了我对于递归思维的理解，现在的我已经不再畏惧递归函数了！

而且他的这个系列视频正是我决定写这篇文章（我花了4天左右的时间打磨细节）的重要精神支柱！