Python 递归：入门+实践

第一阶段：为什么需要递归？（背景与痛点）

1. 场景引入：用循环解决嵌套问题的“笨重”

假设你需要计算一个数字的阶乘（如 5! = 5 × 4 × 3 × 2 × 1）。如果用传统的循环，你需要这样写：

# 😩 传统做法：使用 for 循环deffactorial_iterative(n):result=1foriinrange(1,n+1):result*=ireturnresultprint(factorial_iterative(5))# 120

这看起来还行，但如果遇到嵌套结构（比如遍历一个包含未知层级子文件夹的文件系统，或者解析嵌套的 JSON），循环就会变得极其复杂，需要维护多个栈或队列。

痛点总结：

• 状态管理复杂：循环需要手动维护计数器或状态变量。
• 难以表达自相似问题：对于“树形结构”或“分治问题”，循环的逻辑非常反直觉。
• 代码可读性差：多层嵌套的循环像迷宫，难以阅读和维护。

2. 递归的解法：把大问题拆成小问题

递归的核心思想是：函数自己调用自己，直到满足一个停止条件。

# ✅ 递归做法：数学公式的直接翻译deffactorial_recursive(n):# 约定：n 是非负整数；0! 和 1! 都等于 1ifn<2:# Q1 怎么停：基线条件 + 基线返回值return1# Q2 怎么变小：把输入从 n 变成 n-1# Q3 怎么得到结果：等子调用返回后再组合（n * 子结果）returnn*factorial_recursive(n-1)print(factorial_recursive(5))# 120

三问对照（用来“设计递归调用”）：

• 更小的输入是什么？：从n变成n - 1
• 什么时候停？停时返回什么？：当n < 2时停止，返回1
• 这一层怎么得到最终结果？：先算出子问题factorial_recursive(n - 1)，再用n * (...)组合结果

🧪动手验证 1：在 IDE 中运行递归版本，并在return n * ...这一行加上print(f"计算 {n}!")。观察控制台输出的调用顺序，体会“层层深入，再层层返回”的过程。

第二阶段：核心功能全景图

第三阶段：逐功能实战学习

🔹 1. 递归的三问法

当你“不会写递归的下一次调用怎么写”时，不要背太多概念，直接按顺序回答三个问题（答完基本就能写出来）：

1. 怎么停？什么时候停止？停止时应该返回什么？
2. 怎么变小？下一次递归调用传入什么“更小的输入”，确保每次都更接近停止条件？
3. 怎么得到结果？这一层如何产出结果？
   • 等子调用返回后再组合（例如n * f(n-1)、f(n-1)+f(n-2)）
   • 或用累加器/状态一路往下传（例如f(n-1, acc*n)）
   • 或者这是“副作用型”递归：函数除了“返回值”之外，还会对函数外部产生可观察的影响（例如print输出、写日志/文件、修改外部变量或传入的可变容器）；这类递归通常不靠返回值层层组合来得到结果

备注：第 1 问和第 2 问保证“递归能停且在推进”；第 3 问决定你怎么写return，也是很多人真正卡住的地方。

你也可以把它记成一个模板（把递归当黑盒：输入 → 输出）：

deff(x,...):ifbase_case(x,...):returnbase_value smaller=make_smaller(x,...)sub=f(smaller,...)# 递归调用点：把问题变小returncombine(x,sub,...)# 本层如何把子结果变成最终结果

# ✅ 倒计时（最直观的递归）defcountdown(n):ifn<=0:# Q1 怎么停：到 0 就停止（这里不需要返回值）print("发射！")returnprint(n)# Q3 怎么得到结果：这一层先做事（副作用）countdown(n-1)# Q2 怎么变小：n -> n-1countdown(3)# 3# 2# 1# 发射！

提示：这是“副作用型递归”（每层先print，再递归到n-1，直到n<=0停止）。

🧪动手验证 2：故意去掉countdown中的if n <= 0判断，运行countdown(3)，观察 Python 抛出的RecursionError: maximum recursion depth exceeded。

🔹 2. 经典数学问题：斐波那契数列

斐波那契数列（1, 1, 2, 3, 5, 8…）是递归的教科书级案例：F(n) = F(n-1) + F(n-2)。

# ✅ 基础递归deffib(n):# 说明：这里使用常见的定义 fib(1)=1, fib(2)=1# 如果你习惯 fib(0)=0 的版本，需要调整基线条件和示例。ifn<=2:# Q1 怎么停：基线条件 + 基线返回值return1# Q2 怎么变小：把 n 拆成 n-1 和 n-2 两个更小的输入# Q3 怎么得到结果：等两个子结果回来再组合（相加）returnfib(n-1)+fib(n-2)print(fib(6))# 8

三问对照：

• 更小的输入是什么？：n - 1和n - 2
• 什么时候停？停时返回什么？：n <= 2时返回1
• 这一层怎么产出结果？：等两个子问题返回后，把它们相加组合成答案

