一、递归初探：什么是递归？

说实话，我第一次接触递归时，整个人是懵的。

一个函数调用它自己？这不就是死循环吗？

后来我明白了——递归不是绕圈圈，而是层层递进，再层层返回。

1.1 生活中的递归现象

先别急着看代码。我们看看身边的世界。

俄罗斯套娃——你打开一个大娃娃，里面有个小一点的。再打开，还有更小的。直到最后一个实心的小娃娃，再也打不开了。

这个过程，就是递归：

• 打开娃娃 → 发现里面还有娃娃 → 继续打开
• 直到遇到最小的娃娃（终止条件）
• 然后一层层往回走

两面镜子对着照——你站在中间，会看到无限个自己。每个镜子里的影像，都包含另一个镜子的影像。

这也是递归。只不过它没有终止条件，所以是无限递归——程序里这叫栈溢出。

1.2 递归的数学基础：数学归纳法

递归和数学归纳法，其实是同一件事。

数学归纳法两步走：

1. 基础步骤：证明 n=1 时成立
2. 归纳步骤：假设 n=k 时成立，证明 n=k+1 时也成立

递归也是两步：

1. 终止条件：处理最简单的情况（比如 n=0 或 n=1）
2. 递归步骤：假设小规模问题已解决，解决当前问题

我当年学数据结构时，老师说过一句话，我一直记着：「你不需要关心递归的每一层是怎么执行的，你只需要相信它能正确返回。」

1.3 一个最简单的递归例子

计算 n 的阶乘。n! = n × (n-1) × (n-2) × ... × 1

def factorial(n):
    # 终止条件
    if n == 0 or n == 1:
        return 1
    # 递归步骤
    return n * factorial(n - 1)

print(factorial(5))  # 输出 120

运行过程是这样的：

factorial(5)
= 5 * factorial(4)
= 5 * (4 * factorial(3))
= 5 * (4 * (3 * factorial(2)))
= 5 * (4 * (3 * (2 * factorial(1))))
= 5 * (4 * (3 * (2 * 1)))
= 5 * (4 * (3 * 2))
= 5 * (4 * 6)
= 5 * 24
= 120

看到了吗？先一层层往下递，触底后一层层往上归。

这就是「递归」这个名字的由来。

1.4 递归 vs 循环

对比项	递归	循环
代码可读性	简洁，符合数学思维	需要手动维护状态
性能	有函数调用开销，可能栈溢出	通常更快
适用场景	树、图、分治算法	线性遍历、累加
理解难度	初学者容易晕	直观

说白了，递归和循环是等价的。任何递归都能改写成循环，反之亦然。

但有些问题，用递归写起来就是舒服。比如后面要讲的二叉树遍历、汉诺塔、快速排序——用循环写，代码能绕晕你。

1.5 本章知识体系

下面这张图，是我手绘的递归核心逻辑。你看一眼，就能明白递归到底在干什么。

这张图你看懂了吗？

核心就两点：

• 终止条件：问题小到可以直接解决
• 递归步骤：把大问题拆成小问题，调用自身去解决

我刚开始学递归时，总想跟踪每一层的变量值。后来发现，这完全是自找麻烦。

你只需要相信：递归函数能正确处理比当前更小的问题。剩下的，交给计算机去栈里折腾吧。

下一节，我们会深入递归的底层——栈帧。看看计算机到底是怎么一层层调用、一层层返回的。到时候你会恍然大悟：哦，原来递归是这样工作的！