我带过几个刚入行的朋友几乎每个人都在递归上卡过一次壳。看别人的代码短短五六行逻辑读起来也顺自己合上屏幕想手写一遍就变成了一团浆糊什么时候该往下调什么时候该往回退返回值到底给了谁全都说不清。递归之所以让人犯怵不是因为它难而是因为大多数人学它的时候被塞了一堆自己调用自己的形而上描述却没人把函数执行栈、参数怎么传、结果怎么回这几件具体的事摊开讲。这篇内容想做的事很直接把递归这个看似玄乎的概念还原成一连串可以被手算、可以被打印出来的具体动作。你会看到递归的执行过程怎么用打印日志复现基准情形写错会引发什么后果递归和迭代在什么场景下该选哪个以及汉诺塔、全排列这类经典问题到底是靠什么思路拆开的。不管你是刚学编程的新手还是工作几年但一遇到树形结构就绕道走的开发者把下面的内容跟着敲一遍递归会从背答案变成能推导的东西。1. 递归到底是什么从套娃到函数自我调用很多人第一次听递归接收到的定义是一个函数直接或间接地调用自己。这句话没错但它只描述了现象没说明本质。真正的核心在于递归是把一个规模较大的问题拆成一个结构完全相同、但规模更小的子问题直到子问题小到可以直接给出答案为止。注意这里有两个关键词——结构完全相同和规模更小。前者保证了子问题能用同一套逻辑处理后者保证了拆解过程一定会终止。少了任何一个递归都不成立。1.1 用生活场景把递归具象化先别急着看代码用几个生活场景把感觉找回来。第一个是查字典。你查一个课字释义里出现了一个你不认识的赋字于是你合上这一页先去查赋。查赋的时候又碰见不认识的字再接着查下一个。什么时候停当你查到的所有字都认识或者某个字在字典里查不到时你会停下来原路返回把之前每个字的解释一层层拼回去。这个过程就是标准的递归查字典的动作完全一样待查的字越来越少最终一定会遇到一个能直接看懂的终点。第二个是电影院的座位问题。你坐在第 5 排想知道自己前面还有几个人。你不需要从第一排数起只需要拍拍前面那个人的肩膀哥们儿你前面有几个人他再去问前面的人一直问到第一排第一排的人回答我前面没人。然后答案像接力一样传回来第 1 排说 0第 2 排说 1第 3 排说 2一路传到你这里就是 4。每个人做的事完全相同问题规模每问一次就减 1第一排就是那个不需要再问的终点。用生活场景理解递归的好处是它把函数自我调用这种抽象说法替换成了同一件事反复做、规模越来越小。这层直觉建立起来后看代码时你就不会盯着f(n)调用f(n-1)发呆而是能立刻反应过来这是在把问题往更小的规模上推。1.2 递归必须凑齐的两块拼图任何一段能正常工作的递归代码都必然包含两个部分基准情形base case和递推关系recursive case。基准情形负责终止它回答的是问题小到什么程度就不需要再往下拆了递推关系负责推进它回答的是规模为 n 的问题怎么用规模更小的答案拼出来。以阶乘为例n! n × (n-1) × ... × 1。用递归表达基准情形是n 0或n 1时返回 1递推关系是fact(n) n * fact(n-1)。再看斐波那契数列第 n 项等于前两项之和基准情形是前两项分别为 0 和 1递推关系是fib(n) fib(n-1) fib(n-2)。这两块拼图的关系很像数学归纳法。归纳法证明时你先证明 n1 成立基准再假设 nk 成立并推出 nk1 成立递推两者合起来就覆盖了所有正整数。递归的思维结构跟它一模一样。很多人写递归写崩问题几乎都出在基准情形上——要么漏了要么写的条件永远触达不到要么条件写反了导致无限下探。注意基准情形不是随便找个能返回的数。它必须是一个在有限次拆解后一定能被触及的状态。如果你写的基准是n 100而调用时传进去的是 5且每次递归是n-1那这个基准一辈子都碰不到。1.3 递归和迭代到底该选谁初学者经常纠结一个问题既然循环能干的活递归也能干那到底用哪个我的经验是看问题的数据结构而不是看代码长短。如果问题本身就是递归定义的比如树的遍历、图的深度优先搜索、文件目录的逐层扫描、语法树的求值那用递归写出来的代码几乎就是问题描述的直接翻译可读性远胜循环。反过来如果问题只是简单的线性累积比如求和、求最大值、字符串拼接那循环更直观也没有额外的函数调用开销。还有一个更现实的判断标准递归深度会不会失控。语言对递归层数都有隐式限制Python 默认大约 1000 层超出就抛RecursionErrorJavaScript 各引擎的栈深度也大多在几千到一万多层之间Java 和 C 类似取决于线程栈大小。如果你处理的数据规模可能达到十万级而且每一步只减少 1递归就不是个好选择。对比维度递归迭代代码可读性树形、嵌套结构中更直观线性累积场景更清晰空间开销每层调用占一个栈帧通常只需常数级变量深度风险受语言栈深度限制无栈溢出风险调试难度调用链长需要打印辅助单步跟踪直观典型场景树的遍历、回溯、分治数组求和、计数、线性扫描我自己的习惯是先用递归把逻辑写对跑通测试用例确认思路无误如果发现深度会成为瓶颈再把它改写成显式栈的迭代版本。先保证正确再谈优化这个顺序别反过来。2. 递归的执行机制栈帧、下探与回溯理解递归最大的障碍是很多人把它当成一次性跳到底再算回来的黑盒。实际上每一次函数调用都会在内存里留下痕迹这些痕迹堆积成一条链链的长度就是递归深度链上每个节点保存着当时的参数、局部变量和返回位置。把这些看清楚递归就不再神秘。2.1 函数调用栈是怎么一层层垒起来的程序运行时操作系统会为每个线程分配一段栈空间函数每被调用一次就往栈顶压入一个栈帧stack frame。栈帧里装着这次调用的参数、局部变量、以及执行完之后该回到哪一行继续跑的地址。函数返回时栈帧被弹出控制权交还给上一层。拿fact(4)举例。主程序调用fact(4)栈里压入第一帧fact(4)内部要算4 * fact(3)于是暂停自己压入fact(3)接着压入fact(2)、fact(1)。到fact(1)时命中基准情形直接返回 1这一帧弹出。此时栈顶变回fact(2)它拿到 1 之后算出 2 并返回弹出。接着fact(3)算出 6fact(4)算出 24。整个过程是压入四帧再逐层弹出顺序严格遵循后进先出。这个模型解释了一个常见困惑为什么递归函数里基准情形那一行写在最前面但实际最先被完整执行的却是它。因为它位于调用链的最深处只有在所有上层调用都暂停等待时它才会被执行到。2.2 递推与回归两个方向要分开看递归的执行分成两个阶段我叫它们去程和回程。去程是不断缩小问题规模的过程函数不停地调用自己把更小的参数传下去代码里位于递归调用之前的部分在去程中执行。回程是结果逐层返回的过程每层拿到下层的结果后做本层的加工代码里位于递归调用之后的部分在回程中执行。这个区分非常重要因为它决定了你的代码该写在哪。比如打印n到 1如果写成先打印再递归输出是降序如果写成先递归再打印输出就是升序。两者的差别只在于打印语句相对于递归调用的位置。很多回溯类问题比如全排列之所以要在递归调用后面补一句撤销选择就是因为撤销动作必须发生在回程也就是子树处理完之后。我常用的一个调试技巧是在函数的入口和出口各打一条日志把参数和返回值都带上def fact(n, depth0): indent * depth print(f{indent}进入 fact({n})) if n 1: print(f{indent}命中基准返回 1) return 1 result n * fact(n - 1, depth 1) print(f{indent}离开 fact({n})返回 {result}) return result fact(4)跑一遍输出去程和回程会以缩进的形式直观铺开。这比盯着代码脑补有效得多尤其是处理三层以上的递归时。2.3 用调用树手算递归的真实开销斐波那契是最适合用来说明递归开销的例子。fib(n) fib(n-1) fib(n-2)看起来简洁得不行但它的调用次数是指数级增长的。fib(5)的计算过程展开后是这样fib(5)需要fib(4)和fib(3)fib(4)又需要fib(3)和fib(2)而fib(3)在两个分支里都被算了。也就是说同一份子问题被重复计算了多次。n调用总次数约实际耗时感受10177瞬间2021891瞬间30约 270 万明显卡顿40约 3.3 亿基本跑不动50约 400 亿不可行调用次数大致按 φ 的 n 次方增长φ≈1.618所以 n 每加 10计算量大约翻 100 倍。这就是典型的代码看着优雅性能一塌糊涂。解决办法很简单用一个缓存把算过的结果存下来下次直接查表时间复杂度立刻降到 O(n)。Python 里直接用functools.lru_cache一行搞定from functools import lru_cache lru_cache(maxsizeNone) def fib(n): if n 2: return n return fib(n - 1) fib(n - 2) print(fib(100)) # 354224848179261915075秒出不加缓存fib(100)基本不可能算完。加上缓存它连一秒都不用。这个对比我建议每个学递归的人都亲手跑一遍印象会非常深刻。2.4 递归深度与栈溢出的关系每一层递归都要占一个栈帧栈帧有大小线程栈空间有上限两者一撞程序就崩了。Python 会抛RecursionError: maximum recursion depth exceededC 和 C 通常是段错误Java 抛StackOverflowErrorJavaScript 抛RangeError: Maximum call stack size exceeded。Python 默认限制是 1000 层可以查也可以改import sys print(sys.getrecursionlimit()) # 通常是 1000 sys.setrecursionlimit(10000) # 改大但有风险注意把限制调大不等于安全。栈空间是操作系统分配的物理资源设得太大遇上深度失控程序可能直接从抛异常变成进程被系统杀掉连错误信息都看不到。调参之前先确认算法本身的深度上限是可预期的。深度的估算方法很简单如果每次递归参数减 1那处理 n 个元素就需要 n 层n 不能超过安全阈值如果每次规模减半比如二分、归并深度是对数级的 log n哪怕 n 是一亿深度也才二十几层完全不用担心。所以看到一个递归算法先问一句每次规模缩小多少答案直接决定了它安不安全。3. 手把手实现从阶乘到全排列理论说再多不如动手敲。这一节按难度递进从最简单的数值递归到汉诺塔再到回溯类的全排列最后给出递归转迭代的写法。每段代码我都附上了执行过程的说明你跟着跑一遍理解会牢固很多。3.1 阶乘与数组求和最小可跑通样例阶乘是最标准的入门例子基准是n 1返回 1递推是n * fact(n-1)。这里有个容易被忽略的细节基准为什么建议写成n 1而不是n 1因为如果调用方传进来 0 或者负数写成n 1就会一路减下去永远碰不到终止条件。防御性地把边界条件放宽一点是写递归的一个好习惯。def fact(n): if n 1: # 基准情形兼容 0 和负数 return 1 return n * fact(n - 1) def sum_list(nums, i0): if i len(nums): # 基准情形下标越界即空数组 return 0 return nums[i] sum_list(nums, i 1) print(fact(5)) # 120 print(sum_list([1, 2, 3, 4, 5])) # 15数组求和这个例子值得多说一句因为它展示了一种很常见的递归参数设计用下标控制进度。函数签名里多了一个i每次递归时i1当i走到数组长度时命中基准。这种写法的好处是不用真的去切片复制数组避免了额外的内存开销。我见过不少新手写成nums[1:]每次递归代码看着短但每层都新建一个列表n 大一点内存就爆了。3.2 汉诺塔递归思维的最佳教具汉诺塔的规则不用重复了三根柱子若干个大小不同的盘子每次只能移动一个大盘不能压在小盘上目标是把所有盘子从 A 移到 C。很多人第一次看解法是懵的因为怎么移这个问题在 n 大于 3 的时候会变得非常复杂。关键在于换一个提问方式。不要问每一步怎么走而是问如果要完成 n 个盘子的搬运最后一步之前必须处于什么状态。答案很清楚最大的盘子要从 A 移到 C那它上面必须没有别的盘子也就是 n-1 个盘子已经全部从 A 移到了 B然后把最大盘从 A 移到 C最后把 n-1 个盘子从 B 移到 C。于是整个问题拆成了三个动作其中两个是同构的子问题只是起点和终点变了def hanoi(n, src, aux, dst, movesNone): if moves is None: moves [] if n 1: moves.append(f{src} - {dst}) return moves hanoi(n - 1, src, dst, aux, moves) # 把上面 n-1 个挪到辅助柱 moves.append(f{src} - {dst}) # 移动最大的那个 hanoi(n - 1, aux, src, dst, moves) # 把 n-1 个挪到目标柱 return moves result hanoi(3, A, B, C) print(len(result), 步) # 7 步 for step in result: print(step)n 个盘子的最少步数是 2ⁿ - 1这从递推式T(n) 2T(n-1) 1也能直接推出。这里有个实操上的坑上面这段代码里那个moves参数是可变对象如果写成默认参数moves[]那它会成为函数定义时创建的唯一一个列表反复调用函数时结果会累积叠加第二次调用的结果里会混进第一次的内容。正确做法是默认写成None在函数内部再初始化。提示Python 里默认参数只在函数定义时求值一次。但凡默认值是列表、字典、集合这类可变对象都要用None占位再在函数体内创建这是最常见的新手坑之一递归里尤其容易踩。3.3 全排列与子集回溯模板一把梭回溯本质上是带撤销操作的递归。它的三要素是选择、递归、撤销选择。全排列是最典型的例子思路是逐个位置填数填过的数字标记为已用递归到下一层当所有位置都填满时收集结果然后返回上一层把标记清掉。def permute(nums): res [] used [False] * len(nums) path [] def backtrack(): if len(path) len(nums): res.append(path.copy()) # 必须复制否则存的是同一个引用 return for i in range(len(nums)): if used[i]: continue used[i] True # 做选择 path.append(nums[i]) backtrack() # 进入下一层 path.pop() # 撤销选择 used[i] False backtrack() return res print(permute([1, 2, 3])) # [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]这段代码里有三个地方几乎每个人都会在第一次写的时候出错。第一是res.append(path.copy())如果直接 appendpath由于 path 是同一个列表对象后续的 pop 和 append 会把它改得面目全非最后 res 里存的六个结果全都是空的。这个坑的迷惑之处在于打印出来看列表长度是对的只有打开看内容才发现全一样。第二是撤销顺序pop 和used[i] False必须在递归返回之后执行写错了状态就乱了。第三是剪枝条件的位置if used[i]: continue要在做选择之前判断否则会把已经用过的数字又填一遍。子集问题结构一样只是收集结果的时机不同——每进入一层就收集一次当前路径而不是等到路径长度满了才收def subsets(nums): res [] path [] def backtrack(start): res.append(path.copy()) # 每层都收集 for i in range(start, len(nums)): path.append(nums[i]) backtrack(i 1) # 从 i1 开始避免重复 path.pop() backtrack(0) return res把这两个模板吃透绝大多数求所有方案的题目都能套。我的经验是写回溯时先把递归函数的参数和返回值确定下来再想清楚这一层能做什么选择最后补上撤销。三步走下来出错率会低很多。3.4 递归改迭代用显式栈接管调用栈当递归深度不可控时把递归改写成迭代是标准解法。核心思路是既然系统的调用栈帮你保存了中间状态那我自己用一个栈把这个状态存起来就行。以二叉树前序遍历为例递归版本三行就写完了迭代版本需要手动模拟class Node: def __init__(self, val, leftNone, rightNone): self.val, self.left, self.right val, left, right # 递归版 def preorder_rec(root, outNone): if out is None: out [] if root is None: return out out.append(root.val) preorder_rec(root.left, out) preorder_rec(root.right, out) return out # 迭代版显式栈注意右孩子先入栈 def preorder_iter(root): if root is None: return [] out, stack [], [root] while stack: node stack.pop() out.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return out迭代版的顺序有个要点因为栈是后进先出想让左孩子先被处理就得让右孩子先入栈。这个细节在递归版里完全不需要考虑因为递归的调用顺序天然就是从上到下、从左到右。这也说明了一件事递归把顺序这件麻烦事交给了运行时迭代则要求你自己管。两种方式没有绝对优劣只有适不适合当前场景。4. 常见问题与排查实录递归的 bug 有个共同特点现象千奇百怪原因往往就那么几个。这一节把我在实际项目里和带人过程中反复遇到的情况整理出来配上排查方法希望能帮你少走点弯路。4.1 栈溢出和无限递归怎么定位无限递归的症状是程序跑着跑着突然报栈溢出或者干脆卡死不动。定位方法很直接在函数入口打印参数看参数在连续几次调用中是不是呈现有规律的变化。如果发现参数在两个值之间反复横跳比如f(5)调f(4)f(4)又调f(5)那就是递推方向写反了。另有一种情况是参数根本没变。常见于把递归调用写成了f(n)而不是f(n-1)这类笔误在复制粘贴改代码时特别容易发生。还有一种隐蔽的参数在理论上应该变小但因为某处做了额外的运算导致它又变回去了。判断递归是否会终止最可靠的办法是找单调变化量。不管用什么方式每层递归必须有一个量在朝基准情形靠近且不能被反向操作抵消。找不到这个量这个递归就不可信。4.2 结果重复、引用共享与状态污染这类问题的表现是结果数量对但内容不对或者多次调用后结果越攒越多。原因通常有三个。第一个是前面提到的可变默认参数。def f(path[], res[])这种写法那个空列表是全局唯一的所有调用共享同一份内存结果自然越积越多。第二个是收集结果时没有复制。回溯里res.append(path)存的是引用后续 path 变化会连带影响已存的结果。必须path.copy()或list(path)。第三个是全局变量被污染。有时候为了方便把累加变量定义在函数外面递归里直接改它。单次调用没问题但如果这个函数被调用两次第二次的结果会叠加在第一次之上。递归函数最好是纯函数所有中间状态通过参数传入、通过返回值传出避免依赖外部可变状态。4.3 重复计算的识别与记忆化改造当一个递归函数在同一层里调用了自己两次以上就要警惕重复计算。判断方法很简单把递归树画出来看看有没有相同的参数组合出现多次。斐波那契是典型爬楼梯、最少硬币数、最长公共子序列这些也都属于这一类。改造步骤固定先写一个缓存字典或者加lru_cache装饰器在函数开头查缓存命中就直接返回算完结果后写入缓存再返回。改造前后的代码结构几乎不变但复杂度往往从指数级降到多项式级。def coin_change(coins, amount, memoNone): if memo is None: memo {} if amount 0: return 0 if amount 0: return float(inf) if amount in memo: return memo[amount] best min((coin_change(coins, amount - c, memo) for c in coins), defaultfloat(inf)) memo[amount] best 1 if best ! float(inf) else float(inf) return memo[amount]提示记忆化的关键是函数结果只依赖传入参数。如果函数内部还读了外部可变状态缓存就会返回过期结果反而制造新 bug。改造前先确认函数的纯度。4.4 常见问题速查表现象大概率原因排查动作抛栈溢出异常缺少基准情形或递推方向反了打印参数检查是否单调趋近基准程序卡死无输出无限递归但触发条件慢加调用计数上限超过阈值就报错退出结果全是空列表append 了引用没做复制改成path.copy()第二次调用结果翻倍用了可变默认参数或全局变量默认值改 None状态走参数传递结果数量对但顺序乱回溯撤销顺序写错检查 pop 与标记复位是否成对小数据对大数据超时存在重复子问题画递归树找重复参数组合加缓存数组递归内存暴涨每层都在切片复制改用下标参数传递返回值和预期不符递归调用后的加工逻辑写错位置用缩进日志区分去程与回程5. 递归优化与工程实践里的取舍把递归写对只是第一步真正放到项目里还得考虑性能和可维护性。这一节聊几个实际工作中绕不开的点。5.1 记忆化与动态规划的边界在哪很多人会问记忆化递归和动态规划到底是不是一回事。从结果上看它们解决的是同一类问题都把重复子问题的解存下来复用。区别在于方向记忆化递归是自顶向下的从原问题出发遇到子问题就算算过就存动态规划是自底向上的从小规模开始一层层推到原问题。那什么时候用哪个我的经验是如果状态转移关系清晰、依赖顺序好确定用动态规划能省掉递归调用开销也不会有栈深度问题。如果状态之间的依赖关系比较绕直接想递推方程很费劲那就先写记忆化递归把逻辑理顺、跑通测试之后再考虑要不要改成递推形式。先用递归建模、用缓存兜住性能这套组合在比赛和面试里都够用在实际项目里也常常是最省心的方案。需要注意的一点是记忆化递归的缓存键就是函数的参数组合。参数越多缓存的空间开销越大。如果发现参数里有大对象比如整个数组或者一棵子树那就得想想是不是能用编号或者下标来替代否则缓存会吃掉大量内存。5.2 尾递归这件事别指望所有语言都帮你尾递归指的是递归调用是整个函数体里最后一个动作且返回值直接被返回不再参与任何后续计算。理论上这种形式的递归可以被编译器优化成循环只占用一个栈帧从而消除深度限制。但现实是各语言的支持情况差别很大。Scheme、部分函数式语言把尾调用优化写进了规范Scala 有tailrec注解只在确实能优化时通过编译JavaScript 在严格模式下规范里提过但主流引擎的实际实现并不统一Python、Java、C 基本都不做尾调用优化。也就是说你把阶乘写成尾递归形式在 Python 里该爆栈还是会爆。# 尾递归写法Python 里不会因此省下栈空间 def fact_tail(n, acc1): if n 1: return acc return fact_tail(n - 1, n * acc)所以我的建议是如果你用的语言明确支持尾调用优化那可以放心用如果不支持就别指望它该改迭代就改迭代或者把递归深度控制在安全范围内。评估一个方案时可移植性也很重要不能因为本地环境跑得通就认为线上没问题。5.3 深度限制该不该动怎么动才稳调大递归深度限制这件事我的态度是能不动就不动。原因前面提过栈空间是有限的物理资源越界的方式从抛异常变成进程被杀排查难度直接上一个台阶。如果确实需要更深的递归比较稳的做法有几种。一是评估算法本身的深度上限用对数级的分治代替线性级的递减二是把递归改写成显式栈的迭代三是如果语言支持在独立的线程或者协程里跑单独给这块逻辑分配更大的栈空间。还有一种取巧但实用的办法是加一个深度计数参数超过预设值就主动抛出带上下文信息的异常至少能知道是在哪条路径上失控的。def safe_rec(n, depth0, limit900): if depth limit: raise RuntimeError(f递归深度超过 {limit}参数 n{n}) if n 1: return 1 return n * safe_rec(n - 1, depth 1, limit)这个主动护栏在做数据处理脚本时特别有用尤其是输入数据来源不可控的时候能避免整个任务因为一条异常记录直接崩掉。我个人的体会是递归真正的门槛不在语法而在于有没有耐心把执行过程打印出来、一层一层看清楚。很多人学不会是因为一直在脑子里模拟而人脑处理三层以上的嵌套调用本来就吃力。拿张纸把调用树画出来或者在代码里加几行缩进日志花十分钟跑一遍比盯着教程看两小时管用。另一个建议是刚开始写递归时不要追求一行搞定把基准情形单独拎出来写清楚把参数传递链理顺等熟练了再考虑精简。至于什么时候该把递归换成迭代等你在真实项目里被栈溢出教育过一次自然就有判断了。