跳到主要内容

递归函数

递归是函数直接或间接调用自身来解决问题的方法。它适合处理能够不断缩小、并且结构本身具有层级的问题，例如目录树、组织结构、嵌套数据和分治算法。

本文使用 Python 3.10 及以上版本。读完后，你应该能够：

  • 写出包含终止条件和递归步骤的函数；
  • 跟踪递归调用栈与返回过程；
  • 识别无限递归、重复计算和栈深度风险；
  • 判断何时应改用循环、缓存或显式栈。

一个最小递归函数​

下面的函数从指定数字倒数到 1：

def countdown(number):
    if number <= 0:
        print("结束")
        return

    print(number)
    countdown(number - 1)


countdown(3)

输出结果：

3
2
1
结束

递归函数通常由两部分组成：

  1. 终止条件：问题已经足够简单，直接返回结果，不再继续调用；
  2. 递归步骤：把当前问题缩小，再调用自身处理更小的问题。

这里的终止条件是 number <= 0，递归步骤是 countdown(number - 1)。如果输入没有持续靠近终止条件，递归就不会正常结束。

递归如何执行​

以阶乘为例。正整数 n 的阶乘可以写成：

n! = n * (n - 1)!
0! = 1

对应的函数如下：

def factorial(number):
    if number == 0:
        return 1
    return number * factorial(number - 1)


print(factorial(4)) # 24

调用 factorial(4) 时，计算先逐层展开：

factorial(4)
4 * factorial(3)
4 * 3 * factorial(2)
4 * 3 * 2 * factorial(1)
4 * 3 * 2 * 1 * factorial(0)

到达 factorial(0) 后，再从最内层逐层返回：

factorial(0) -> 1
factorial(1) -> 1 * 1
factorial(2) -> 2 * 1
factorial(3) -> 3 * 2
factorial(4) -> 4 * 6

最终得到 24。理解“先深入、后返回”是读懂递归的关键。

调用栈​

每次函数调用都需要保存本次调用的参数、局部变量和返回位置，这些信息组成一个栈帧。递归调用会不断把新栈帧压入调用栈，返回时再按后进先出的顺序移除。

因此递归不是没有成本的循环。递归过深会占用大量栈空间，并最终触发 RecursionError：

def never_end(number):
    return never_end(number + 1)


# never_end(0) # RecursionError: maximum recursion depth exceeded

Python 设置递归深度限制是为了避免解释器栈无限增长。可以通过 sys.getrecursionlimit() 查看当前限制，但不应把提高限制当作默认解决方案，因为系统栈仍然有限。

写递归函数的四个步骤​

面对一个递归问题，可以按下面的顺序设计：

  1. 明确函数对一个输入应该返回什么；
  2. 找到无需继续拆分的最小问题；
  3. 把大问题缩小为同类的小问题；
  4. 使用小问题的结果组合出当前结果。

例如计算列表中所有数字的和：

def recursive_sum(numbers):
    if not numbers:
        return 0
    return numbers[0] + recursive_sum(numbers[1:])


print(recursive_sum([2, 4, 6])) # 12

空列表是最小问题，其总和为 0；非空列表的结果等于“第一个元素 + 剩余列表的总和”。

这个写法每次切片都会创建新列表，适合教学但不适合大型数据。实际代码可以传递索引，或直接使用内置的 sum()。

先验证输入边界​

前面的阶乘函数没有处理负数。负数会一直递减，永远到不了 0：

def factorial(number):
    if not isinstance(number, int):
        raise TypeError("number 必须是整数")
    if number < 0:
        raise ValueError("number 不能是负数")
    if number == 0:
        return 1
    return number * factorial(number - 1)

终止条件不仅要存在，还要覆盖所有合法输入；非法输入则应在递归开始前尽早拒绝。

若不希望每层递归都重复校验，可以用外层函数负责校验，内部函数负责递归：

