教程

5.4 递归函数 ​

任务管理器支持子任务，子任务还能有自己的子任务，形成多层嵌套结构。要统计一个任务及其所有后代任务的总耗时，用循环一层层展开会非常繁琐，因为你不知道嵌套有多深。这种结构天然适合用递归来处理：统计一个任务的总耗时，等于它自身的耗时加上所有子任务的总耗时，而每个子任务的总耗时用同样的方法计算。递归就是函数调用自身，把一个大问题拆解成同类型的较小问题。本节讲解递归的构成要素、终止条件、深度限制、递归与迭代的对比，以及用缓存优化递归的方法。

5.4.1 递归的定义 ​

递归是指函数在执行过程中调用自身。一个递归函数通常把问题分解为一个或多个规模更小的同类子问题，通过调用自身来解决这些子问题，再把结果组合起来。递归是一种自然的思考方式，特别适合处理具有自相似结构的问题，如树形数据、分治算法等。

python
def countdown(n):
    print(n)
    if n > 0:
        countdown(n - 1)

countdown(3)

输出如下。

3
2
1
0

countdown(3) 打印 3，然后调用 countdown(2)，后者打印 2 再调用 countdown(1)，依此类推，直到 countdown(0) 打印 0 后不再递归。这就是递归的基本形式：函数调用自身处理更小的输入。

5.4.2 递归的两个要素 ​

一个正确的递归函数必须包含两个要素：递推关系和终止条件。递推关系描述如何把原问题分解为子问题，即函数在什么情况下调用自身。终止条件描述最小的问题如何直接求解，即函数在什么情况下不再递归而直接返回。缺少终止条件的递归会无限调用自身，直到触发深度限制。

python
def factorial(n):
    if n <= 1:       # 终止条件
        return 1
    return n * factorial(n - 1)  # 递推关系

print(factorial(5))  # 120

阶乘的数学定义是 n! = n * (n-1)!，当 n 为 0 或 1 时 n! = 1。if n <= 1: return 1 是终止条件，对应最小情况的直接答案。return n * factorial(n - 1) 是递推关系，把 n! 转化为 n * (n-1)!。每次递归调用 n 都比原来小 1，最终会到达终止条件 n <= 1，递归开始逐层返回。

理解递归执行过程的一个有效方式是画出调用栈。factorial(5) 的调用过程是：factorial(5) 调用 factorial(4)，factorial(4) 调用 factorial(3)，一直到 factorial(1) 返回 1。然后逐层返回：factorial(2) 返回 2*1=2，factorial(3) 返回 3*2=6，factorial(4) 返回 4*6=24，factorial(5) 返回 5*24=120。

5.4.3 终止条件的重要性 ​

终止条件是递归能够结束的关键。如果终止条件写错或遗漏，递归会一直进行下去，直到 Python 的调用栈溢出，抛出 RecursionError。每个递归调用都会在内存中创建一个新的栈帧，栈深度有限，不能无限增长。

python
def bad_recursion(n):
    return n * bad_recursion(n - 1)  # 没有终止条件

bad_recursion(5)  # 最终报 RecursionError

这段代码没有终止条件，bad_recursion 会不断调用自身，n 一直减小却永远没有返回的出口，最终触发递归深度限制。编写递归函数时，第一步就应想清楚终止条件是什么，确保所有递归路径最终都能到达它。

5.4.4 斐波那契数列递归实现 ​

斐波那契数列是经典的递归例子。数列定义为 F(n) = F(n-1) + F(n-2)，其中 F(0)=0，F(1)=1。这个定义本身就是递归的，直接翻译成代码很自然。

python
def fib(n):
    if n < 2:        # 终止条件：F(0)=0, F(1)=1
        return n
    return fib(n - 1) + fib(n - 2)  # 递推关系

print(fib(10))  # 55

fib(10) 返回 55，结果是正确的。但这种朴素递归实现有一个严重问题：存在大量重复计算。计算 fib(5) 需要计算 fib(4) 和 fib(3)，计算 fib(4) 又需要 fib(3) 和 fib(2)，fib(3) 被计算了两次。随着 n 增大，重复计算呈指数级增长，fib(40) 就已经非常慢了。

5.4.5 递归深度限制 ​

Python 对递归深度有默认限制，防止栈溢出导致程序崩溃。可以用 sys.getrecursionlimit() 查看当前限制，用 sys.setrecursionlimit() 调整。默认值通常是 1000。

python
import sys

print(sys.getrecursionlimit())  # 1000（默认值）

def deep(n):
    if n == 0:
        return 0
    return deep(n - 1)

print(deep(900))   # 0，正常
print(deep(2000))  # 报 RecursionError

