引言
这是第四章「函数」的第 6 篇，也是函数专题的收官之作。第 1 篇你学会了用 def 定义函数，第 2 篇搞清楚了作用域如何决定变量可见性，第 3 篇掌握了 *args / **kwargs 处理不确定参数，第 4 篇学习了 lambda 表达式，第 5 篇理解了装饰器如何包裹函数。现在，我们把目光转向函数的一个特殊能力：函数可以调用自己——这就是递归（recursion）。
递归是计算机科学中最核心的思想之一。它不仅仅是一种编程技巧，更是一种问题分解的策略：把一个复杂问题拆解成结构相同但规模更小的子问题，直到子问题小到可以直接求解。递归在算法设计（分治法、动态规划的记忆化搜索）、数据结构遍历（树的深度优先搜索）、数学证明（数学归纳法）中无处不在。
本篇先讲递归的三个必要组成部分（基线条件、递归步骤、终止保证），然后用 Python 的运行机制作解释递归背后的「栈帧」机制，接着对比递归和迭代在 Fibonacci 数列上的性能差异，再介绍回溯算法框架（全排列、迷宫求解），最后讨论尾递归和 Python 为何不支持尾递归优化（TCO）。读完本篇，你将能正确编写递归函数，并知道何时该用递归、何时该改用迭代。
概念与原理
递归的三要素
任何一个正确的递归函数都必须满足三个条件，缺一不可：
1. 基线条件（base case）
基线条件是递归停止的条件，也就是最简单、不需要再拆分的问题。没有基线条件的递归会无限进行下去，最终导致 RecursionError。
以计算阶乘为例，0! = 1 就是基线条件——当 n == 0 时直接返回 1，不再递归。
2. 递归步骤（recursive case）
递归步骤是把当前问题转化为规模更小的同类问题。每次递归调用都应该让问题的规模向基线条件靠近，而不是远离或保持不变。
在阶乘中，n! = n * (n-1)! 就是递归步骤——把 n! 转化为 (n-1)! 乘以 n，规模减小了 1。
3. 终止保证（termination guarantee）
必须保证无论传入什么合法输入，递归都最终会到达基线条件。这需要从数学上论证（归纳法）或从逻辑上验证。
在阶乘中，由于每次调用 n 严格递减，且 n >= 0 时最终会到达 n == 0，所以终止是有保证的。但如果调用方传入了负数，递归就会永远无法到达基线条件——这是一个典型的终止保证漏洞。
def factorial(n):
if n < 0:
raise ValueError("n must be non-negative")
if n == 0:
return 1
return n * factorial(n - 1)调用栈与栈帧
理解递归的关键是理解 Python 的调用栈（call stack）。每当函数被调用时，Python 会在内存中创建一个栈帧（stack frame），用于保存该次调用的局部变量、参数和返回地址。栈帧按照「后进先出」（LIFO）的方式组织，最新调用的函数对应的栈帧在最上面。
以 factorial(3) 为例，调用过程如下：
factorial(3)
→ factorial(2)
→ factorial(1)
→ factorial(0) ← 到达基线条件，返回 1
← factorial(1) 返回 1 * 1 = 1
← factorial(2) 返回 2 * 1 = 2
← factorial(3) 返回 3 * 2 = 6
每一层递归调用都会在调用栈上压入一个新帧，直到基线条件触发后，帧逐层弹出，返回值逐层传递回来。调用栈的总深度决定了递归的最大允许深度——这也是 Python 设置递归限制的原因。
可以用以下代码观察递归过程中的调用栈：
import sys
def observe_depth(n):
print(f" " * (sys.getrecursionlimit() - n) + f"depth={n}, n={n}")
if n == 0:
return 1
result = n * observe_depth(n - 1)
print(f" " * (sys.getrecursionlimit() - n) + f"return {result} from depth={n}")
return result
observe_depth(5)输出会显示调用深度从 0 到 5 的增长，以及返回值从内到外的传递。这种可视化有助于建立对调用栈的直观理解。
操作与实现
递归 vs 迭代：Fibonacci 对比
Fibonacci 数列是最经典的递归教学案例，但它同时也是递归性能问题的典型反面教材：
def fib_recursive(n):
"""纯递归版本"""
if n <= 1:
return n
return fib_recursive(n - 1) + fib_recursive(n - 2)
def fib_iterative(n):
"""迭代版本"""
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b两段代码逻辑上计算的是同一个数列，但性能差异巨大：
import time
n = 30
start = time.time()
r1 = fib_recursive(n)
t1 = time.time() - start
start = time.time()
r2 = fib_iterative(n)
t2 = time.time() - start
print(f"recursive fib({n})={r1}, time={t1:.4f}s")
# recursive fib(30)=832040, time=0.1100s
print(f"iterative fib({n})={r2}, time={t2:.6f}s")
# iterative fib(30)=832040, time=0.000000s
print(f"match: {r1 == r2}") # True在我的环境中，fib_recursive(30) 耗时约 0.11 秒，而 fib_iterative(30) 接近瞬间完成（微秒级）。原因在于纯递归版本存在大量重复计算——fib(30) 需要计算 fib(29) 和 fib(28)，而 fib(29) 又需要计算 fib(28) 和 fib(27)，fib(28) 被重复计算了两次。这个时间复杂度是指数级的 O(2^n)。
用 functools.lru_cache 给递归版本加上记忆化（memoization）后，复杂度降为 O(n)：
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n):
if n <= 1:
return n
return fib_memo(n - 1) + fib_memo(n - 2)
print(fib_memo(30)) # 832040
print(fib_memo.cache_info())
# CacheInfo(hits=28, misses=31, maxsize=None, currsize=31)hits=28 说明有 28 次调用直接命中缓存，只花了 31 次实际计算就得到了结果。这是递归+缓存的典型用法。
回溯算法框架
回溯（backtracking）是一种基于递归的穷举搜索策略，核心思想是：尝试一个选择，递归求解，如果走不通则退回（回溯）上一步，尝试另一个选择。回溯的经典应用是全排列和迷宫求解。
全排列
给定一个列表，生成其所有可能的排列：
def permute(nums):
result = []
def backtrack(start):
if start == len(nums):
result.append(nums[:]) # 保存副本，不是引用
return
for i in range(start, len(nums)):
nums[start], nums[i] = nums[i], nums[start] # 交换
backtrack(start + 1)
nums[start], nums[i] = nums[i], nums[start] # 回溯（撤销交换）
backtrack(0)
return result
print(permute([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]关键点：每次交换后递归，递归返回后再交换回来（回溯），确保下一次循环从正确的状态出发。result.append(nums[:]) 必须用切片创建副本，否则保存的只是同一对象的引用，后续修改会覆盖之前的结果。
迷宫求解
用一个二维矩阵表示迷宫，1 表示通路，0 表示墙壁：
def solve_maze(maze, x, y, solution):
n = len(maze)
# 到达右下角终点
if x == n - 1 and y == n - 1:
solution[x][y] = 1
return True
# 检查边界、是否可通行、是否已访问
if 0 <= x < n and 0 <= y < n and maze[x][y] == 1 and solution[x][y] == 0:
solution[x][y] = 1
# 尝试向下
if solve_maze(maze, x + 1, y, solution):
return True
# 尝试向右
if solve_maze(maze, x, y + 1, solution):
return True
# 两条路都走不通，回溯
solution[x][y] = 0
return False
return False
maze = [
[1, 0, 0, 0],
[1, 1, 0, 1],
[0, 1, 0, 0],
[1, 1, 1, 1]
]
solution = [[0] * 4 for _ in range(4)]
if solve_maze(maze, 0, 0, solution):
for row in solution:
print(row)
# [1, 0, 0, 0]
# [1, 1, 0, 0]
# [0, 1, 0, 0]
# [0, 1, 1, 1]这条路径从左上角 (0,0) 出发，依次经过 (1,0)、(1,1)、(2,1)、(3,1)、(3,2)、(3,3) 到达右下角终点，共 7 个格子。迷宫中用 0 标记未走过的格子，用 1 标记通路。
迷宫问题的递归框架是通用的：判断当前位置是否是目标；如果是，返回成功；如果不是，标记当前位置并尝试每个可行方向（递归），任何方向成功就返回；所有方向都失败则回溯（取消标记）并返回失败。
递归深度与 sys.getrecursionlimit
Python 对递归深度有限制，默认值是 1000：
import sys
print(sys.getrecursionlimit()) # 1000超过这个限制会抛出 RecursionError：
def count_down(n):
if n == 0:
return
count_down(n - 1)
count_down(1001) # RecursionError: maximum recursion depth exceeded可以临时修改限制（谨慎使用）：
sys.setrecursionlimit(2000)但修改限制并不能解决根本问题——它只是让你能跑到更深的递归深度，最终仍然会遇到栈溢出（segfault）的风险。在生产代码中，应该优先改写为迭代或用 lru_cache 优化，而非依赖调大递归限制。
对于需要深层递归的场景（如处理深层嵌套的数据结构），可以考虑使用显式栈模拟递归，完全避开 Python 的递归限制。
尾递归与 Python 的 TCO 缺失
尾递归（tail recursion） 是指递归调用是函数体中的最后一个操作，其结果直接作为当前函数的返回值，不需要进行任何额外的计算：
# 尾递归版本：阶乘
def factorial_tail(n, accumulator=1):
if n == 0:
return accumulator
return factorial_tail(n - 1, accumulator * n) # 递归调用是最后一步在支持**尾递归优化（Tail Call Optimization，TCO）**的语言中（如 Scheme、Rust、Erlang），编译器会将尾递归转换为等价的循环，不增加栈帧深度，从而避免栈溢出。上面这个 factorial_tail 在 Scheme 中可以安全地递归任意深度。
但 Python 不支持尾递归优化。这是 CPython 设计者的有意选择——Guido van Rossum 认为 TCO 会让调试变得困难（栈帧消失，无法查看中间状态），且不符合 Python 「可读性优先」的哲学。Python 官方文档明确说明不提供 TCO：
import sys
sys.setrecursionlimit(2000)
def factorial_tail(n, accumulator=1):
if n == 0:
return accumulator
return factorial_tail(n - 1, accumulator * n)
print(factorial_tail(1500)) # 1500! 的前几位，递归深度 1500，需要预先调大限制在 sys.setrecursionlimit(2000) 后，上述代码可以正常运行。但如果你尝试更大的深度，比如 5000，仍然会抛出 RecursionError。
Python 中没有 TCO，因此将尾递归改写为迭代是最佳实践：
def factorial_iterative(n, accumulator=1):
while n > 0:
accumulator *= n
n -= 1
return accumulator迭代版本没有递归限制，可以处理任意大的 n（受限于整数本身的大小）。
易错点与陷阱
陷阱一：忘记基线条件
最常见的递归错误是缺少基线条件，导致无限递归：
# ❌ 没有基线条件，会无限递归
def count_up(n):
print(n)
count_up(n + 1) # n 越来越大，永远无法到达基线
# ✅ 正确版本
def count_down(n):
if n <= 0:
return
print(n)
count_down(n - 1)编写递归函数时，先问自己：这个问题的最小形式是什么？什么时候可以不再拆分？把这个条件写成 if 放在函数最前面。
陷阱二：递归步骤没有向基线条件靠近
即使有基线条件，如果递归步骤没有让问题规模减小，仍然会无限递归：
# ❌ 递归步骤没有缩小问题规模
def silly(n):
if n == 0:
return
silly(n) # 还是 n，永远不会到达 0
# ✅ 必须让参数变化并趋近基线
def okay(n):
if n == 0:
return
okay(n - 1) # n 每次减 1，最终到达 0检查递归步骤时，要验证：每次递归调用后，输入是否在某种意义上「变小」了？
陷阱三：忽略递归的重复计算
纯递归在没有记忆化的情况下会产生大量重复计算，如 Fibonacci 的朴素递归版本。遇到这种情况，可以用 functools.lru_cache 自动缓存结果，或者手动维护一个备忘录字典。这是递归性能优化的标准做法。
陷阱四：递归深度超过限制
递归深度默认上限是 1000。如果你的递归可能超过这个深度（比如处理大型树结构或长序列），应该考虑：
- 用迭代替代递归
- 用
lru_cache加记忆化减少调用次数 - 用显式栈模拟递归（将调用栈改为堆上的数据结构）
不要简单地通过 sys.setrecursionlimit() 来解决——这只是在推迟问题，并未消除根本风险。
小结
递归是用函数自身解决规模更小同类问题的编程范式。一个正确的递归函数必须包含基线条件（停止点）、递归步骤（缩小问题）和终止保证（确保能到达基线）。Python 的递归通过调用栈实现，每层递归对应一个栈帧，栈的深度受 sys.getrecursionlimit() 限制（默认 1000）。递归相比迭代的代价是额外的栈帧开销和潜在的重复计算，但在树遍历、回溯搜索等场景下，递归的代码结构往往比迭代更自然清晰。Python 不支持尾递归优化（TCO），因此尾递归应改写为显式循环；需要深层递归时优先用迭代或 lru_cache 记忆化。掌握这三点——三要素、调用栈本质、TCO 缺失——递归就不再是神秘的技巧，而是一种可以安全使用的问题分解工具。
练习与思考题
-
用递归实现一个函数
flatten(lst)，将嵌套列表（如[1, [2, [3, 4]], 5]）展平为[1, 2, 3, 4, 5]。提示：用isinstance(x, list)判断元素是否为列表。 -
手写一个不带
lru_cache的递归 Fibonacci 函数，与迭代版本对比，分别在n=20、n=35时测量运行时间。你能观察到什么规律？为什么会有这个规律？ -
用回溯法实现一个函数
combinations(items, k)，返回从items中选取k个元素的所有组合（不区分顺序）。提示：在每个位置决定是否选取当前元素，然后递归处理剩余元素。 -
讨论：在什么场景下递归比迭代更合适？在什么场景下应该避免使用递归？结合调用栈的内存开销和代码可读性两方面给出你的分析。