def factorial(number):
    if not isinstance(number, int):
        raise TypeError("number 必须是整数")
    if number < 0:
        raise ValueError("number 不能是负数")

    def calculate(current):
        if current == 0:
            return 1
        return current * calculate(current - 1)

    return calculate(number)

递归处理嵌套结构​

递归特别适合层级数量不固定的数据。下面的函数计算任意嵌套列表中的数字总和：

def nested_sum(value):
    if isinstance(value, int | float):
        return value
    if isinstance(value, list):
        return sum(nested_sum(item) for item in value)
    raise TypeError("只支持数字和列表")


data = [1, [2, 3], [4, [5]]]
print(nested_sum(data)) # 15

每个值只有两种情况：数字可以直接返回，列表则递归处理其中的每个元素。这种写法能自然对应数据结构。

递归遍历树​

文件目录、菜单和评论回复都可以看作树。树节点通常包含自身数据与若干子节点：

tree = {
    "name": "根目录",
    "children": [
        {"name": "docs", "children": []},
        {
            "name": "src",
            "children": [
                {"name": "main.py", "children": []},
            ],
        },
    ],
}


def print_tree(node, depth=0):
    print("  " * depth + node["name"])
    for child in node["children"]:
        print_tree(child, depth + 1)


print_tree(tree)

输出中的缩进反映节点深度。递归函数不需要预先知道树有多少层，只需处理“当前节点”和“它的子节点”。

分治：二分查找​

分治算法把问题拆成更小的一部分。下面用递归在有序列表中查找目标：

def binary_search(numbers, target, left=0, right=None):
    if right is None:
        right = len(numbers) - 1

    if left > right:
        return -1

    middle = (left + right) // 2
    current = numbers[middle]

    if current == target:
        return middle
    if target < current:
        return binary_search(numbers, target, left, middle - 1)
    return binary_search(numbers, target, middle + 1, right)


values = [2, 5, 8, 12, 16]
print(binary_search(values, 12)) # 3

每次调用都把搜索范围缩小约一半。输入必须已经排序，否则算法的判断依据不成立。

重复计算与缓存​

朴素的斐波那契递归会反复计算相同子问题：

def fibonacci(number):
    if number < 2:
        return number
    return fibonacci(number - 1) + fibonacci(number - 2)

例如计算 fibonacci(5) 时，fibonacci(3)、fibonacci(2) 会被多次调用，耗时会随输入快速增长。

可以用 functools.cache 保存已经计算过的结果：

from functools import cache


@cache
def fibonacci(number):
    if number < 0:
        raise ValueError("number 不能是负数")
    if number < 2:
        return number
    return fibonacci(number - 1) + fibonacci(number - 2)


print(fibonacci(40)) # 102334155

缓存适合“相同输入总是得到相同结果”的函数。参数必须可以哈希；缓存也会占用内存，不适合无限增长或依赖外部状态的输入。

斐波那契数列用循环通常更加直接，并且不会受递归深度限制：

def fibonacci(number):
    if number < 0:
        raise ValueError("number 不能是负数")

    previous, current = 0, 1
    for _ in range(number):
        previous, current = current, previous + current
    return previous

图结构要防止循环引用​

树不会回到已经访问过的父节点，但一般的图可能包含环。递归遍历图时要记录已访问节点，否则会无限循环：

graph = {
    "A": ["B"],
    "B": ["C"],
    "C": ["A"],
}


def visit(node, visited=None):
    if visited is None:
        visited = set()
    if node in visited:
        return

    visited.add(node)
    print(node)

    for neighbor in graph.get(node, []):
        visit(neighbor, visited)


visit("A")

这里使用 None 创建每次顶层调用独立的集合，避免可变默认参数在多次调用间共享状态。

直接递归与间接递归​

函数调用自身称为直接递归。函数 A 调用函数 B，而函数 B 又调用函数 A，称为间接递归：

def is_even(number):
    if number == 0:
        return True
    return is_odd(number - 1)