当递归深度超过限制时，Python 抛出 RecursionError。虽然可以用 sys.setrecursionlimit() 提高上限，但过深的递归会消耗大量栈空间，可能导致解释器崩溃。如果一个问题需要很深的递归，通常说明应该改用迭代方式实现。

5.4.6 递归与迭代的对比 ​

任何递归都可以用迭代（循环）来实现，反之亦然。递归的优势在于代码与问题的数学定义高度吻合，可读性强，特别适合树形结构和分治问题。递归的劣势是函数调用有开销，且受深度限制，还可能有重复计算。迭代的优势是效率高、没有深度限制，劣势是对于某些问题代码会比递归复杂得多。

阶乘的迭代实现非常简单，用循环累乘即可。

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

print(factorial_iter(5))  # 120

迭代版本没有函数调用开销，也不会有深度限制问题，对于阶乘这种线性递归，迭代实现明显更优。但对于树形遍历这类问题，递归代码往往比迭代代码简洁得多，迭代实现需要手动维护一个栈来模拟递归过程。选择递归还是迭代，要看具体问题的结构和对性能的要求。

5.4.7 Python 不支持尾递归优化 ​

有些编程语言支持尾递归优化，当递归调用是函数的最后一步操作时，编译器复用当前栈帧而不新建，从而避免栈溢出。Python 不支持尾递归优化，即使写成尾递归形式，每次调用仍会新建栈帧，深度限制依然存在。因此在 Python 中，需要很深递归的问题应该转换为迭代实现。

5.4.8 用 lru_cache 优化递归 ​

对于斐波那契这种存在大量重复计算的递归，可以用 functools.lru_cache 装饰器缓存已计算的结果。下次遇到相同参数时直接返回缓存值，避免重复计算。lru 是 Least Recently Used 的缩写，表示缓存满了时淘汰最久未使用的结果。

python
from functools import lru_cache

@lru_cache
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(50))  # 12586269025，瞬间完成

加上 @lru_cache 后，每个 n 只计算一次，后续调用直接取缓存。fib(50) 在朴素递归下几乎无法完成，加了缓存后瞬间返回。lru_cache 默认缓存 128 个结果，可以通过 @lru_cache(maxsize=...) 调整。被缓存的函数参数必须是可哈希的，因为缓存以参数为键。

lru_cache 是优化递归的简单手段，但它是用空间换时间。如果参数范围很大，缓存会占用较多内存。对于斐波那契这类问题，缓存效果极佳，因为参数就是整数，且范围有限。

5.4.9 嵌套子任务总耗时的递归实现 ​

回到本节开头的问题：任务管理器中每个任务可以有子任务，子任务还可以有子任务，要计算一个任务及其所有后代任务的总耗时。这种树形结构是递归的典型应用场景。

python
def total_time(task):
    # task 是字典，包含 time 字段和可选的 children 列表
    total = task.get("time", 0)
    for child in task.get("children", []):
        total += total_time(child)
    return total

task = {
    "title": "完成项目",
    "time": 2,
    "children": [
        {"title": "写报告", "time": 3, "children": [
            {"title": "收集资料", "time": 2},
            {"title": "撰写正文", "time": 4},
        ]},
        {"title": "评审", "time": 1, "children": [
            {"title": "内部评审", "time": 1},
        ]},
    ]
}

print(total_time(task))  # 13

total_time 计算逻辑是：当前任务的耗时加上所有子任务的总耗时。每个子任务的总耗时又用 total_time 计算，这就是递推关系。终止条件是任务没有 children，此时循环不执行，直接返回自身的 time。

计算过程：最底层的 收集资料 耗时 2、撰写正文 耗时 4，所以 写报告 子树总耗时是 3 + 2 + 4 = 9。内部评审 耗时 1，评审 子树总耗时是 1 + 1 = 2。根任务 完成项目 自身耗时 2，加上两个子树的 9 和 2，总计 13。

这种树形遍历如果用迭代实现，需要手动维护一个栈来模拟递归调用，代码会复杂得多。递归让代码结构与数据结构高度吻合，这是递归最大的价值所在。

递归适用场景

递归适合处理具有自相似结构的问题，如树形数据遍历、分治算法、回溯问题。对于线性问题（如阶乘、累加），迭代实现通常更好。遇到性能瓶颈时，先考虑用 lru_cache 消除重复计算，再考虑改写为迭代。

练习题 ​

练习 1 用递归实现一个函数 sum_list(numbers)，计算列表中所有数字的和。写出终止条件和递推关系。

参考答案
python
def sum_list(numbers):
    if not numbers:        # 终止条件：空列表和为 0
        return 0
    return numbers[0] + sum_list(numbers[1:])  # 递推关系：第一个元素加剩余元素的和

print(sum_list([1, 2, 3, 4, 5]))  # 15

终止条件是列表为空时返回 0。递推关系是 第一个元素 + 剩余列表的和。numbers[1:] 每次切掉第一个元素，列表逐渐变短，最终到达空列表。

