递归函数：让函数学会“分身术”

你有没有遇到过这样的问题：要数清一堆套娃里到底有多少层？或者要计算全班同学两两握手一共多少次？这些问题都有一个共同特点——它们可以被拆分成一个“小一号”的同样问题，直到最简单的情况。递归就是编程里用来解决这类问题的利器：一个函数在执行过程中调用自己，就像套娃一样，一层套一层，直到碰到最小、不能再分的那个“娃娃”。

1. 什么是递归？用生活例子秒懂

俄罗斯套娃模型

想象你面前有一套俄罗斯套娃：最大的娃娃里装着一个稍小的，稍小的里面还有一个更小的，直到最小的不能再打开。要打开所有娃娃，你可以重复同一个动作：打开当前娃娃，拿出里面的小娃娃。这就是递归的核心思想——重复做同一件事，每次处理的数据规模变小。

排队买冰淇淋的小明

假设小明排队买冰淇淋，他想知道自己前面有几个人。他不能直接回头数，只能问前面的人：“你前面有几个人？”前面的人又问更前面的人……直到最前面的人回答“0个”。然后一路往回传：“我前面有0个，所以前面的人有1个……”。这也是递归：把问题（当前人的位置）交给下一个更小规模的人去解决。

递归的本质：把一个大问题，分解成一个相同结构但规模更小的子问题，直到子问题简单到可以直接给出答案。

2. 递归的两大要素：缺一不可

任何正确的递归函数都必须包含两个部分：

要素一：基线条件（停止条件）

定义：最简单、不能再分解的情况。当满足这个条件时，函数不再调用自己，而是直接返回一个结果。
作用：防止无限递归，就像套娃里最小的那个实心娃娃——不能再打开。
没有基线条件的递归就是死循环，程序会崩溃（栈溢出）。

要素二：递归步骤（递推关系）

定义：将问题分解为更小的同类问题，然后调用自身来解决这个更小的问题。
通常形式：当前结果 = 对当前数据做一点处理 + 递归调用处理剩余部分

3. 经典例子：计算阶乘（n!）

阶乘的定义：
n! = n × (n-1)!，并且 1! = 1。
这天然就是递归！因为 (n-1)! 和 n! 是同一类问题，只是规模小 1。

def factorial(n):
    if n == 1:          # 基线条件：1的阶乘等于1
        return 1
    else:               # 递归步骤：n! = n * (n-1)!
        return n * factorial(n - 1)

print(factorial(5))    # 输出：120

计算机是如何一步步运行的？ 就像剥洋葱，一层层深入，再一层层返回：

factorial(5) 发现 n != 1，于是计算 5 * factorial(4)，先暂停等待 factorial(4) 的结果。
factorial(4) 计算 4 * factorial(3)，等待结果……
直到 factorial(1) 直接返回 1。
然后 factorial(2) 得到 2 * 1 = 2 返回给上一层……
最后 factorial(5) 得到 5 * 24 = 120。

这个过程叫递归调用栈：每次调用都把当前状态压入栈，返回时弹出。

4. 第二个例子：倒计时发射火箭

这个例子展示了递归的“先递后归”过程——先一路输出数字向下，到基线条件后再输出“发射！”。

def countdown(n):
    if n <= 0:          # 基线条件：n小于等于0时停止递归
        print("发射！")
    else:
        print(n)               # 先打印当前数字
        countdown(n - 1)        # 然后递归调用，处理更小的数字

countdown(3)
# 输出：
# 3
# 2
# 1
# 发射！

注意：这里递归调用在 print 之后，所以先打印再递归。如果交换顺序，输出就会反过来（先递归到底，再依次打印数字——那就是从1到3的顺序了）。你可以自己试试看。

5. 调皮的陷阱：新手常犯的错误

❌ 错误1：忘记写基线条件

def bad_recursive():
    return bad_recursive()  # 没有停止条件，无限调用，程序崩溃

运行后会报错：RecursionError: maximum recursion depth exceeded（递归深度超过最大限制）。

❌ 错误2：基线条件写错，导致永远达不到

def countdown_wrong(n):
    if n == 0:          # 如果传入的是负数，永远到不了0
        print("发射！")
    else:
        print(n)
        countdown_wrong(n - 1)

countdown_wrong(-5)  # 会无限递归吗？实际上 n 越来越小，永远不等于0，会一直减下去直到超出深度

解决方法：把条件改为 n <= 0 覆盖负数情况。

❌ 错误3：递归步骤没有让问题规模缩小

def infinite(n):
    if n == 0:
        return 0
    else:
        return infinite(n)  # 传入的n没变，会无限递归

每次调用必须让参数更接近基线条件！

❌ 错误4：递归层数太深导致栈溢出

Python 默认递归深度约 1000 层。如果计算 factorial(99999) 就会栈溢出。这时候应该改用循环（迭代）。

6. 完整可运行示例：用递归计算斐波那契数列（附记忆化优化）

斐波那契数列：0, 1, 1, 2, 3, 5, 8, 13...
定义：fib(0)=0, fib(1)=1, fib(n)=fib(n-1)+fib(n-2)（n≥2）。

未优化的递归（效率低，重复计算多）：

def fib_slow(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib_slow(n-1) + fib_slow(n-2)

print(fib_slow(10))  # 输出：55

计算 fib_slow(40) 就很慢了，因为会重复计算很多次相同的值。

记忆化优化（把算过的结果存起来，避免重复）：

# 用字典存储已经计算过的斐波那契数
memo = {}

def fib_fast(n):
    if n in memo:          # 如果已经算过，直接返回
        return memo[n]
    if n == 0:
        result = 0
    elif n == 1:
        result = 1
    else:
        result = fib_fast(n-1) + fib_fast(n-2)
    memo[n] = result       # 保存结果
    return result

print(fib_fast(100))  # 瞬间输出 354224848179261915075

7. 递归 vs 循环：什么时候选谁？

很多递归问题都可以用循环解决。比如阶乘用循环：

def factorial_loop(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

选递归的情况：

问题天然是递归定义的（树、分治、汉诺塔）
代码更清晰、更短
问题规模不大（深度不超几千）

选循环的情况：

性能要求高（递归有调用栈开销）
容易用循环实现（比如阶乘、遍历）
递归深度可能很大

小贴士：很多复杂问题（比如文件夹遍历、网页爬虫、游戏AI）用递归写起来比循环简单得多。学会递归，就像拿到一把万能钥匙！

8. 相关知识点指引

你已经学会了递归的基本思想，接下来可以继续探索：

分治算法：把大问题分成几个小问题分别解决，再合并结果（如归并排序）
树与图的遍历：文件夹目录结构、家族族谱、迷宫寻路都非常适合递归
汉诺塔问题：经典的递归练习题
尾递归优化：某些语言可以优化递归，但Python不支持
记忆化搜索：用缓存加速递归（像上面的斐波那契）
回溯算法：尝试所有可能，走不通就退回（如八皇后问题）

递归不仅仅是一种编程技巧，更是一种思维方式——把一个复杂问题不断“简化”，直到不能更简单为止。下次遇到难题，不妨问自己：“这个问题能不能拆成一个更小的、同样的问题？” 如果能，递归就是你的好朋友！

例题精讲