def is_odd(number):
    if number == 0:
        return False
    return is_even(number - 1)

间接递归更难跟踪，仍然必须保证输入持续靠近共同的终止条件。上例只是演示机制，实际判断奇偶应直接使用 % 2。

尾递归在 Python 中不会自动优化​

如果递归调用是函数返回前的最后一步，就称为尾递归：

def factorial_tail(number, result=1):
    if number == 0:
        return result
    return factorial_tail(number - 1, result * number)

有些语言会复用尾递归的栈帧，但 Python 不保证尾调用优化。这个函数仍会逐层增加调用栈，输入很大时仍可能产生 RecursionError，因此不要把尾递归当作突破深度限制的方法。

递归与循环如何选择​

场景通常更合适的方式
遍历树、嵌套结构递归通常更贴合结构
重复固定次数for 循环
状态逐步更新直到满足条件while 循环
数据层级可能很深且不可控循环配合显式栈或队列
子问题会大量重复缓存、动态规划或循环
分治后自然组合结果递归

递归并不天然比循环高级。优先选择能清楚表达问题、不会造成深度风险且性能足够的写法。

用显式栈替代深递归​

层级可能非常深时，可以自己维护列表作为栈：

def print_tree_iterative(root):
    stack = [(root, 0)]

    while stack:
        node, depth = stack.pop()
        print("  " * depth + node["name"])

        for child in reversed(node["children"]):
            stack.append((child, depth + 1))

显式栈使用堆内存，不受 Python 调用栈深度的同一限制，也更容易暂停或控制遍历过程。

调试递归函数​

遇到结果错误时，可以记录输入和深度：

def factorial(number, depth=0):
    print(f"{'  ' * depth}进入 factorial({number})")

    if number == 0:
        result = 1
    else:
        result = number * factorial(number - 1, depth + 1)

    print(f"{'  ' * depth}返回 {result}")
    return result

测试时至少覆盖：

  • 最小合法输入，也就是终止条件；
  • 比终止条件大一步的输入；
  • 一个普通输入；
  • 空结构、负数或错误类型等边界输入；
  • 足以暴露性能或深度问题的较大输入。

常见错误​

没有终止条件​

函数会一直调用自身，直到触发 RecursionError。

输入没有靠近终止条件​

例如目标是到达 0，却错误地让正数不断增加。每条递归路径都必须向可结束的状态推进。

忘记返回递归结果​

def factorial(number):
    if number == 0:
        return 1
    factorial(number - 1) # 忘记 return 和当前层计算

此时外层调用会得到 None。要明确当前层如何使用并返回子问题结果。

在递归过程中反复复制大对象​

列表切片、字符串拼接等操作可能让代码产生大量临时对象。可以传递索引、使用共享结果容器，或改为迭代实现。

为普通循环强行使用递归​

对简单计数、求和等线性任务，循环通常更快、更直观，也没有调用栈限制。

练习​

  1. 编写递归函数，计算 1 + 2 + ... + n，并处理 n = 0 和负数。
  2. 编写递归函数，反转一个字符串；再比较切片写法与索引写法的开销。
  3. 统计嵌套列表中所有非列表元素的数量。
  4. 为朴素斐波那契函数添加缓存，并比较较大输入的运行时间。
  5. 使用递归遍历目录树，再用显式栈实现同样功能。

小结​

  • 递归函数必须同时具备终止条件和让问题不断缩小的递归步骤。
  • 调用会先逐层深入，再沿调用栈逐层返回；每层都会占用栈空间。
  • 树、嵌套结构和分治问题通常适合递归，简单线性任务通常更适合循环。
  • 重复子问题可以用缓存减少计算；图结构需要记录已访问节点以避免环。
  • Python 不保证尾调用优化，深度不可控时应使用循环或显式栈。
  • 边界验证、返回值和性能测试是保证递归函数正确性的关键。