文章目录第一阶段为什么需要递归背景与痛点1. 场景引入用循环解决嵌套问题的“笨重”2. 递归的解法把大问题拆成小问题第二阶段核心功能全景图第三阶段逐功能实战学习 1. 递归的三问法 2. 经典数学问题斐波那契数列 3. 记忆化Memoization给递归装上“缓存” 4. 遍历嵌套数据结构递归的真正主场 5. 尾递归思想避免内存爆炸第一阶段为什么需要递归背景与痛点1. 场景引入用循环解决嵌套问题的“笨重”假设你需要计算一个数字的阶乘如 5! 5 × 4 × 3 × 2 × 1。如果用传统的循环你需要这样写# 传统做法使用 for 循环deffactorial_iterative(n):result1foriinrange(1,n1):result*ireturnresultprint(factorial_iterative(5))# 120这看起来还行但如果遇到嵌套结构比如遍历一个包含未知层级子文件夹的文件系统或者解析嵌套的 JSON循环就会变得极其复杂需要维护多个栈或队列。痛点总结状态管理复杂循环需要手动维护计数器或状态变量。难以表达自相似问题对于“树形结构”或“分治问题”循环的逻辑非常反直觉。代码可读性差多层嵌套的循环像迷宫难以阅读和维护。2. 递归的解法把大问题拆成小问题递归的核心思想是函数自己调用自己直到满足一个停止条件。# ✅ 递归做法数学公式的直接翻译deffactorial_recursive(n):# 约定n 是非负整数0! 和 1! 都等于 1ifn2:# 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}!)。观察控制台输出的调用顺序体会“层层深入再层层返回”的过程。第二阶段核心功能全景图功能模块解决的问题关键词基础递归将大问题拆解为相同的小问题基线条件 (Base Case), 递归步骤数学与序列斐波那契、阶乘、汉诺塔数学归纳法数据结构遍历树、图、嵌套列表的遍历深度优先搜索 (DFS)记忆化递归解决重复计算导致的性能灾难lru_cache尾递归思想减少内存占用的优化思路累加器 (Accumulator)第三阶段逐功能实战学习 1. 递归的三问法当你“不会写递归的下一次调用怎么写”时不要背太多概念直接按顺序回答三个问题答完基本就能写出来怎么停什么时候停止停止时应该返回什么怎么变小下一次递归调用传入什么“更小的输入”确保每次都更接近停止条件怎么得到结果这一层如何产出结果等子调用返回后再组合例如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 smallermake_smaller(x,...)subf(smaller,...)# 递归调用点把问题变小returncombine(x,sub,...)# 本层如何把子结果变成最终结果# ✅ 倒计时最直观的递归defcountdown(n):ifn0:# Q1 怎么停到 0 就停止这里不需要返回值print(发射)returnprint(n)# Q3 怎么得到结果这一层先做事副作用countdown(n-1)# Q2 怎么变小n - n-1countdown(3)# 3# 2# 1# 发射提示这是“副作用型递归”每层先print再递归到n-1直到n0停止。动手验证 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 的版本需要调整基线条件和示例。ifn2:# 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如果没算过正常递归计算把结果存进缓存再返回maxsizeNone缓存不设上限如果给一个整数如maxsize128会按LRU最近最少使用淘汰旧缓存什么时候你该想到用缓存一眼判断递归/动态规划里出现大量重复子问题同一个f(x)会被反复计算比如斐波那契就是典型函数是“近似纯函数”同样输入 → 同样输出不依赖时间/随机数/外部 IO否则缓存可能不正确输入空间不会无限大否则缓存可能占用过多内存fromfunctoolsimportlru_cache# ✅ 记忆化递归瞬间起飞lru_cache(maxsizeNone)deffib_fast(n):ifn2:# 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):total0foritemindata:ifisinstance(item,list):# Q2 怎么变小对子列表递归更小的输入就是 itemtotalnested_sum(item)# Q3 怎么得到结果把子结果累加进 totalelse:# Q1 怎么停到叶子非 list就不再递归直接累加totalitemreturntotal 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):ifn2:# Q1 怎么停return1# Q2 n - n-1Q3 回溯时组合乘法returnn*fact_normal(n-1)# ✅ 尾递归思想用累加器传递结果deffact_tail(n,accumulator1):ifn2:# 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())