我带过几个刚入行的同学几乎每个人学递归都会经历同一个阶段看别人的递归代码一眼就懂自己动手写就崩。印象最深的一次是代码评审一个小伙子在二叉树里写了三行递归跑出来结果全对但把同样的思路搬到链表反转上程序直接卡死。他盯着屏幕问我明明是两个几乎一样的结构为什么一个能跑一个不能这个问题问得很好因为它戳到了递归最容易被忽略的地方——大多数人记住的是函数自己调自己这句话而这句话本身几乎不包含任何有用的信息。真正决定一段递归代码能不能跑通的是终止条件设计、规模缩减方式、返回值怎么攒、栈上发生了什么这四件事。这篇内容就是把这四件事一层层剥开从调用栈的物理过程讲到回溯法的成对操作从尾递归为什么在很多语言里得不到优化讲到记忆化和剪枝怎么把一个指数级算法拉回可用范围。不管你是刚接触递归的新人还是写过几百行递归但说不清它为什么能收敛的老手下面这些内容应该都能帮你把这块知识补完整。我会尽量少讲抽象概念多讲实际写代码时手会发生什么、脑子该想什么。1. 把函数调用自己这句话先放下1.1 一个反直觉的观察递归不是循环的替代品很多人第一次学递归时教材会告诉你能用循环的地方尽量用循环递归只是另一种写法。这句话在工程上没错但它会让你误以为递归和循环是同一个层次的工具只是形式不同。实际上这两个东西根本不在一个维度上。循环描述的是控制流的重复它关心的是这一堆语句要执行多少遍递归描述的是问题的自我相似结构它关心的是一个大问题能不能被拆成几个同构的小问题。举个具体的例子。你要计算 1 到 n 的和用循环写是for累加用递归写是sum(n) n sum(n-1)。这两段代码看起来在做同一件事但思维过程完全不同循环的写法里你脑子里想的是我要从 1 走到 n每走一步加一次递归的写法里你想的是n 的和等于 n 加上前 n-1 个数的和。后一种描述里问题本身被重新定义了一次而不是被重复执行了一遍。这个区别在树形结构上会变得极其明显。你要遍历一棵二叉树如果用循环写你得自己维护一个栈手动处理压栈弹栈的顺序如果用递归写你只需要说遍历左子树处理根遍历右子树剩下的交给运行时。不是因为递归更短而是因为二叉树的定义本身就是递归的——一棵树是根节点加上两棵更小的树。当数据结构的定义是递归的时候用递归去处理它几乎总是最省心的选择。所以第一件事是纠正认知递归首先是一种建模方式其次才是一种代码写法。当你拿到一个问题先问自己这个问题能不能用更小规模的它自己来描述如果答案是能递归就是一个自然选择如果答案是我只想重复执行某个动作那循环才是对的。1.2 剥洋葱、查字典以及一个更贴切的排队类比解释递归的常见类比有两个剥洋葱和查字典。剥洋葱说的是层层深入直到核心查字典说的是查递归这个词时解释里又出现了递归。这两个类比都只讲了递归的一半——深入的那一半没讲回来的那一半。我更愿意用排队报数的例子。假设你站在一条长长的队伍里你想知道自己排第几但队伍太长看不到队首。你的做法是拍一下前面的人问你前面有几个人前面的人也不知道于是再拍他前面的人一直传到队首。队首的人知道自己是第一个回答 0然后这个答案一层层往回传每传一层加 1最后传到你这里你就知道自己前面有多少人了。这个例子里包含了递归的全部要素递推关系我的位置 前面那个人的位置 1。终止条件队首的人位置是 0不需要再往前问。回传过程答案不是一次算出来的而是在回程中一层层累加出来的。绝大多数人写递归出错都是因为只想了往下问的部分忘了答案怎么回来的部分。比如在递归函数里把结果累加到一个全局变量上然后忘了在回溯时恢复或者函数执行完了但忘了把子问题的返回值返回给上一层。所以从今天起看到任何递归代码先在脑子里跑一遍下去再上来的完整路径而不是只看它怎么下去的。1.3 递归的三个理解层次我把递归分成三层卡在不同层次的人需要的练习完全不一样。语法层知道函数可以调用自己会写def f(n): return f(n-1)。这一层只要五分钟就能学会但它毫无价值因为这样写出来的函数一定栈溢出。执行层知道每次调用会在调用栈上压入一个新的栈帧函数返回时栈帧弹出局部变量跟着销毁。能在纸上画出压栈弹栈的顺序能解释为什么递归深度过大会爆栈。到这一层你至少能看懂别人写的递归也能自己写一些简单的。思维层能自然地做到假设子问题已经解决然后只关注当前这一层要做什么。写递归的时候不去脑内展开整个调用过程而是相信递归调用会返回正确结果自己只负责把它组合出来。这一层是真正分水岭跨过去之后回溯、分治、动态规划这些依赖递归的算法会一下子变得好写很多。大部分人卡在第二层和第三层之间。他们能画出执行过程但每次写代码都忍不住在脑子里展开整棵树结果小问题还行稍微复杂一点就绕晕了。接下来的章节会分别从这三个层次往下讲。2. 写出正确的递归只需要盯住两件事2.1 终止条件为什么总是写错终止条件是递归的刹车。没有它函数会一直往下调直到栈空间耗尽。但写了终止条件和写对了终止条件是两回事。我见过最典型的错误有三种。第一种是条件方向写反。比如倒序打印数组本该在index 0时返回写成了index len(arr)结果第一次判断就不成立继续往下调直到越界报错或者爆栈。第二种是终止条件不可达。比如二分查找里left right作为继续条件但mid (left right) / 2在整数除法下如果left和right相邻且没正确收缩边界left和mid会一直相等区间再也不缩小。第三种是终止条件写对了但只覆盖了一部分情况比如同时有左右两棵子树的递归只判了左子树为空就返回。正确的终止条件要满足两个要求它一定能被触达以及在它成立时函数能直接给出答案不需要再调用自己。第二点经常被忽略。有的人写了if n 0: return返回空值但上一层拿到这个空值还要参与运算结果整个结果链就断了。终止条件返回的东西必须是最小规模问题的正确答案不是到此为止。2.2 规模缩减才是收敛的保证终止条件负责刹车规模缩减负责让车能开到刹车点。这两件事必须同时成立递归才有意义。所谓规模缩减指的是每一次递归调用传入的参数都必须严格地更靠近终止条件。注意严格两个字。如果某次调用传进去的参数和当前一样函数就会原地打转永远不会到达终止条件。如果参数来回震荡比如f(n)调用f(n1)f(n1)又调用f(n)那就是死循环加栈溢出。举一个真实踩过的坑。有一次我写一个字符串分割函数逻辑是按分隔符把字符串切成两半分别递归处理。终止条件是len(s) 1。看起来没问题但如果分隔符出现在开头切出来的前半部分是空字符串后半部分和原字符串一样长。于是递归参数没有变小程序在同一个字符串上无限打转。修复方法是在切分后显式跳过空片段保证每次递归的字符串长度严格变小。这个例子说明规模缩减不是看一眼代码就能确认的你得确认在最坏输入下参数依然严格缩小。比如上例中分隔符在开头就是最坏输入。平时写递归我建议在函数开头加一句断言把当前规模和上一次比较一旦发现没有缩小就直接抛错这样问题会立刻暴露在第一次运行而不是等到线上爆栈。2.3 一个三句话的自检流程写完之后不用急着跑先问自己三个问题检查项具体问法不通过时的症状终止条件可触达吗从当前参数出发每次调用都更接近它吗栈溢出、程序卡死最小情形返回对了吗参数取到终止值时返回值是不是题目要求的最小答案结果偏大偏小、返回空值子问题的返回值被用上了吗递归调用的结果有没有参与本层的组合运算结果永远是初始值这三个问题覆盖了我见过的九成递归 bug。第三个问题特别值得展开因为很多人写了递归调用但忘了用返回值。比如求二叉树最大深度写成def depth(node): if node is None: return 0 depth(node.left) # 返回值被丢掉了 depth(node.right) return 1每个节点都返回 1结果永远是 1。函数没报错也不爆栈就是结果不对。这种 bug 最难查因为它没有崩溃信号只能靠对比结果发现。3. 调用栈视角递归在内存里到底发生了什么3.1 每个栈帧都存着一份现场记录理解递归的执行过程必须理解调用栈。在一段程序运行的时候运行时系统会维护一个叫做调用栈的区域每发生一次函数调用就往上压入一个栈帧函数返回时栈帧弹出。栈帧里主要装着四样东西传入的参数、函数内部的局部变量、返回地址也就是我返回之后该回到哪一行继续执行以及一些运行时的元信息。递归之所以和普通函数调用不同是因为同一个函数的多个栈帧会同时存在于栈上。每一个栈帧都带着自己那一层的参数和局部变量互不干扰。这一点非常关键它解释了为什么递归函数里的局部变量不需要担心被上层修改——每一层都是独立的复制。同时它也解释了一个常见困惑为什么递归函数里用i作为循环变量会出问题。如果你在递归函数里用一个外层定义的i那所有层级共用同一个i一层的修改会影响其他层。正确的做法是把需要的状态当作参数往下传或者当作局部变量重新声明。3.2 手动模拟一次阶乘的完整过程光说原理不够直观我们把factorial(4)走一遍。函数定义是def factorial(n): if n 1: return 1 return n * factorial(n - 1)执行过程可以拆成下潜和上浮两个阶段。阶段当前调用栈内保存的内容自底向上待办事项下潜 1factorial(4)fact(4)等 fact(3) 的结果然后乘 4下潜 2factorial(3)fact(4), fact(3)等 fact(2) 的结果然后乘 3下潜 3factorial(2)fact(4), fact(3), fact(2)等 fact(1) 的结果然后乘 2触底factorial(1)fact(4), fact(3), fact(2), fact(1)命中终止条件返回 1上浮 1回到 fact(2)fact(4), fact(3), fact(2)1 * 2 2返回 2上浮 2回到 fact(3)fact(4), fact(3)2 * 3 6返回 6上浮 3回到 fact(4)fact(4)6 * 4 24返回 24这张表里最值得注意的是待办事项那一列。函数之所以要保存现场就是因为它在等下层的返回值还没法完成自己的工作。如果某一层的返回值不依赖下层比如尾递归那这一层就不需要保存现场栈帧可以复用这就是尾递归优化的原理。3.3 栈溢出是怎么发生的以及递归深度的实际估算栈溢出Stack Overflow不是内存不够而是调用栈这个特定区域被用满了。每个栈帧占多少字节取决于参数个数、局部变量数量和编译优化通常在几十到几百字节之间。栈的容量则取决于语言和运行环境。不同环境下递归深度的差异很大这个表可以给你一个直觉环境默认栈限制大致安全递归深度调整方式Python解释器内建限制约 1000 层修改递归限制需谨慎同时要加大线程栈Java每线程栈约 512KB 到 1MB约 5000 到 10000 层启动参数调整栈大小C/C主线程栈通常 1MB 到 8MB约 1 万到 10 万层编译或链接参数调整栈大小JavaScript各引擎不同约 1 万层左右一般靠改写为迭代这里有个容易踩的坑有人发现 Python 栈溢出了就去把递归限制调到十万结果程序直接段错误崩溃。原因是 Python 的递归限制只是一道软闸门真正决定能不能撑住的是底层 C 栈的容量。绕过软闸门但没加大真实栈空间程序会以更难看的方式挂掉。正确做法是评估数据规模如果输入可能达到几万层就应该改成迭代写法或者用显式栈手动管理而不是硬撑递归深度。4. 递归的几种形态气质完全不同4.1 线性递归一条链走到黑线性递归指的是每次调用只产生一个递归分支调用链是一条直线。阶乘、链表遍历、字符串反转、数组求和都属于这一类。它的特点是递归深度等于问题规模时间复杂度通常也是线性的。线性递归最好理解但也最容易和尾递归混淆。区分方法是看返回值有没有待完成的操作。return n * factorial(n-1)里乘法这个操作要等下层返回后才做所以它不是尾递归栈帧必须保留。而return factorial(n-1, acc * n)把累乘的结果通过参数往下传当前层没有任何待办这就是尾递归。4.2 树形递归分叉带来的指数爆炸当一个递归函数内部调用自己两次或更多次调用结构就变成了一棵树。最典型的是斐波那契数列def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)这个写法优雅得让人不忍心改但它慢得离谱。原因是大量子问题被重复计算。fib(5)需要fib(4)和fib(3)而fib(4)又需要fib(3)和fib(2)fib(3)被算了两次。往下推重复的程度会指数增长。fib(40)的递归调用次数大约是 3 亿次在普通机器上要跑十几秒而fib(50)就基本跑不完了。汉诺塔也是树形递归但它没有重复子问题因为每个子问题的规模都不同。汉诺塔的总步数是 2 的 n 次方减 1n 等于 64 的时候大约是 1844 亿亿步。所以树形递归不一定都慢关键看子问题有没有重叠。4.3 尾递归为什么很多语言根本不给你优化尾递归的定义是递归调用是函数体里最后一个动作它的返回值直接作为本函数的返回值没有任何后置运算。满足这个条件时理论上可以复用当前栈帧把递归变成事实上的循环空间复杂度从 O(n) 降到 O(1)。但现实是主流语言里只有一部分做了这个优化。Scheme、部分函数式语言是强制要求Scala 需要显式标注Java、Python、JavaScript 的主流实现都不做尾递归优化。Python 的作者还专门说过不打算加理由是尾递归优化会破坏调用栈的调试信息而且他认为把递归写成循环更清晰。所以写 Python 的时候看到尾递归不要指望它省内存。你要么手动改成循环要么接受递归深度限制。下面两段代码等价后者的写法可以直接改成循环# 普通递归深度 O(n) def sum_to(n): if n 0: return 0 return n sum_to(n - 1) # 尾递归形式但仍会占 O(n) 栈空间 def sum_to_tail(n, acc0): if n 0: return acc return sum_to_tail(n - 1, acc n) # 等价循环O(1) 空间 def sum_to_loop(n): acc 0 while n 0: acc n n - 1 return acc4.4 互递归与回溯递归真正发挥威力的地方互递归指的是两个或更多函数互相调用。最简单的是判断奇偶def is_even(n): if n 0: return True return is_odd(n - 1) def is_odd(n): if n 0: return False return is_even(n - 1)这种写法看起来是玩具但在解析器里是标配。写一个四则运算表达式解析器时通常会有parse_expr调用parse_termparse_term调用parse_factorparse_factor遇到括号又会调回parse_expr。这种按语法层级拆分的互递归结构非常清晰比塞在一个大函数里维护状态机要可读得多。回溯是递归最有价值的一种用法。它的骨架是固定的在当前层做选择向下递归递归返回后撤销选择。全排列、组合求和、N 皇后、数独求解、迷宫寻路全都是这个骨架。def permute(nums): result [] path [] used [False] * len(nums) def backtrack(): if len(path) len(nums): result.append(path[:]) # 注意要复制 return for i in range(len(nums)): if used[i]: continue path.append(nums[i]) used[i] True backtrack() used[i] False # 撤销选择 path.pop() # 撤销选择 backtrack() return result这段代码里有两个地方新手最容易错。一是result.append(path[:])必须复制否则后续path.pop()会把已经存进结果里的列表也改掉。二是撤销操作必须成对且位置正确忘记used[i] False会导致后续分支无法使用某些数字结果数量骤减但程序不报错。5. 把递归改写成迭代的三种路径5.1 尾递归转循环有固定套路如果递归是尾递归形式改写几乎是机械的。步骤是把累加器参数提出来变成循环外变量把终止条件变成while的继续条件把递归调用变成更新变量。用二叉树中序遍历来举例会更实际。中序的递归写法是def inorder(node): if node is None: return inorder(node.left) visit(node) inorder(node.right)这个不是尾递归因为inorder(node.left)返回后还要做visit和右子树。但是它的结构足够规律用显式栈可以完全等价改写。5.2 用显式栈模拟递归的完整流程显式栈写法的核心思路是把待办事项从运行时的调用栈搬到你自己维护的数据结构里。中序的本质是一路向左压栈弹出时访问然后转向右子树def inorder_iterative(root): stack [] cur root while cur or stack: while cur: stack.append(cur) cur cur.left cur stack.pop() visit(cur) cur cur.right前序遍历更简单因为访问发生在进入节点的时候压栈顺序反过来即可def preorder_iterative(root): if not root: return stack [root] while stack: node stack.pop() visit(node) if node.right: stack.append(node.right) # 先压右 if node.left: stack.append(node.left) # 后压左先弹出这里有个细节值得说压栈顺序必须和访问顺序相反。因为栈是后进先出你想先访问左孩子就得把左孩子后压进去。这个顺序第一次写的人十有八九会搞反验证方法很简单拿一个只有两个孩子的根节点手工跑一遍。5.3 什么情况下我坚持用递归虽然迭代确实省内存、没有深度限制但有几种场景我会毫不犹豫地选择递归。第一种是结构本身递归的场景比如树的遍历、图的深度优先搜索、表达式解析、JSON 序列化。用迭代写这些代码你的注意力会被大量压在栈的操作上反而看不清算法本身。第二种是回溯法。回溯的本质是做选择—探索—撤销选择这个模式需要天然的前后对称性。用递归写撤销代码紧跟在递归调用后面一眼就能看出配对关系。改成迭代你得手动模拟每一层的选择状态代码量翻倍还不容易维护。第三种是分治算法比如归并排序、快速排序、最近点对。分治的核心是拆开—分别解决—合并递归的分层结构和分治的逻辑层级是一一对应的。第四种是深度可控的场景。如果我已经知道数据的最大深度是几百层那递归的开销完全可以忽略代码可读性带来的收益远大于那点栈空间。判断标准可以总结成一句话如果递归的层级和问题的结构天然对应就用递归如果递归只是为了遍历一个线性序列那就用循环。6. 递归的性能黑洞与两把解药6.1 斐波那契为什么慢得超出直觉前面提过fib(40)要跑几百万到几亿次调用这里把数字算清楚一点。递归版的调用次数记作 T(n)有 T(n) T(n-1) T(n-2) 1。这个递归式的增长速率约等于 1.618 的 n 次方黄金比例。具体来说fib(30)约 130 万次调用fib(40)约 1.6 亿次fib(45)约 18 亿次。每增加 5 层调用次数大约翻 11 倍。这就是典型的重复子问题问题。整棵树里fib(2)被算了无数次fib(3)也被算了无数次而这些结果每次都是相同的。解决办法只有一个方向把算过的结果记下来。6.2 记忆化的两种实现与各自代价记忆化的本质是拿空间换时间。最简单的实现是用字典缓存def fib_memo(n, memoNone): if memo is None: memo {} if n 1: return n if n in memo: return memo[n] memo[n] fib_memo(n - 1, memo) fib_memo(n - 2, memo) return memo[n]优化后每个 n 只算一次时间复杂度降到 O(n)空间是 O(n)。fib(1000)也能瞬间出结果。Python 里还可以用标准库的缓存装饰器省去手写字典from functools import lru_cache lru_cache(maxsizeNone) def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)但记忆化不是免费的。第一它改变了空间复杂度如果状态空间很大比如状态由多个参数组合而成缓存可能吃掉几百兆内存。第二它要求子问题结果与调用路径无关如果递归过程中依赖了外部可变状态缓存会给出错误结果。第三缓存不能用在有环的状态图上否则会读到还没算完的中间值。我踩过的一次坑是给一个带路径约束的搜索函数加了缓存函数的参数里有一个已访问节点集合我一时偷懒没把它放进缓存键里结果不同路径下的结果被互相覆盖程序给出了完全错误的最优解而且没有任何报错。后来我把所有影响结果的参数都拼进键里才修好。这个教训是缓存键必须覆盖所有影响返回值的输入一个都不能漏。6.3 剪枝让回溯法从暴力走向可用回溯法如果老老实实枚举所有分支复杂度通常是指数级。剪枝就是在递归往下走之前提前判断这条分支不可能产生有效结果直接砍掉。举个组合求和的例子给定候选数组和目标值找出所有和为目标的组合。如果没有剪枝每个候选数字都有选或不选两种状态总分支数是 2 的 n 次方。加上两个剪枝之后会快很多def combination_sum(candidates, target): candidates.sort() # 排序是剪枝的前提 result [] path [] def backtrack(start, remain): if remain 0: result.append(path[:]) return for i in range(start, len(candidates)): if candidates[i] remain: break # 剪枝一后面的更大全部不可能 if i start and candidates[i] candidates[i - 1]: continue # 剪枝二跳过同层重复元素 path.append(candidates[i]) backtrack(i, remain - candidates[i]) path.pop() backtrack(0, target) return result第一个剪枝依赖排序既然数组已经从小到大排好当前数字已经超过剩余目标那它后面的数字只会更大整条分支可以直接砍断。这里用break而不是continue因为后面全都不可能。第二个剪枝处理重复元素同一层里如果当前数字和上一个数字相同那么以它为起点产生的组合一定和上一个重复直接跳过。注意判断条件是i start而不是i 0这个区别很关键——i start保证只跳过同一层的重复而不会错误地跳过不同层使用相同数字的情况。这两个剪枝能把实际运行时间降低一到两个数量级具体取决于数据里重复元素的占比。7. 四个必须亲手写一遍的递归练习7.1 汉诺塔检验你是否真的会信任递归汉诺塔的规则是从 A 柱把所有盘子搬到 C 柱每次只能移动一个大盘不能放在小盘上面。递归思路是这样的想把 n 个盘子从 A 搬到 C先把上面 n-1 个搬到 B把最大的盘子搬到 C再把 B 上的 n-1 个搬到 C。def hanoi(n, src, dst, aux): if n 1: print(fmove disk 1 from {src} to {dst}) return hanoi(n - 1, src, aux, dst) print(fmove disk {n} from {src} to {dst}) hanoi(n - 1, aux, dst, src)这个函数只有六行但它难住了无数人。难的地方不在代码而在心态——你要相信hanoi(n-1, src, aux, dst)这个调用真的能把 n-1 个盘子搬到 B 上而不去追踪它内部怎么搬的。一旦你试图在脑子里展开所有移动步骤n 稍微大一点就会彻底晕掉。汉诺塔的移动次数是 2 的 n 次方减 1这个结论可以反过来验证代码n1 是 1 次n2 是 3 次n3 是 7 次。写完后手算 n3 的输出来对数能确认三个参数的位置有没有传错。参数顺序是这类递归最容易错的地方很多人的第一版都会把辅助柱和目标柱搞反。7.2 全排列回溯法的标准骨架全排列的代码在第 4 节已经给过这里补充几个容易忽略的细节。第一个细节是空数组和单元素数组的边界。permute([])应该返回[[]]而不是[]因为空集的全排列是包含一个空排列的集合这在数学上更自然也避免调用方再做特判。第二个细节是判重。上面那段代码默认数组里没有重复元素。如果数组是[1,1,2]直接跑会输出重复的排列。修法是在循环里加一句如果当前元素和前一个相同且前一个还没被使用就跳过。判断前一个没被使用很重要因为它能区分同一层的重复分支和更深层的合法重复使用。第三个细节是性能。path[:]每次都要复制整个列表如果只需要输出数量而不需要具体排列可以用计数器代替省掉大量内存分配。7.3 二叉树遍历递归最自然的战场二叉树的前中后序遍历是学习递归的绝佳素材因为三个函数只差一行的位置def preorder(node, out): if not node: return out.append(node.val) preorder(node.left, out) preorder(node.right, out) def inorder(node, out): if not node: return inorder(node.left, out) out.append(node.val) inorder(node.right, out) def postorder(node, out): if not node: return postorder(node.left, out) postorder(node.right, out) out.append(node.val)三个函数唯一的区别是out.append放在哪个位置。前序放在进入节点时中序放在左子树处理完之后后序放在两棵子树都处理完之后。理解了这个你就理解了递归函数里当前层代码的位置决定了执行时机——递归调用之前执行的是下潜阶段之后执行的是上浮阶段。还有一个常用的技巧是把遍历写成返回值的风格而不是传一个 out 参数进去def depth(node): if not node: return 0 return max(depth(node.left), depth(node.right)) 1这种风格更符合信任递归的思路我不关心子树内部我只知道depth(node.left)会给我左子树的高度我拿它做一次比较加一任务完成。7.4 归并排序与快排分治的两种不同脾气归并排序的分治体现在先拆再合把数组从中点切成两半分别排序然后合并两个有序数组。合并不是递归调用但对有序数组的合并是一个额外的辅助过程。def merge_sort(arr): if len(arr) 1: return arr mid len(arr) // 2 left merge_sort(arr[:mid]) right merge_sort(arr[mid:]) return merge(left, right) def merge(a, b): result [] i j 0 while i len(a) and j len(b): if a[i] b[j]: result.append(a[i]); i 1 else: result.append(b[j]); j 1 result.extend(a[i:]) result.extend(b[j:]) return result快速排序的分治体现在先分再治选一个基准值把数组分成小于基准和大于基准两部分然后递归处理这两部分。分割过程是在递归之前完成的这是它和归并排序最大的区别。def quick_sort(arr, lo, hi): if lo hi: return p partition(arr, lo, hi) quick_sort(arr, lo, p - 1) quick_sort(arr, p 1, hi)这两个算法的终止条件写法值得对比。归并用len(arr) 1快排用lo hi。快排这个条件看起来简单但如果partition返回的p等于lo下一个递归的区间[lo, p-1]会变成空区间被终止条件拦住而[p1, hi]是缩小的所以整体能收敛。但如果partition实现有问题比如基准值选得不好导致某一边区间和原区间一样大就会无限递归。这就是为什么快排的三数取中和随机化基准不只是性能优化也是正确性保障。8. 调试递归的实战手法8.1 缩进打印法最土但最有效递归代码出问题时光看代码很难判断是哪一层出了错。最直接的办法是在函数入口和出口打印带缩进的日志把调用深度可视化def solve(n, depth0): indent * depth print(f{indent}enter solve({n})) if n 0: print(f{indent}return 0) return 0 res n solve(n - 1, depth 1) print(f{indent}exit solve({n}) {res}) return res跑一遍solve(3)你会看到清晰的缩进结构什么时候下潜、什么时候上浮、每层的返回值是多少一目了然。这个方法我用了很多年比打断点快得多尤其是在调试那种结果对但顺序不对的问题时。需要注意的是打印必须放在正确的位置。入口打印在递归调用之前出口打印在递归调用之后。如果只打印入口你只能看到下潜过程看不到结果是怎么攒起来的。8.2 画递归树把复杂度问题可视化当程序性能不达标时把递归树画出来能立刻暴露问题。以斐波那契为例画到第四层你就会发现同一个节点反复出现。当你在图上看到重复节点就知道该上记忆化了。画树的时候有个小技巧只画每一层的参数值不画函数名。比如fib(5)的下一层是4和34下面又出现3和2一眼就能看出3重复了。参数值相同的节点就是重复子问题这是判断能不能记忆化的直接依据。另一种情况是图上节点数量爆炸但几乎没有重复比如汉诺塔。这时候记忆化没用只能从算法本身入手看有没有数学公式可以直接推导。8.3 递归错误对照表症状最可能的原因排查方法程序无输出卡死或爆栈终止条件不可达或规模没有缩小打印每层参数看是否逼近终止值结果偏小或数量不对撤销操作缺失或返回值被丢弃检查回溯的成对操作、检查递归返回值是否参与运算结果里出现重复项同层重复分支没跳过排序后加同层去重判断结果里的数据被意外修改存结果时没复制可变对象用切片或深拷贝保存快照同样的输入结果不一致递归中依赖了外部可变状态把状态改成参数传递或每次调用前重置性能随规模爆炸式下降存在重复子问题画递归树检查重复参数9. 递归思维到底怎么练出来9.1 从假设子问题已经解决开始这是递归思维里最难跨的一步也是最有效的一步。具体做法是写递归函数的时候先明确函数签名和它的含义然后假设所有更小规模的调用都能返回正确结果自己只负责处理当前这一层。用二叉树最大深度举例。你先定义depth(node)的含义是以 node 为根的子树最大深度。然后假设depth(node.left)和depth(node.right)都是对的那么当前层要做的只是取两者较大值加一。整个过程中你完全不展开子树内部只在当前层思考。这个思路在数学上叫强归纳法在编程里就是所谓的递归的信仰之跃。很多人过不去这一关是因为他们习惯性地想追踪每一层的执行细节。追踪在小规模时可行规模一大就崩了。你要做的是把它当成一个已经验证过的黑盒只管调用。9.2 用小规模数据手算验证你的递推关系信任递归不代表不验证。正确的做法是设计完递推关系后手算 n1、n2、n3 三个规模看看结果对不对。以汉诺塔为例n1 应该输出 1 条移动指令n2 应该 3 条n3 应该 7 条。如果你手算出的结果不符合 2 的 n 次方减 1那说明参数位置传错了。手算规模小的时候不容易出错而且能快速定位问题。这个习惯能帮你省下大量调试时间。我现在的流程基本是设计递推关系手算前三个规模写代码跑测试。如果手算就错了代码根本不用写。9.3 每天写一道先写递归再写优化练习递归最有效的方法不是看题解而是自己写。具体建议是拿到一个问题先用最朴素的递归写出来哪怕它是指数复杂度的然后跑小数据验证正确性最后再加上记忆化或者剪枝做优化。这个顺序很重要。先追求正确再追求高效能让你把注意力分开。如果一上来就想写最优解很容易在还没搞清递推关系的时候就陷进优化细节里。练习的题目可以按难度递进先做数组求和、字符串反转这类线性递归再做阶乘、斐波那契这类有重复子问题的然后做全排列、子集、组合求和这类回溯最后做 N 皇后、数独、单词搜索这类带约束的搜索。每类做五到十题手感就会稳定下来。9.4 一个我经常用的小检查写完之后我习惯问自己一句把规模缩到最小会发生什么。比如递归函数处理数组我就想如果数组只剩一个元素会走到哪儿再想如果数组是空的会走到哪儿。这两个最小情形覆盖了绝大多数边界 bug。还有一句递归调用的次数是几。看一眼函数体里有几个递归调用就知道调用结构是一条线还是一棵树。一个调用是线性两个是树形循环里加一个递归就是指数级的搜索。这个数量直接决定了复杂度也决定了要不要上记忆化。关于递归我个人在实际操作中最深的体会是它不是靠背模板学会的而是靠一次次手画调用过程、一次次把栈溢出跑出来、一次次在纸上算小规模数据积累出来的。真正的转折点是你开始相信那个还没展开的子问题会返回正确答案然后把注意力收回到当前这一层。剩下的优化手段——尾递归改写、显式栈、记忆化、剪枝——都只是在这套思维已经稳固之后的工程补充。另外分享一个我自己常用的排查习惯任何递归函数写完后先拿空输入和一个元素的输入各跑一遍这两个用例能拦下大部分边界问题比事后再去读代码找 bug 快得多。