注意 numbers[1:] 每次创建新列表，效率不高，这里仅作递归练习。实际求和应直接用内置函数 sum(numbers)。

练习 2 斐波那契的朴素递归实现计算 fib(35) 会非常慢，原因是大量重复计算。请用 lru_cache 优化它，并对比优化前后是否能快速得到 fib(35) 的结果。

参考答案
python
from functools import lru_cache

@lru_cache
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(35))  # 9227465，加了缓存后瞬间完成

朴素递归计算 fib(35) 需要数千万次函数调用，因为 fib(3)、fib(2) 等被反复计算。加上 lru_cache 后，每个参数值只计算一次并缓存，fib(35) 只需约 35 次计算，瞬间返回。

如果想验证缓存效果，可以在函数体内加一行 print(f"计算 fib({n})")，对比有无缓存时打印次数的差异。

练习 3 以下递归函数用于计算列表的最大深度（嵌套列表的层数），但有错误会导致无法正确终止或结果错误。请找出问题并修正。例如 depth([1, [2, [3]]]) 应返回 3。

python
def depth(lst):
    return 1 + max(depth(item) for item in lst)
参考答案

问题在于缺少终止条件。当 lst 是空列表或全部是非列表元素时，生成器为空，max() 会报 ValueError。同时当列表中没有嵌套列表时，应该返回 1。

修正方式是加终止条件。

python
def depth(lst):
    if not isinstance(lst, list):
        return 0
    if not lst:  # 空列表深度为 1
        return 1
    return 1 + max(depth(item) for item in lst)

print(depth([1, [2, [3]]]))  # 3
print(depth([]))             # 1
print(depth(5))              # 0，非列表

终止条件有两部分：元素不是列表时返回 0（不增加深度），空列表返回 1。递推关系是当前层数 1 加上所有子元素深度的最大值。isinstance 判断确保遇到非列表元素时停止递归。

练习 4 任务管理器中任务以嵌套字典表示，每个任务有 title 字段和可选的 children 列表。请用递归编写函数 count_all_tasks(task)，统计一个任务及其所有后代任务的总数量（包括它自身）。

参考答案
python
def count_all_tasks(task):
    count = 1  # 当前任务自身
    for child in task.get("children", []):
        count += count_all_tasks(child)
    return count

task = {
    "title": "项目",
    "children": [
        {"title": "设计", "children": [
            {"title": "UI 设计"},
            {"title": "数据库设计"},
        ]},
        {"title": "开发", "children": [
            {"title": "前端"},
        ]},
    ]
}

print(count_all_tasks(task))  # 6

终止条件是任务没有 children，此时循环不执行，返回 1。递推关系是当前任务数量 1 加上所有子任务的 count_all_tasks 之和。这与 total_time 的结构完全一致，递归处理树形数据时这种模式非常通用：累加自身，再遍历子节点递归累加。

统计过程：UI 设计、数据库设计、前端 各 1 个，设计 子树 3 个（含自身），开发 子树 2 个，根任务 1 个加 3 加 2，共 6 个。

常见错误 ​

错误 1 · RecursionError: maximum recursion depth exceeded

原因：递归函数缺少终止条件，或终止条件永远无法到达。例如终止条件写成 if n == 0: 但参数以负数递减，永远到不了 0；或忘了写 return，递归调用结果未传出。

解决：检查终止条件是否覆盖所有递归路径，确保每次递归调用都让问题规模严格缩小并最终命中终止条件。先用最小输入手动模拟一遍执行过程验证。

错误 2 · TypeError: depth() missing 1 required positional argument: 'lst' 或递归调用参数不全

原因：递归调用自身时漏传参数，或终止条件分支只 return 不带值导致后续运算类型错乱。常见于递归调用写成 func() 不带参数，或终止分支 return 后外层用 1 + func(...) 拼接。

解决：递归调用时的参数列表要与定义一致。终止分支应返回明确的值，不要单独 return 让默认 None 参与运算。

错误 3 · 朴素斐波那契递归计算 fib(40) 长时间无响应

现象：fib(40) 等较大输入下程序极慢，但小输入结果正确。

原因：朴素递归存在大量重复计算，fib(n-1) 和 fib(n-2) 各自又重复计算更小的子问题，调用次数呈指数增长。

解决：用 functools.lru_cache 装饰器缓存已计算结果，或改用迭代实现从底向上累加。

错误 4 · ValueError: max() arg is an empty sequence

原因：递归生成器在终止条件下为空，再对空序列调用 max() 或 min() 触发报错。常见于树形递归遍历叶子节点时未处理空列表情况。

解决：在递归函数开头加终止条件判断，遇到空序列或非列表元素时直接返回固定值，避免对空可迭代对象调用聚合函数。