⚠️性能陷阱：计算fib(40)会非常慢！因为fib(5)会被计算多次，产生了指数级的重复计算。

🧪动手验证 3：运行fib(35)，感受明显的卡顿。然后继续往下看，学习如何解决这个问题。

🔹 3. 记忆化（Memoization）：给递归装上“缓存”

使用 Python 内置的functools.lru_cache装饰器，可以自动缓存函数的返回值，将指数级复杂度降为线性。

它的工作方式：

• 缓存 key：用“函数入参”当 key（所以入参通常要是可哈希类型，比如int/str/tuple）
• 命中（hit）：如果同样的入参之前算过，直接返回缓存结果，不再执行函数体
• 未命中（miss）：如果没算过，正常递归计算，把结果存进缓存再返回
• maxsize=None：缓存不设上限；如果给一个整数（如maxsize=128），会按LRU（最近最少使用）淘汰旧缓存

什么时候你该想到用缓存？（一眼判断）

• 递归/动态规划里出现大量重复子问题（同一个f(x)会被反复计算），比如斐波那契就是典型
• 函数是“近似纯函数”：同样输入 → 同样输出，不依赖时间/随机数/外部 IO（否则缓存可能不正确）
• 输入空间不会无限大（否则缓存可能占用过多内存）

fromfunctoolsimportlru_cache# ✅ 记忆化递归（瞬间起飞）@lru_cache(maxsize=None)deffib_fast(n):ifn<=2:# Q1 怎么停return1# Q2/Q3 同 fib：变小 + 组合；但缓存会复用子结果，避免重复计算returnfib_fast(n-1)+fib_fast(n-2)print(fib_fast(100))# 354224848179261915075，瞬间出结果！

小贴士：你可以用fib_fast.cache_info()看命中/未命中次数，用fib_fast.cache_clear()清空缓存（便于自己做实验）。

提示（对应“三问法”的第 3 问：性能/重复子问题）：递归结构不变，但缓存让“同一个子问题”只算一次，从指数级降到线性。

💡原理：第一次计算fib_fast(5)时，结果被存入缓存。下次再需要fib_fast(5)时，直接返回，不再递归。

🧪动手验证 4：对比fib(35)和fib_fast(35)的执行时间，感受缓存的威力。

🔹 4. 遍历嵌套数据结构（递归的真正主场）

当面对层级未知的嵌套列表时，循环几乎无能为力，而递归轻松搞定。

# ✅ 计算任意嵌套列表中所有数字的总和defnested_sum(data):total=0foritemindata:ifisinstance(item,list):# Q2 怎么变小：对子列表递归（更小的输入就是 item）total+=nested_sum(item)# Q3 怎么得到结果：把子结果累加进 totalelse:# Q1 怎么停：到叶子（非 list）就不再递归，直接累加total+=itemreturntotal nested_list=[1,[2,[3,4],5],6,[7,8]]print(nested_sum(nested_list))# 36

三问对照：

• 更小的输入是什么？：遇到子列表时，把item当作更小的输入递归处理
• 什么时候停？停时返回什么？：当item不再是list（到达叶子），就直接把数字加进total
• 这一层怎么产出结果？：用total做累加，把子结果nested_sum(item)合并进来

🧪动手验证 5：创建一个包含 5 层嵌套的列表，用上面的函数求和，验证结果。

🔹 5. 尾递归思想：避免内存爆炸

普通递归在返回时需要保留每一层的调用栈（因为要等子调用返回后再做乘法）。尾递归的思想是：把中间结果通过参数传递下去，让最后一次调用直接返回结果。

# 😩 普通递归：需要保留 n 层栈deffact_normal(n):ifn<2:# Q1 怎么停return1# Q2 n -> n-1；Q3 回溯时组合（乘法）returnn*fact_normal(n-1)# ✅ 尾递归思想：用累加器传递结果deffact_tail(n,accumulator=1):ifn<2:# Q1 怎么停：直接返回累加器returnaccumulator# Q2 怎么变小：n -> n-1# Q3 怎么得到结果：把本层贡献乘进 accumulator，继续往下传（累加器型）returnfact_tail(n-1,n*accumulator)print(fact_tail(5))# 120

提示（对应三问法第 3 问）：这是“累加器型”写法——把中间结果放在accumulator里一路传到底，不再回溯组合。

⚠️Python 的遗憾：Python 解释器没有实现尾递归优化（TCO）。所以尾递归在 Python 中不会减少内存占用，但它是一种极好的编程思维，且在支持 TCO 的语言（如 Scala）中极其重要。

🧪动手验证 6：分别用fact_normal(1000)和fact_tail(1000)测试。多数环境下两者都会触发RecursionError（递归深度限制通常是 1000，但以实际环境为准）。你也可以用下面这段代码查看限制：

importsysprint(sys.getrecursionlimit())