Python 递归函数：让函数"自己调用自己"的艺术

引言：站在两面镜子之间的奇妙景象

你有没有试过站在两面相对的镜子中间？你会看到镜子里有镜子，镜子里的镜子里还有镜子……一直延伸下去，仿佛无穷无尽。

递归函数就是这个原理：一个函数在它的内部调用它自己。

这听起来有点疯狂——一个东西怎么能"调用自己"呢？就像一个人怎么能"把自己举起来"？但递归恰恰是编程中最优雅、最强大的思维方式之一。很多复杂问题（比如遍历文件夹、计算斐波那契数列、走迷宫），用递归写出来只有几行代码，用其他方法却要写几十行。

今天，我们就从零开始，彻底搞懂递归这个看似神秘的概念。

---

一、什么是递归函数？

1.1 递归的定义

在函数内部，可以调用其他函数。如果一个函数在内部调用自身本身，这个函数就是递归函数。

def story():
    print("从前有座山，山里有座庙，庙里有个老和尚在讲故事：")
    story()  # 函数调用自己！

这个故事大家都听过——"从前有座山"的故事可以无限讲下去，因为每讲一次，故事里面又包含了一个"讲故事"的动作。这就是递归最形象的写照。

注意：上面这个例子会无限循环下去（直到报错），因为它没有"停下来的条件"。一个合格的递归函数必须有终止条件，我们后面会详细讲。

1.2 生活化理解：排队问题

想象你在电影院排队买票，你想知道自己排在第几位，但你懒得数。你可以问前面的人："你排第几？"

• 前面的人也不知道，于是他也问他前面的人；
• 这个问题一直往前传，直到问到第一个人，他说："我排第 1！"（终止条件）
• 然后答案依次往回传：第 2、第 3、第 4……最终传回你这里，你就知道自己排第几了。

这个过程就是典型的递归：

• 递（传递）：问题一层层往前传，越传越小；
• 归（回归）：到达最简单的情况后，答案一层层往回传。

1.3 递归的三大要素

任何一个正确的递归函数，都必须包含三个要素：

要素	说明	排队例子
终止条件（基例）	最简单的情况，直接给出答案，不再递归	第 1 个人知道自己排第 1
递归调用	函数调用自己，但问题规模必须变小	问前面一个人排第几
问题规模缩小	每次递归都让问题更接近终止条件	每问一次，就离队首更近

核心口诀：大事化小，小事化了。

---

二、第一个递归实战：计算阶乘

2.1 什么是阶乘

阶乘是数学中的经典运算，n! 表示从 1 乘到 n：

5! = 1 × 2 × 3 × 4 × 5 = 120

2.2 用循环的思路

先用我们熟悉的循环来写：

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

print(fact_loop(5))  # 120

这个写法没问题，但我们换个角度思考。

2.3 用递归的思路：发现"套娃结构"

仔细观察阶乘的定义，你会发现一个秘密：

5! = 5 × 4 × 3 × 2 × 1
   = 5 × (4 × 3 × 2 × 1)
   = 5 × 4!

5! 里面藏着一个 4!！ 同理，4! 里面藏着 3!……这就像俄罗斯套娃，大娃娃里面装着小一号的娃娃。

用数学语言表达：

fact(n) = n × fact(n - 1)

只有一个特殊情况：fact(1) = 1（这就是终止条件）。

2.4 翻译成代码

把上面的数学公式几乎原封不动地翻译成 Python：

def fact(n):
    if n == 1:        # 终止条件：最简单的情况
        return 1
    return n * fact(n - 1)   # 递归调用：问题规模缩小

验证一下：

