同事老张对着电脑愁了一下午。他要统计组织架构树每个层级的在职人数用循环写了快两百行到处是临时列表、层级标记、兄弟节点顺序的处理改一处崩三处越补越乱。我瞄了一眼他的数据说你把这份活儿交给递归函数试试。二十分钟后代码缩到了不到二十行逻辑一眼能看穿。递归函数不是玄学也不是面试官的刁难玩具。它本质上是一种把问题本身自带的重复结构直接翻译成代码的思维工具。这篇文章我想把递归的使用和设计一次讲透它到底怎么执行的、设计时该按什么顺序思考、常见的几个大坑怎么排查、工程上什么时候该用递归、什么时候该换成迭代。适合被递归绕晕的新手也适合写过不少递归但偶尔被栈溢出和重复计算坑到的老手。1. 递归的本质把问题拆成更小的自己1.1 树形结构天生就是递归的先看老张遇到的那棵组织架构树。CEO 下面挂着技术部、市场部技术部下面又挂着前端组、后端组前端组可能还挂着基础架构小组。这种结构有个特点一棵树的子树它自己还是一棵树。这不是巧合文件系统、商品分类、评论楼中楼、菜单权限几乎所有的树形数据都长这样。树的定义本身就是递归的——树由根节点和若干子树构成子树是一棵更小的树子树又由子树的子树构成。如果用循环去遍历这种结构你必须自己维护一个栈或者队列手动记录哪些节点访问过、哪些兄弟节点还没处理顺序稍有疏忽就会漏节点或者重复访问。代码写出来都是 append、pop、visited.add 这种细节真正的业务逻辑反而被淹没在状态管理里了。而递归处理这种结构写出来的代码几乎就是问题定义的翻译先处理当前节点再依次处理当前节点的每一棵子树。为什么递归适合树因为树这个数据结构本身就是用递归方式定义的。1.2 递归思维模型任务清单法则很多人对递归恐惧是试图在心里完整模拟函数调用自己的全过程想象一个函数无限嵌套下去很快就晕了。我给你一个更生活化的模型。假设你在办公室整理一个巨大的文件夹打开后发现里面还有子文件夹。你的实际做法是什么手头这个文件夹先放一边打开子文件夹处理完里面的所有文件再回到刚才的位置继续。如果子文件夹里还有子文件夹就一层一层往下钻直到某个文件夹里没有文件夹了才开始往回收。这不就是一个递归吗处理一个文件夹的动作是先处理当前文件夹里的文件遇到子文件夹就重复执行处理一个文件夹这个动作。区别只在于人处理时靠大脑记着回到哪里函数处理时靠调用栈记着回到哪里。所以递归的思维模型很简单遇到子任务先暂停当前任务把子任务做完再回来续上前面的工作。1.3 递归代码的通用骨架脑子里有了这个模型递归函数的代码骨架其实是固定的def solve(当前参数): if 满足终止条件: return 直接结果 # 拆解成规模更小的同型子问题 子问题结果 solve(更小的参数) # 把子问题结果组合成当前问题结果 return 组合结果用这套骨架能解决的问题主要有三类数据本身是递归定义的树、链表、嵌套列表的处理。问题可以被拆成同类型的子问题排序、二分查找、分治计算。状态空间搜索迷宫寻路、排列组合枚举。判定标准就一条把问题缩小一圈之后剩下的事和原来是不是同一类事如果是就可以用递归如果不是递归就帮不上忙。2. 调用栈递归真正执行的地方2.1 函数调用与栈帧递归不神秘但它依赖一个底层机制调用栈。不理解这个你后面遇到栈溢出就完全没法排查。每次你调用一个函数操作系统都会在调用栈上压入一个栈帧里面存的是这个函数运行需要的信息参数值、局部变量、函数执行到哪一行了。函数执行完返回后这个栈帧被弹出程序回到调用方的返回地址继续往下走。这个后进先出的机制跟叠盘子一模一样——你后放上去的盘子一定是先被拿走的。函数 A 调用函数 BB 的栈帧在 A 的栈帧上面B 执行完B 的栈帧弹出A 继续执行。递归只是恰好让 A 和 B 是同一个函数但栈帧的机制完全一致。2.2 用 factorial(4) 走一遍完整的入栈出栈过程看一个最经典的例子。假设我们要算 4 的阶乘def factorial(n): if n 1: return 1 return n * factorial(n - 1)很多人以为递归是一路算上去先算 factorial(4) 得到 4 乘 factorial(3)然后 factorial(3) 是 3 乘 factorial(2)……其实执行顺序不是这样的。调用栈的实际过程是factorial(4) 被调用n4不满足终止条件于是调用 factorial(3)。此时栈里压着 factorial(4) 的栈帧等待返回。factorial(3) 被调用n3不满足终止条件调用 factorial(2)。栈里压着两个栈帧factorial(4) 和 factorial(3)。factorial(2) 被调用n2不满足终止条件调用 factorial(1)。栈里压着三个栈帧。factorial(1) 被调用n1满足终止条件直接返回 1。此时它不需要再压栈帧了。然后开始归的旅程factorial(2) 收到 factorial(1) 返回的 1算出 2 * 1 2返回给 factorial(3)factorial(3) 收到 2算出 3 * 2 6返回给 factorial(4)factorial(4) 收到 6算出 4 * 6 24返回给调用方。注意这个过程递是不断压栈、层层深入归是不断弹栈、层层回算。阶乘这种写法计算结果是在归的路上才产生的。理解这个先拆到底再一路算回来的过程你会突然明白很多递归代码为什么这么写。比如后序遍历之类的问题本质就是先处理子树再回到当前节点。2.3 为什么递归太深会栈溢出既然递归会压栈那每递归一层调用栈就多一个栈帧。栈空间是有限的栈帧太多就会溢出。这就是 RecursionError 和段错误Segmentation fault的来源之一。Python 出于保护默认限制了递归深度。你可以查一下import sys print(sys.getrecursionlimit())默认一般是 1000。也就是说递归调用的层数超过 1000 层Python 就会直接抛 RecursionError不再继续往下执行。这个限制不是为了刁难你而是防止你程序写错比如递归没写终止条件时瞬间吃光系统资源。有人问那我用 sys.setrecursionlimit(100000) 改大一点行不行行但你只是把症状往后推了。改到十万遇到超深的数据或者真的无限递归照样崩而且崩得更难看。setrecursionlimit 治标不治本真正要解决的是为什么递归会这么深这个放在第 5 章讲。3. 设计递归的实操方法递推式、终止条件、收敛方向很多教程讲递归就甩一句递归就是自己调用自己然后扔给你几个例子看完还是不会写自己遇到的题。本节给一个可复用的设计顺序按这个顺序走递归没你想的那么难。3.1 先写出函数签名明确输入和输出这是最容易被忽略的一步。很多新人上来就写 return self.solve(...) 之类的东西写几行就乱套了因为根本不清楚这个函数是干嘛的。先问自己这个递归函数接收什么参数返回什么结果比如统计二叉树节点个数签名就是 count_nodes(root: 节点) - int。输入一棵树的根节点输出这棵树有多少个节点。再比如算斐波那契数列第 n 项签名就是 fib(n: int) - int。把签名写清楚相当于给自己立了个契约只要我调用这个函数它就会按照签名返回正确结果我不需要关心它内部怎么实现。这个思路特别重要——等下写递归体的时候你就能站在子问题的角度思考了。3.2 找递推关系把大问题拆成小问题签名有了下一步是问自己当前规模的问题能不能由几个更小规模的同型子问题的结果组合出来这是递归设计的核心一步。怎么找数值递推类把 f(n) 用 f(n-1)、f(n-2) 表示出来。阶乘是 f(n) n * f(n-1)斐波那契是 f(n) f(n-1) f(n-2)。结构递归类把树节点的问题拆成左子树、右子树的问题。节点总数 1 左子树节点数 右子树节点数。分治类把数组拆成两半分别解决再合并结果。归并排序就是这样。找到一个递推关系后它基本就对应着递归函数里的一个 return 语句。def count_nodes(root): if root is None: return 0 # 递推关系左子树节点数 右子树节点数 当前节点自己 return count_nodes(root.left) count_nodes(root.right) 13.3 写终止条件所有拆不动的情况都要覆盖递推关系必须有底否则就真的无限递归了。终止条件就是那些不用再拆、直接给结果的最小情况。数值类n 0 或 n 1直接返回已知结果。结构类root is None返回 0 或空值root 是叶子时返回特定值。搜索类坐标越界、目标已找到、可选路径用完。这里有一个非常常见的坑写了一个终止条件但没覆盖所有边界分支。还是拿二叉树举例。统计节点数写了 root is None 返回 0那空数组、空链表这些极端情况能兜住。但如果你写翻转一棵二叉树终止条件只写 root is None 返回 None这没问题因为叶子节点的左右子树都是 None递归自然停住。可如果你在处理字符串时只考虑 s 为空的情况忘了 s 只有一个字符的情况就可能出现 s[1:] 切到空串后继续切陷入错误。经验是每次写递归把参数可能到达的最小形态列一遍看着它们一个个被终止条件兜住再往下写。3.4 参数收敛每一层都要离终止条件更近递归的最终目标是到达终止条件所以每一层递归的调用参数都必须比当前这一层更小、更简单、更接近边界。数值递归传 n-1、n//2确保越来越小。树递归传 root.left、root.right确保子树越来越浅。数组递归传 start1 或者传入左半区间的索引确保区间在缩小。如果参数不收敛递归就永远够不到终止条件就会无限递归。这个道理像走楼梯要一层一层往下走你如果每层都只平移不停下就永远到不了终点。实践中的一个小技巧写递归之前先假设规模为 k 的子问题已经能算出结果了然后想想我用它怎么算出规模为 k1 的结果。这个思路能帮你把递推关系和参数收敛同时理顺避免一上来就在函数体里迷路。4. 递归三大坑与完整排查链路4.1 无限递归从报错信息逆推根因无限递归是新人遇到最多的错误。报错通常长这样RecursionError: maximum recursion depth exceeded while calling a Python object或是在栈很深时报RecursionError: maximum recursion depth exceeded in comparison遇到这个第一件事不是去调 sys.setrecursionlimit而是去想清楚递归为什么没有停只有两个可能终止条件没写对或者参数没有收敛。排查链路如下看报错信息里最后几行栈回溯找到反复出现的同一个函数。如果在栈回溯里看到同样的行号反复出现那这一行就是无限递归发生的核心位置。在递归函数入口临时加一行打印把参数的值打出来print(fcurrent param: {n})。运行后观察参数是否在某一组值之间反复横跳或者是否一直不靠近终止条件。如果参数在几组值之间循环基本可以确认是数据结构里有环后面 4.3 会细说如果参数一直不变那就是递归调用时传参传错了比如把 parent 传成了当前节点本身。修复后把临时打印删掉加一个守卫再跑一次在函数开头加if depth 100: raise RuntimeError(递归过深疑似未收敛)防止修复不彻底时再次卡死。记住RecursionError 只是症状不是问题本身。盲目调高递归限制等于给发烧的人吃退烧药但不查感染源。4.2 重复计算同一个子问题被算了一遍又一遍无限递归是显性的崩溃重复计算则是隐性的性能炸弹。最经典的例子是朴素斐波那契def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)这段代码逻辑完全正确但算 fib(40) 就已经慢到让人抓狂了。为什么因为在递归调用的展开过程中同一个子问题会被反复求解。调用链展开后fib(2) 会被算 3 次fib(3) 会被算 5 次fib(4) 会被算 8 次。整个递归树里有大量重叠的子树复杂度是指数级的 O(2^n)。n40就要调用数亿次函数n50基本就等不完了。这个坑比栈溢出更隐蔽因为程序不报错只是慢得离谱你会误以为代码逻辑有问题或者电脑太卡。判断标准很简单在纸上画出递归调用的展开图看看同一个参数是否被多次计算。如果出现了大量重复的子树就需要用下一章的记忆化来做优化或者在设计时就避免这种拆分方式。4.3 真实事件组织架构树递归统计踩坑全记录回到开篇老张那个需求。我帮他改成递归后测试时又报了一次 RecursionError。我以为他数据量特别大但数据其实就几千条。排查过程值得完整记录第一轮排查我在递归入口加上部门 id 打印发现 id 在反复出现技术部 - 前端组 - 技术部 - 前端组。这明显不是数据深而是数据里有环。查数据库发现有一批历史数据是从旧系统导过来的parent_id 字段出现了环形引用A 部门的 parent_id 指向 BB 的 parent_id 又指向 A。数据库表设计时没有加约束老系统的脏数据就这样进来了。这类环在树形数据里防不胜防因为上游数据不总是可信的。设计递归时如果处理的是外部数据源就不能默认它是一棵严格的树。解法很简单用一个集合记录已经访问过的节点遇到重复就跳过。def count_staff(dept_id, visitedNone): if visited is None: visited set() if dept_id in visited: return 0 visited.add(dept_id) total count_people_in_dept(dept_id) for child_id in get_child_depts(dept_id): total count_staff(child_id, visited) return total注意这里 visited 集合要在调用链中共享所以必须通过参数传递而不是在函数内部每次新建。这个案例也说明递归面对的数据结构并不总是教科书里那只干净的二叉树。工程上既要懂递归怎么写也要警惕假设前提可能被脏数据破坏。5. 工程优化记忆化、尾递归与迭代改造5.1 记忆化用缓存消除重叠子问题第 4.2 节里那个斐波那契性能差在重复计算。最直接的优化叫记忆化思路一句话第一次算出子问题的结果存起来后面再遇到同一个子问题直接取答案不再重新算。基于原函数改造成本极低。手动加字典cache {} def fib(n): if n 1: return n if n in cache: return cache[n] cache[n] fib(n - 1) fib(n - 2) return cache[n]也可以直接用标准库装饰器from functools import lru_cache lru_cache(maxsizeNone) def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)加了缓存后每个 n 只会真正算一次复杂度从指数级 O(2^n) 直接降到线性 O(n)这就是为什么记忆化是递归优化性价比最高的一招。使用时有几个注意点递归参数必须是可哈希的list、dict 这类可变类型不能直接当缓存 key需要转成 tuple 或 frozenset。如果递归函数依赖全局状态、随机数或当前时间就不能用缓存结果可能错。缓存返回的是可变对象时要注意外部代码可能会修改缓存里的值导致下次取出的是脏数据。记忆化适合的场景是子问题高度重叠的递归特别是各种状态搜索、动态规划的递归实现。5.2 尾递归的真相别再被面试题带偏了尾递归的定义是递归调用是函数执行的最后一个动作并且递归调用的结果直接返回不再参与后续计算。比如def fact_tail(n, acc1): if n 0: return acc return fact_tail(n - 1, acc * n)而def fact(n): if n 1: return 1 return n * fact(n - 1)就不是尾递归因为 fact(n-1) 的结果还要再乘 n 才能返回。尾递归之所以被反复提及是因为在支持尾递归优化TCO的编译型语言里编译器发现当前栈帧已经没用了就可以直接把它丢掉递归就能以常数级栈空间运行和循环一个级别。这是 C、C、Rust 等语言在开启优化后的行为。但 Python 官方明确不支持尾递归优化。所以在 Python 里写尾递归并不能规避 RecursionError效果和普通递归没有本质区别。不要为了让函数看起来像尾递归而扭曲代码结构不值得。尾递归真正的价值在于帮你完成一种心智翻译把递归改写为循环只需要把递归参数转变成循环变量把累加结果变成循环体内不断更新的变量。这段尾递归逻辑翻译成循环就是def fact_iter(n): acc 1 while n 0: acc * n n - 1 return acc5.3 显式栈迭代想保留递归逻辑又不想爆栈时的选择如果问题本身适合递归比如树遍历但数据深度可能大到让函数调用栈扛不住可以选择显式栈用一个 list 当栈模拟函数递归的入栈出栈过程。这样你把需要的栈从系统调用栈里搬到了自己手里想控制多深都可以。以统计二叉树节点数为例递归写法def count_nodes(root): if root is None: return 0 return count_nodes(root.left) count_nodes(root.right) 1用显式栈改写def count_nodes_iter(root): count 0 stack [root] while stack: node stack.pop() if node is None: continue count 1 stack.append(node.left) stack.append(node.right) return count这个改写的本质是把系统用栈帧维护的待办任务换成你自己维护的待处理节点列表。什么时候用递归、什么时候用显式栈我给出自己的决策参考场景推荐方案数据量小、树浅、可读性优先递归重叠子问题多递归 记忆化深度可能超过几百上千层显式栈迭代生产环境对稳定性和栈占用有硬要求显式栈迭代数据来自不可信外部源可能带环迭代 visited 去重集合这里想多说一句递归和迭代不是对立的很多情况下它们是同一份逻辑的两种描述。递归强调问题长什么样迭代强调机器怎么算。工程师的修养是两种都要会按场景切换。6. 实战案例目录树打印工具的完整设计过程6.1 先建模输入是什么输出是什么最后用一个完整案例把前面的方法串一遍。需求来自真实工作写一个小工具给定一个根目录打印目录树类似 tree 命令每个层级缩进两个空格显示目录和文件名中间跳过一些无法访问的目录并支持限制最大深度。这个需求的数据结构是文件系统天然是树非常适合递归。我们先定函数签名def print_tree(path: str, indent: int 0, max_depth: int 5) - None参数path是当前要打印的目录路径indent是当前层级缩进量max_depth是最大允许打印的深度。返回值为空因为我们的操作是打印不需要计算结果。6.2 递归版本开口就是终止条件和递归调用按第 3 章的思路拆解终止条件如果 indent 超过 max_depth就不打印也不再深入直接返回。递推关系打印当前目录下的每个条目如果条目是目录就递归调用自身处理这个子目录。参数收敛每次递归indent 1path 变成子目录路径逐渐逼近 max_depth。import os def print_tree(path, indent0, max_depth5): if indent max_depth: return try: entries sorted(os.scandir(path), keylambda e: e.name) except OSError: print( * indent f[无法访问: {path}]) return for entry in entries: print( * indent entry.name) if entry.is_dir(follow_symlinksFalse): print_tree(entry.path, indent 1, max_depth)这里有三个行业里踩过坑的细节第一用 os.scandir 而不是 os.listdir。scandir 返回的是 DirEntry 对象可以直接用 is_dir 判断类型不用再多做一次系统调用大目录下性能差距很明显。第二try/except 必须包住 scandir 和递归因为权限不足、路径已删除、网络磁盘掉线等等都会抛 OSError。一个打印工具绝不能因为某个目录没权限就整个崩溃。第三follow_symlinksFalse。这不是可选的小事而是防止符号链接导致无限递归。如果某个目录里有个软链接指向它的祖先目录跟着链接走会陷入死循环最终栈溢出。递归处理外部文件系统时环是一种真实存在的风险不是极端情况。6.3 深目录下的迭代版本显式栈的正确打开方式递归版干净直观但如果某些目录真的深到几百上千层比如灰产日志目录、自动化测试生成的嵌套项目递归版还是会蹦出 RecursionError。生产环境用这个工具可以把核心逻辑改成显式栈def print_tree_iter(root, max_depth5): stack [(root, 0)] while stack: path, depth stack.pop() if depth max_depth: continue try: entries sorted(os.scandir(path), keylambda e: e.name) except OSError: continue for entry in reversed(entries): print( * depth entry.name) if entry.is_dir(follow_symlinksFalse): stack.append((entry.path, depth 1))这里有个很隐蔽的坑因为 list.pop() 是从栈尾取元素如果你直接按字母顺序把 entries 压进栈打印顺序会和递归版相反——最后一个字母的目录反而先打印。所以必须先把 entries 反转这样从栈尾弹出时先弹出来的是字母序最小的条目打印顺序就和递归版一致了。这个细节要是没意识到你会得到一个看起来有规律但和预期不一样的目录树排查半天还以为递归和迭代的语义不同。6.4 可维护性之后哪些扩展值得做工具能用之后你很可能还想加几个功能指定输出格式、统计每个目录的文件个数、排除某些目录、支持 glob 模式匹配。从递归函数扩展这些功能并不难但要记住每一个功能扩展都应该重新审查一遍终止条件和环的兜底。比如加了排除某些目录别在递归调用时等目录打印完再判断因为如果你不打算进入某个子目录就应该在递归调用前直接跳过否则白耗一次系统调用。又比如统计文件个数这天然适合递归实现但如果你要统计的总量特别大缓存和显示进度条就值得考虑——不要在一个递归函数里既做统计又做缓冲输出拆成两个纯函数更容易测试和维护。我在实际维护这类工具时还有一个习惯给工具加一个总深度统计日志每次打印前记录depth 某个阈值的路径。这样即使能正常工作也能持续观察线上目录结构的变化避免数据在其他环节悄悄引入了深嵌套结构而不自知。最后分享一点个人体会写了这么多年递归最大的一个心得是不要试图在心里完整跑一遍递归的调用链。人脑的调用栈也就几层深非要跟踪每一层递归立刻变得不可理解。正确的姿势是相信你的抽象——函数签名已经约定了子问题的答案你只需要负责把大问题拆成子问题再把子问题答案拼回大问题。就像你写代码调用第三方库时不会去关心库里每一行是怎么执行的。另一个小技巧调试递归时别盯着整个递归树看那会让你越陷越深。挑一个最小例子比如 n3 或者一棵两层深的树拿张纸把每一次调用的参数和返回值一笔一笔画出来。画一遍之后整个递归的运行逻辑就深深刻在脑子里了之后再遇到复杂的递归代码你会自然地在脑中浮现出这条最小的调用链。递归是一种思维方式的转变从我带你去逛完每一个角落变成我告诉你每个角落都长这样——希望这篇文章帮你完成这次转变。