用两段 Python 代码检验你的递归思维

递归不只是“函数调用自己”。真正需要想清楚的是：什么时候停止、每次调用处理多大一块问题，以及状态和计算结果该由谁保存。用一棵树和一个带缓存的数列，就能检验这些关键点。

先找出口，再缩小问题

递归函数至少要回答两个问题：最小的问题是什么，以及下一次调用为何更接近它。遍历树时，叶子节点就是出口；计算 fib(n) 时，n 为 0 或 1 就可以直接返回。若参数没有向出口推进，函数最终会触及 Python 的递归深度限制。

遍历递归数据时，状态跟着调用走

下面假设树由字典表示，每个节点有 name，可选的 children 是子节点列表。任务是列出从根节点到每片叶子的路径。代码可直接保存为 recursion_demo.py 并运行：

from functools import lru_cache


def leaf_paths(node, path=()):
    current_path = path + (node["name"],)
    children = node.get("children", [])
    if not children:  # 基本情况：到达叶子
        return ["/".join(current_path)]

    paths = []
    for child in children:
        paths.extend(leaf_paths(child, current_path))
    return paths


@lru_cache(maxsize=None)
def fib(n):
    if n < 0:
        raise ValueError("n must be non-negative")
    if n < 2:  # 基本情况
        return n
    return fib(n - 1) + fib(n - 2)


tree = {
    "name": "repo",
    "children": [
        {"name": "README.md"},
        {
            "name": "src",
            "children": [{"name": "app.py"}, {"name": "tests.py"}],
        },
    ],
}

print(leaf_paths(tree))
print(fib(10))

运行后会得到 ['repo/README.md', 'repo/src/app.py', 'repo/src/tests.py'] 和 55。path 使用元组，每层调用都构造自己的新路径，因此兄弟节点不会意外共享可变状态。这里把空 children 视为叶子；如果你的数据模型区分“空目录”和“文件”，需要另加节点类型字段。

缓存解决的是重复子问题

fib(n) 会反复计算相同的参数，例如 fib(8) 会从多条调用路径出现。@lru_cache(maxsize=None) 按参数保存结果，让每个非负整数对应的结果只需计算一次。它不会让所有递归都变快：上面的树遍历若每个节点只访问一次，缓存通常没有收益。

缓存也有边界。被装饰函数的参数必须可哈希；若结果依赖会变化的外部状态，旧缓存可能失效。maxsize=None 还意味着缓存不会按大小自动淘汰，长时间运行的服务应评估内存占用。

写递归前的四个检查

• 基本情况能否直接返回？空输入、单节点输入是否覆盖到了？
• 每次调用是否严格缩小问题？
• 状态应作为参数传入、作为返回值汇总，还是确实需要共享？
• 是否存在重复子问题，值得缓存？

递归很适合树和嵌套结构，但要留意循环引用与极深的层级。输入可能形成环时应记录已访问节点；深度不可控时，显式栈通常比继续加深递归更稳妥。