>>> fact(1)
1
>>> fact(5)
120
>>> fact(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

短短 4 行代码，连 100 的阶乘（一个 158 位的巨大数字）都能算出来！Python 的整数没有大小限制，所以不会溢出。

2.5 递归的执行过程：慢镜头回放

计算 fact(5) 时，计算机内部发生了什么？让我们像放电影一样逐帧看：

=> fact(5)
=> 5 * fact(4)
=> 5 * (4 * fact(3))
=> 5 * (4 * (3 * fact(2)))
=> 5 * (4 * (3 * (2 * fact(1))))   # 到达终止条件，开始"回归"
=> 5 * (4 * (3 * (2 * 1)))
=> 5 * (4 * (3 * 2))
=> 5 * (4 * 6)
=> 5 * 24
=> 120

生活化理解：这就像公司老总布置任务——

• 老总对总监说："给我算出 5!，我只需要 5 乘以 4! 的结果。"
• 总监对经理说："给我算出 4!，我只需要 4 乘以 3! 的结果。"
• ……
• 传到最后一个实习生，他说："1! 就是 1，我直接知道答案！"
• 然后答案逐级上报：实习生报给主管，主管算完报给经理……最终报给老总。

关键洞察：每一层调用都"停在那里等结果"，直到最底层返回，才一层层完成计算。这就是为什么递归需要消耗额外的内存——每一层都要"记住自己在等谁"。

---

三、递归的代价：栈溢出问题

3.1 什么是栈（Stack）

在计算机中，函数调用是通过栈这种数据结构实现的。

生活化理解：栈就像一摞盘子——

• 每次调用一个函数，就往上面放一个盘子（专业术语叫"栈帧"，里面保存着这一层函数的局部变量、返回地址等信息）；
• 函数执行完返回，就把最上面的盘子拿走；
• 只能从最顶部放和取，不能从中间抽。

正常情况下，函数调用几层就返回了，盘子放几个拿几个，相安无事。

3.2 栈溢出：盘子放太多了

但递归不一样——在拿到最底层结果之前，所有盘子都不能拿走。

计算 fact(1000) 意味着栈上要同时压着 1000 个盘子。而操作系统给每个程序的栈空间是有限的（Python 默认递归深度限制约为 1000 层），盘子放不下，就栈溢出了：

>>> fact(1000)
Traceback (most recent call last):
  ...
RecursionError: maximum recursion depth exceeded in comparison

生活化理解：就像让一个人同时记住 1000 件"等下要做的事"——他记不住，直接崩溃了。

3.3 查看和修改递归深度限制

可以用以下代码查看和调整限制（但不推荐依赖它）：

import sys
print(sys.getrecursionlimit())   # 默认通常是 1000

sys.setrecursionlimit(10000)     # 调大限制（治标不本，且设置过大可能导致程序真正崩溃）

---

四、尾递归优化：理论很美，Python 很现实

4.1 什么是尾递归

解决栈溢出的一个思路是尾递归优化。

尾递归是指：函数返回时，直接返回对自身的调用，return 语句里不包含任何其他运算。

对比两种写法：

# 普通递归：return 里有乘法表达式 n * fact(n-1)，不是尾递归
def fact(n):
    if n == 1:
        return 1
    return n * fact(n - 1)     # 返回时还要做乘法

# 尾递归：return 只返回函数调用本身
def fact(n):
    return fact_iter(n, 1)

def fact_iter(num, product):
    if num == 1:
        return product
    return fact_iter(num - 1, num * product)   # 返回时什么都不用算

生活化理解：

• 普通递归像"领导等下属汇报后再加工"——每层都要留在原地等结果，回来还要再算一步（乘以 n）。
• 尾递归像"接力赛"——每一棒把当前累计的结果（product）直接交给下一棒，交完就可以退场了，不需要在原地等。

4.2 尾递归的执行过程

=> fact_iter(5, 1)
=> fact_iter(4, 5)      # 累计乘积 5
=> fact_iter(3, 20)     # 累计乘积 20
=> fact_iter(2, 60)     # 累计乘积 60
=> fact_iter(1, 120)    # 到达终止条件，直接返回累计结果
=> 120

注意：中间结果（5、20、60）通过参数 product 一路向下传递，不需要任何一层"等着"。

理论上，编译器/解释器发现尾递归后，可以复用同一个栈帧——旧盘子直接扔掉换新盘子，栈永远不增长，无论递归多少层都不会溢出。尾递归在效果上和循环完全等价，所以没有循环语句的编程语言（如某些函数式语言）只能靠尾递归来实现循环。

4.3 残酷的现实：Python 不做尾递归优化

遗憾的是，Python 的标准解释器（CPython）并没有针对尾递归做优化。

也就是说，即使你把 fact 改成上面漂亮的尾递归形式，fact(1000) 依然会栈溢出。Python 之父 Guido 明确反对引入尾递归优化，原因之一是它会让调试时的调用栈信息变得难以理解。

实用结论：

在 Python 中，如果递归深度可能超过几百层，请老老实实改写成循环。递归应该用在"天然适合递归且深度可控"的场景。

---

五、递归 vs 循环：什么时候用哪个？

理论上，所有递归都可以改写成循环，反之亦然。那么什么时候用递归？

对比维度	递归	循环
代码可读性	简洁优雅，贴近数学定义	有时更繁琐
内存开销	大（每次调用占一个栈帧）	小（只占固定变量）
执行效率	较低（函数调用有开销）	较高
栈溢出风险	有，深度受限	无
适用场景	树形结构、分治问题、深度可控	简单重复、大规模迭代

经验法则：

• 问题本身有明显的"套娃结构"（树、目录、数学递推公式）→ 用递归，清晰；
• 只是简单的"重复 N 次"，且 N 可能很大 → 用循环，安全。

---

六、经典实战：汉诺塔问题

6.1 问题背景

汉诺塔是一个古老的益智游戏：

• 有三根柱子 A、B、C，A 柱上套着 n 个大小不同的盘子，大盘在下，小盘在上；
• 目标：把所有盘子从 A 移到 C；
• 规则：每次只能移动一个盘子，且任何时候大盘不能压在小盘上面。

传说印度神庙里的僧侣在移动 64 个金盘，完成之日就是世界末日——别紧张，算一下就知道，即使每秒移动一个盘子，也需要 5849 亿年（移动次数是 2⁶⁴ - 1）。

6.2 递归思维：别想每一步，只想"框架"

用递归解汉诺塔的秘诀是：不要去想每一步具体怎么走，而是相信递归会帮你搞定细节。

假设有 n 个盘子在 A，要移到 C，借助 B。三步走：

1. 把上面 n-1 个盘子从 A 移到 B（借助 C）——交给递归去办；
2. 把最底下最大的盘子从 A 移到 C——这一步自己动手；
3. 把 n-1 个盘子从 B 移到 C（借助 A）——交给递归去办。

生活化理解：就像搬一摞书——你不需要纠结每一本书怎么搬，只要想："先把上面那堆（n-1 本）搬到旁边，把最底下这本大厚书搬到目的地，再把旁边那堆搬过来。"至于"那堆"怎么搬？同样的方法，递归处理。

6.3 代码实现

def move(n, a, b, c):
    if n == 1:
        # 终止条件：只有一个盘子，直接移过去
        print(a, '-->', c)
        return
    # 第 1 步：把 n-1 个盘子从 A 经 C 移到 B
    move(n - 1, a, c, b)
    # 第 2 步：把最大的盘子从 A 移到 C
    print(a, '-->', c)
    # 第 3 步：把 n-1 个盘子从 B 经 A 移到 C
    move(n - 1, b, a, c)

move(3, 'A', 'B', 'C')

输出：

A --> C
A --> B
C --> B
A --> C
B --> A
B --> C
A --> C

7 步搞定 3 个盘子（2³ - 1 = 7），完全正确。

6.4 解读参数变化的玄机

注意 move(n - 1, a, c, b) 中参数顺序的变化：函数签名是 move(n, 源, 辅助, 目标)。

• 第 1 步 move(n-1, a, c, b)：源是 A，目标是 B，所以辅助柱是 C；
• 第 3 步 move(n-1, b, a, c)：源是 B，目标是 C，所以辅助柱是 A。

柱子只是"角色"，每次调用时哪个柱子扮演什么角色会变——这正是用参数表示柱子的精妙之处。

---

七、更多递归应用场景

递归不是玩具，它在实际开发中无处不在：

7.1 遍历文件夹（树形结构）

import os

def list_files(directory, indent=0):
    for item in os.listdir(directory):
        path = os.path.join(directory, item)
        print('  ' * indent + item)
        if os.path.isdir(path):
            list_files(path, indent + 1)   # 文件夹里还有文件夹？递归进去

list_files('D:/my_project')

文件夹套文件夹，天然就是递归结构。用循环写这个会麻烦得多（需要自己维护一个栈）。

7.2 斐波那契数列（数学递推）

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

性能警告：这个写法虽然优雅，但存在大量重复计算（计算 fib(5) 时 fib(3) 会被算两遍），时间复杂度是指数级的。实际中应改用循环或加缓存（functools.lru_cache），这是面试常考点。

7.3 处理嵌套数据（JSON、菜单、评论）

def find_key(data, target):
    """在任意嵌套的字典/列表中查找某个 key"""
    if isinstance(data, dict):
        for key, value in data.items():
            if key == target:
                return value
            result = find_key(value, target)
            if result is not None:
                return result
    elif isinstance(data, list):
        for item in data:
            result = find_key(item, target)
            if result is not None:
                return result
    return None

多级菜单、无限层级的评论回复、JSON 数据解析——这些"不知道嵌套多深"的场景，递归是首选。

7.4 其他典型场景

• 分治算法：快速排序、归并排序（把大问题切成小问题，分别解决再合并）；
• 回溯算法：走迷宫、数独求解、八皇后问题；
• 树的遍历：文件系统、组织结构图、HTML/XML 文档解析。

---

八、常见误区与避坑指南

误区 1：忘记写终止条件

# 错误示范：没有 if n == 1 的判断
def fact(n):
    return n * fact(n - 1)

后果：无限递归 → RecursionError。写递归第一件事永远是先写终止条件。

误区 2：递归时问题规模没有缩小

# 错误示范：传入的还是 n，永远到不了 1
def fact(n):
    if n == 1:
        return 1
    return n * fact(n)     # 应该是 fact(n - 1)

后果：同样是无限递归。检查每次调用是否让参数朝终止条件靠近了一步。

误区 3：return 语句写漏或写错位置

# 错误示范：缩进错误，return 被放进了 if 里面
def fact(n):
    if n == 1:
        return 1
        return n * fact(n - 1)   # 永远执行不到！

递归逻辑对缩进极其敏感，写完务必用 fact(1)、fact(2) 这种小输入先测试。

误区 4：盲目信任尾递归能救场

如前文所述，Python 不做尾递归优化。别花时间把递归改成尾递归形式指望它防溢出——深度大的问题直接改循环。

误区 5：在递归中使用可变默认参数

# 危险写法
def collect(n, result=[]):
    if n == 0:
        return result
    result.append(n)
    return collect(n - 1, result)

Python 的默认参数只在函数定义时创建一次，多次调用之间会共享同一个列表，导致结果意外累积。安全写法是默认用 None 再在函数内初始化。

误区 6：深度预估不足

树形结构的深度有时出乎意料。比如处理文件系统时，遇到符号链接循环（A 文件夹里有个链接指回 A 的父目录），递归会无限深入。健壮的做法是加一个深度参数，超过阈值就停止。

---

九、动手练习

1. 基础题：编写递归函数 sum_list(lst)，不用内置 sum()，计算列表 [1, 2, 3, 4, 5] 的总和。
2. 进阶题：编写递归函数 reverse_string(s)，将字符串 "hello" 反转为 "olleh"（提示：终止条件是空字符串或单字符）。
3. 挑战题：完善本文的汉诺塔代码，让它同时统计并打印总移动次数，然后验证 n=10 时是否是 1023 次（2¹⁰ - 1）。
4. 思考题：为什么斐波那契的朴素递归写法慢得离谱？试着给 fib 函数加上 @functools.lru_cache() 装饰器，对比 fib(35) 的运行时间。

---

小结

• 递归函数：在函数内部调用自身的函数，核心思想是"大事化小，小事化了"。
• 三大要素：终止条件、递归调用、问题规模缩小——缺一不可。
• 优点：定义简单，逻辑清晰，尤其适合树形结构和分治类问题，代码往往比循环优雅得多。
• 缺点：每次调用占用一个栈帧，递归过深会导致栈溢出（Python 默认限制约 1000 层）。
• 尾递归：理论上可以优化成不占栈空间的形式，效果等价于循环；但 Python 解释器不做尾递归优化，任何递归函数都存在栈溢出风险，深度大的场景请改用循环。
• 实战心法：写递归时不要去脑补每一层的细节，只要确保"终止条件正确 + 每一步问题在变小"，然后信任递归。