递归详解：原理与 Python 示例

递归解决什么问题

有些问题本身就是用自身来定义的。文件夹里有文件，也有其他文件夹；树节点有子树；n 的阶乘等于 n 乘以 n − 1 的阶乘。用普通循环来写这些问题，往往需要手动维护一个存放待处理任务的栈；递归则让语言替你保管这个栈。

递归函数由两部分组成：

• 基准情形：最小的输入，直接给出答案。对阶乘来说，0! = 1。
• 递归情形：缩小问题，对更小的部分调用函数，再合并结果。对阶乘来说，n! = n × (n − 1)!。

def factorial(n):
    if n == 0:                  # base case
        return 1
    return n * factorial(n - 1) # recursive case
print(factorial(5))   # 120

逐步追踪调用栈

每次调用都会在调用栈上获得自己的栈帧，其中保存着自己那份 n。调用一路向下直到基准情形，然后结果按相反的顺序逐层返回。

这里的栈深度是 n + 1 个栈帧，所以即使没有创建任何列表，额外空间也是 O(n)。

对嵌套数据的递归

当数据本身的结构就是递归的，递归最能发挥作用。下面的函数对一个可能包含其他列表（任意深度）的列表求和。

def deep_sum(items):
    total = 0
    for x in items:
        if isinstance(x, list):
            total += deep_sum(x)   # same problem, smaller piece
        else:
            total += x
    return total
print(deep_sum([1, [2, 3], [4, [5, [6]]]]))   # 21

同样的模式也可用来遍历目录树、JSON 文档、HTML DOM 或二叉树：先处理当前节点，再递归处理每个子节点。

def power_set(items):
    if not items:
        return [[]]
    rest = power_set(items[1:])
    return rest + [[items[0]] + s for s in rest]
print(power_set([1, 2, 3]))
# [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

递归函数的复杂度

代价可以估算为（调用次数）×（每次调用的工作量）。空间复杂度至少等于最大栈深度。

分治类的递推式，例如归并排序的 T(n) = 2T(n/2) + O(n)，解得 O(n log n)。而对 n − 1 做两次调用的函数则呈指数级增长。

记忆化：避免重复计算

朴素的斐波那契函数会把相同的值重复计算很多次：fib(5) 会调用两次 fib(3)、三次 fib(2)。把每个结果在首次算出时缓存起来，就能把指数时间变成线性时间。Python 的 functools.lru_cache（或 Python 3.9+ 的 functools.cache）只需一个装饰器就能做到。

from functools import lru_cache
def fib_slow(n):
    return n if n < 2 else fib_slow(n - 1) + fib_slow(n - 2)
@lru_cache(maxsize=None)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)
print(fib_slow(20))   # 6765, about 22,000 calls
print(fib(90))        # 2880067194370816120, 91 distinct calls

带记忆化的递归是动态规划的自顶向下形式；自底向上的形式则是用循环去填表。

递归深度限制与改写为循环

可以用 sys.setrecursionlimit() 调高上限，但过深的递归仍可能让解释器崩溃。对于可能很深的输入，例如一百万个节点的链表或退化的树，请改用循环加显式栈来重写。

def deep_sum_iter(items):
    total, stack = 0, [items]
    while stack:
        current = stack.pop()
        for x in current:
            if isinstance(x, list):
                stack.append(x)
            else:
                total += x
    return total
print(deep_sum_iter([1, [2, 3], [4, [5, [6]]]]))   # 21

常见误区

• 缺少基准情形，或基准情形永远到不了。例如用上面的代码调用 factorial(-1)，永远不会到达 0，最终以 RecursionError 结束。
• 递归情形没有缩小输入，比如在 f(n) 里又调用 f(n)。
• 忘记 return 递归的结果：写成 factorial(n - 1) 而不加 return，得到的是 None。
• 每次调用都复制数据。items[1:] 会复制列表，因此在长列表的切片上递归，时间是 O(n²)；应改为传递下标。
• 用可变默认参数（如 def f(x, seen=[])）在多次调用之间传递状态；该函数的每次调用都共享同一个列表。

何时使用递归

当数据或问题天然具有递归结构时使用递归：树、图（深度优先搜索）、嵌套结构、表达式解析、回溯（排列、N 皇后、数独），以及分治（归并排序、快速排序、二分查找）。如果问题只是简单的序列，或者在 Python 中递归深度会随输入规模增长，就用循环。

面试中，递归题常考察你能否说清基准情形、递归情形、包含栈在内的时间与空间代价，以及记忆化在什么情况下有用。