Python 递归实战
递归的本质，是用“更小规模的同类问题”的解，来拼凑出“当前问题”的解。
def tree_size(node) -> int:
if node is None:
return 0
return 1 + tree_size(node.left) + tree_size(node.right)
正确性自检清单
写递归前，先过这四关：
- Base Case（终止条件）： 最小实例必须直接返回，不能继续递归。
- Progress Measure（收敛性）： 每次递归调用，必须让问题规模严格变小，确保最终能碰到 Base Case。
- Inductive Contract（归纳假设）： 假设子问题的递归结果是对的，然后验证当前层级的组合逻辑是否正确。
- State Ownership（状态管理）： 如果涉及可变累加器（Accumulator），必须明确它是被复制、恢复，还是严格限制在局部作用域内，避免状态污染。
成本模型
评估递归开销，要看两点：
- 调用次数
- 单次调用的工作量
栈空间峰值取决于递归树的最大深度，而不是节点总数。
Python 解释器不保证尾调用优化（Tail Call Elimination, TCE），且为了防栈溢出，对递归深度有硬性限制。
- 建议： 深度较大的线性递归，通常应改写为显式栈（Explicit Stack）的迭代实现。
适用场景
递归在以下场景最自然：
- 树结构、嵌套语法解析；
- 分治算法（Divide and Conquer）；
- 深度优先搜索（DFS）与回溯（Backtracking）；
- 输入深度可控的自然递归数学定义。
重复子问题与记忆化
递归不等于低效，但重叠子问题可能导致指数级重复计算。
- 工具：
functools.cache或lru_cache可对参数可哈希的纯函数进行记忆化（Memoization）。 - 注意： 缓存会持有参数和结果的引用。在长驻进程中，需明确缓存的生命周期策略，防止内存泄漏。
严禁仅因函数是递归的，就缓存以下类型：
- 有副作用的函数
- 依赖时间/随机性的函数
- 返回生成器（Generator）的函数
- 返回可变对象的函数
完整的树示例与输入假设
这里用 None 表示空子树，其他节点必须有 left 和 right 属性。输入必须是有限的树：不能有环；如果要统计不同节点的数量，分支间也不能共享节点。
from dataclasses import dataclass
@dataclass
class Node:
left: "Node | None" = None
right: "Node | None" = None
tree = Node(Node(), Node(Node()))
assert tree_size(None) == 0
assert tree_size(Node()) == 1
assert tree_size(tree) == 4
每个叶子返回 1 + 0 + 0；父节点把两棵互不重叠的子树大小相加，再加上自身的一个节点。当前子树的节点数是非负整数，每次进入非空子树都会严格减少。这才说明递归能够终止，仅有终止分支还不够。假设属性访问和整数加法按常数时间计，对于有 n 个节点、高度为 h 的树，总工作量与 n 成正比，递归栈峰值与 h 成正比。
同一契约也可以不用递归调用实现：
def tree_size_iterative(node):
pending = [] if node is None else [node]
count = 0
while pending:
current = pending.pop()
count += 1
if current.right is not None:
pending.append(current.right)
if current.left is not None:
pending.append(current.left)
return count
assert tree_size_iterative(tree) == tree_size(tree)
assert tree_size_iterative(None) == 0
两个版本都不检测环。遍历图时需要已访问集合，并明确共享节点是否只计一次。在 CPython 中，递归过深会抛出 RecursionError，但安全深度没有可移植的固定值。sys 文档提醒：递归上限设得过高可能导致解释器崩溃。记忆化可以减少重复工作，却不能缩短最深的调用链。