学过算法的人几乎没有谁能绕开递归与分治策略这道坎。我第一次看到递归代码时总觉得它像魔术一个函数还没算完竟然又在调用自己最后还能返回一个正确结果。后来把调用栈和递推方程在纸上画出来才意识到它背后没有什么玄学只是把“大问题拆成小问题、小问题再拆成更小问题”这件事用代码描述得比较直接而已。这篇文章想把我在学习《算法设计与分析》时对递归与分治策略的理解整理出来包括调用栈模型、分治的适用前提、归并排序/快速排序/最近点对三个经典案例、递推式推导以及工程中常见的栈溢出和重复计算问题。内容适合正在学算法设计、准备面试或者希望把递归基础打扎实的读者我会尽量写得接地气一些少说废话。1. 递归不是“函数调用自己”这么简单三要素与执行模型1.1 递归三要素基准、递推关系、收敛性一个递归函数是否成立只需要看三件事。第一是基准情形例如阶乘里n 0时直接返回 1。基准情形必须是不需要继续递归就能直接得到的答案很多人写递归爆栈就是因为基准情形漏掉了某些输入。比如求阶乘时没有处理n 0程序就会一直减下去永远无法进入返回分支。第二是递推关系当前规模的答案必须能由更小规模的答案计算出来阶乘里n! n * (n-1)!就是典型的递推关系。第三是收敛性每次递归调用都要让问题规模朝基准方向严格变小。如果递归逻辑写成“先调用再减小参数”或者参数根本没变化程序就会无限递归下去。这三条本质上对应了数学归纳法基准情形是归纳基础递推关系是归纳步骤收敛性保证归纳能覆盖所有输入。所以我一直建议初学者把递归和数学归纳法放在一起理解而不是单纯背代码。判断一个递归写法对不对最有效的方式就是问自己三个问题基准情形覆盖所有终止条件了吗递推关系真的把问题规模缩小了吗缩小后是否一定能到达基准情形如果答案都是肯定的递归逻辑基本不会出大错。1.2 调用栈与栈帧递归如何一步步展开每次函数调用都会在系统栈上压入一个栈帧栈帧中保存了局部变量、返回地址等信息。递归调用也一样只不过调用的是同一个函数所以栈帧会一层一层叠起来。计算factorial(5)时程序会先依次调用factorial(4)、factorial(3)、factorial(2)、factorial(1)、factorial(0)然后从factorial(0)开始逐层返回。整个过程中系统栈最多同时存在 6 个栈帧。栈帧的问题在于它有真实的内存代价。每个栈帧哪怕只有几百字节当递归深度达到十万、百万时总内存消耗就会非常大。Python 默认的递归深度限制是 1000原因就在于此。很多语言不显式限制递归深度而是受系统栈大小限制默认可能只有几 MB 到几十 MB。因此递归深度是否能接受应该是写递归代码之前就估算的问题而不是等出现栈溢出再回头改。对递归函数做深度估算核心是看“最坏情况下会连续调用多少次”而不是“总共调用多少次”。树形递归虽然总调用次数很多但只要同一时刻的嵌套深度不大系统栈压力就有限。1.3 线性递归、树形递归与尾递归的区别根据递归调用的形态可以把递归粗略分成三类。线性递归指函数每次最多只发起一个递归调用计算过程像一条线典型例子是阶乘。树形递归指函数在 return 语句里出现多个递归调用例如fib(n) fib(n-1) fib(n-2)调用展开后是一棵二叉树。树形递归并不总是坏事归并排序在递归阶段是两个子问题但它每个子问题只被求解一次复杂度是 O(nlogn)而朴素斐波那契的同一子问题被反复求解才导致指数级复杂度。尾递归是另一类需要单独说明的形态。尾递归指递归调用是函数的最后一个操作调用结束后不需要再做任何运算。阶乘写成return n * factorial(n-1)不是尾递归因为回来之后还要乘 n但写成factorial(n, acc) factorial(n-1, acc*n)就是尾递归。尾递归在 GCC、Rust 等编译型语言中可能被优化成循环从而避免栈增长但 Python 解释器一般不处理尾递归所以不要指望用 Python 的尾递归写法避开栈溢出。如果某个递归问题可以用尾递归表达又担心栈深度最稳妥的方案是直接改循环而不是赌编译器行为。2. 分治策略到底在“治”什么子问题独立性、合并代价与笨办法的对比2.1 分治的四个环节基准、分解、递归求解、合并分治策略通常被概括为“分解、求解、合并”三个步骤但我更喜欢把它拆成四个环节确定基准、分解问题、递归求解、合并结果。之所以把“合并结果”单独拎出来是因为很多问题的难点根本不在分解而在合并。归并排序里分解只是从数组中间切一刀递归求解也只要对左右两半分别排序真正考验人的是把两个有序数组合并成一个有序数组。合并写不好整个分治策略就失去了意义。最近点对问题同理跨中线的点怎么合并比较才是这类题目真正的考点。分治策略的效率也不是自动得来的。它建立在“子问题独立”和“合并代价可控”两个前提上。如果合并需要扫描大量数据导致f(n)接近 O(n²)那么最终复杂度可能比暴力求解还差。所以拿到一个能分治的问题先别急着写递归而是应该先估算递推式T(n) aT(n/b) f(n)中的a、b、f(n)看看合并阶段的代价是不是主导项。如果合并代价太离谱就要换思路。2.2 子问题重叠与子问题独立分治和动态规划的边界分治要求子问题相互独立意思是一个子问题的求解过程不会改变另一个子问题所需的数据也不会重复计算完全相同的子问题。如果子问题有重叠分治策略就会做大量重复工作。朴素递归的斐波那契数列是典型反例fib(n)会同时调用fib(n-1)和fib(n-2)而fib(n-2)本身又被fib(n-1)调用同一个输入的子问题被反复求解复杂度达到指数级。这种情况下应该改用记忆化递归或者直接用自底向上的循环而不是套分治标签。判断方法很简单把递归树画出来看有没有完全相同的节点。如果存在大量重复节点就优先考虑动态规划如果每个节点都只出现一次子问题之间互不影响才可能用分治。很多初学者把“递归分治”和“递归记忆化”混为一谈觉得都是“拆小再算”但两者的前提完全不同。分治强调子问题独立记忆化恰恰是为子问题重叠而生的。这个区别在面试里很容易被追问也是理解后续很多算法的分水岭。2.3 二分查找是“减治”不是完整分治课程里经常把二分查找放在分治这一章但严格来说二分查找属于减治而非完整分治。分治是把问题拆成多个子问题分别求解后合并结果减治则是每轮消去一部分规模最后只剩一个可解的子问题。二分查找每轮只进入左半或右半根本没有合并阶段所以它的递推式是T(n) T(n/2) O(1)解得 O(logn)。明白这个区别最大的价值在于让你意识到“合并”在分治中的分量。如果一个递归分解后不需要合并问题往往更简单通常可以写成循环优化。比如二分查找改成 while 循环后时间和空间表现都更好。如果一个问题既需要分解又需要合并那大概率才是真正的分治问题比如归并排序和最近点对。把“减治”和“分治”分开不是说二分查找不能在这一章学而是让你知道递归分解后有哪些走向要么合并要么不合并不合并时一定要想想有没有更简单的迭代写法。3. 三个经典分治案例拆解归并排序、快速排序与最近点对3.1 归并排序稳定、O(nlogn) 与额外空间的取舍归并排序是我认为最好理解的分治案例因为它把“分解”和“合并”分得很清楚。核心代码可以这样写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(left, right): i j 0 res [] while i len(left) and j len(right): if left[i] right[j]: res.append(left[i]) i 1 else: res.append(right[j]) j 1 res.extend(left[i:]) res.extend(right[j:]) return res时间复杂度推导很直观递归深度是 logn每一层所有合并操作合计 O(n)总复杂度 O(nlogn)。它不会因为输入已经有序或逆序而改变性能因为每次都是平均切分。空间复杂度是 O(n)因为合并时创建了额外数组。如果要求原地归并复杂度会显著上升或者代码很复杂所以标准归并排序不是原地算法。工程中归并排序更适合链表排序、外部排序以及需要稳定排序的场景。很多语言内置排序并不是简单归并比如 Python 的list.sort()用的是 TimSort但核心思想里依然有归并的影子。3.2 快速排序枢轴选择决定生死快速排序同样用分治但它的核心是 partition而不是合并。经过 partition 后枢轴元素已经落在最终位置不需要再对两个子数组做合并。基本实现如下def quick_sort(arr, low, high): if low high: return pivot partition(arr, low, high) quick_sort(arr, low, pivot - 1) quick_sort(arr, pivot 1, high) def partition(arr, low, high): pivot arr[high] i low - 1 for j in range(low, high): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] arr[i 1], arr[high] arr[high], arr[i 1] return i 1平均复杂度 O(nlogn)最坏情况 O(n²)。最坏情况发生在每次 partition 都选到最小或最大元素比如数组已经有序时固定取最后一个元素做枢轴每次只能排除一个元素递归树彻底失衡。正因为如此工程实现里很少直接取固定位置而是用随机枢轴或三数取中法降低退化概率。快速排序是原地排序实际运行往往比归并排序更快但它的排序结果不稳定。如果面试里碰到排序题一定要能说清楚“快排的最坏情况是什么、怎么缓解”否则很容易被认为是背模板。3.3 最近点对合并阶段才是真正的难点二维最近点对问题是指给定平面上 n 个点求欧氏距离最近的两个点。暴力做法是 O(n²) 枚举所有点对分治算法能达到 O(nlogn)。整体思路是按 x 坐标排序取中点分成左右两半递归求出左右两侧的最小距离 dL 和 dR令d min(dL, dR)。然后检查两个点分别位于左右两侧的情况这时只需要考虑距离中线一定范围内的点再按 y 坐标排序对每个点检查后面有限个点。这里最关键的证明是在宽度为 2d 的带状区域内如果任意点对距离不小于 d那么每个点只需要与后续常数个点比较所以合并阶段可以控制在 O(n) 或 O(nlogn)。如果合并阶段写成双重循环把所有点都互相比较复杂度会立刻退化到 O(n²)分治就失去了意义。这个案例给我的启发是分治的收益不只来自“分”更来自“治”。合并阶段有没有数学上的裁剪直接决定算法能不能从 O(n²) 提升到 O(nlogn)。学习最近点对时不要只背代码一定要亲手推一遍“为什么每个点只需要比较常数个邻居”。4. 主定理之外自己手推递推式三种情形与常见陷阱4.1 主定理三种情形的直觉处理分治递推式T(n) aT(n/b) f(n)最常用的工具是主定理。这里a是子问题数量n/b是子问题规模f(n)是分解和合并的代价。主定理通过比较f(n)与n^(log_b a)的关系给出结论条件复杂度f(n) O(n^(log_b a - ε))ε 0T(n) Θ(n^(log_b a))f(n) Θ(n^(log_b a) log^k n)k ≥ 0T(n) Θ(n^(log_b a) log^(k1) n)f(n) Ω(n^(log_b a ε))且a f(n/b) ≤ c f(n)T(n) Θ(f(n))直觉其实很简单n^(log_b a)可以理解为递归带来的基础开销f(n)是根节点及其它节点的合并开销。谁的幂次大谁就决定复杂度。相等时多出一个对数因子。掌握主定理不需要背很多题只需要理解这三个分支分别对应“递归主导”“两者均衡”“合并主导”三种情况。4.2 套主定理最容易翻车的三个地方死记主定理容易在三个地方出错。第一比较的是“多项式意义下”的大小不是直接比较数值。比如f(n) n与n^(log_2 2) n相等属于情形二但f(n) n/log n与n之间不能直接用情形一因为它只小了一个对数因子不满足 ε 0。第二递推式里的取整可以忽略但前提是递推式本身有定义。实际写代码时n/b通常不是整数渐近分析中取整误差不影响最终量级可以放心处理。第三主定理要求所有子问题规模相等如果遇到T(n) T(n/4) T(3n/4) n这种两个子问题规模不同的递推式标准形式不能直接套需要换递归树分析。把这三个坑记住比多背几个例子有用得多。4.3 递归树展开什么时候比背公式可靠遇到主定理不好直接套的情况我习惯画递归树。以T(n) 2T(n/2) n为例根节点代价是 n第二层有两个节点每个代价 n/2合计 n第三层四个节点每个代价 n/4合计 n。直到叶子节点每一层的合计代价都是 n递归深度是 logn所以总复杂度 O(nlogn)。这个推导比背公式更能解释“为什么很多分治算法是 nlogn”因为每层的整体代价保持同一量级而层数只有 log n。再看不平衡的例子T(n) T(n/4) T(3n/4) n。最深的递归路径每次走 3n/4 那条分支深度约为 log(4/3) n也就是 O(logn)。同一层所有节点覆盖的规模总和不超过 n所以每层代价仍不超过 n总复杂度 O(nlogn)。这种“不看单个分支看每层代价”的方法是递归树分析的核心。以后遇到分治问题先画出递归树再判断每层代价往往比硬套主定理更稳。5. 递归在工程中的三件麻烦事栈溢出、重复计算、循环改写5.1 栈溢出递归深度不是免费午餐工程中写递归最需要警惕的是栈溢出。递归深度由具体场景决定比如二叉树高度、分治切分次数等。最极端的例子是链表形态的树每个节点只有一个后代递归计算高度时深度就是节点数 n。当 n 达到上万甚至十万系统栈很可能崩溃。估算方法很简单假设一个栈帧占用 256 字节递归深度 100 万时大约需要 256 MB 栈空间而系统默认栈通常只有几 MB。所以写递归前先估算最坏递归深度深度达到数千甚至上万就要考虑显式栈模拟或循环改写。这里有个容易忽视的点树形递归总调用次数很多但不一定导致高深度。比如完全二叉树的节点数是 2^h - 1递归深度只有 h也就是 log 级别栈压力不大。线性递归虽然总调用次数少但深度可能等于输入规模 n反而更容易爆栈。判断一个递归能不能用在生产环境关键看“同一时刻的最大嵌套层数”而不是总调用次数。这个指标可以在纸上推也可以加一个深度计数器在测试时打出来。5.2 重复计算分治和记忆化的分界线前面说过朴素斐波那契是重复计算的典型递归树里大量相同节点被反复展开复杂度指数级。解决办法是加缓存把已经算过的结果保存下来from functools import lru_cache lru_cache(maxsizeNone) def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)加上缓存后每个子问题只计算一次复杂度降到 O(n)。这种做法的本质是“自顶向下的动态规划”也就是记忆化递归。这里要特别强调记忆化递归与分治的关键区别在于记忆化针对子问题重叠分治针对子问题独立。看到一个问题先判断子问题是否重叠再决定用哪种策略比拿到就递归更靠谱。很多人把“动态规划”理解成只能自底向上写数组其实记忆化递归往往更容易写出正确边界条件只是要注意缓存本身的内存开销。5.3 递归改写循环显式栈与尾递归优化递归改循环主要有两种模式。第一种是针对简单的尾部递归或单路递归可以直接去掉递归调用。比如二分查找的递归版可以很容易改成 while 循环def binary_search(arr, target): low, high 0, len(arr) - 1 while low high: mid (low high) // 2 if arr[mid] target: return mid if arr[mid] target: low mid 1 else: high mid - 1 return -1第二种是针对需要回溯的递归例如二叉树的深度优先遍历、快速排序的分治流程。这种情况下可以在循环里手动维护一个栈结构用显式栈保存待处理的子任务。显式栈的优点是不受系统调用栈限制深度可以很大缺点是需要自己管理状态代码可读性明显下降。工程原则是默认先用递归保证逻辑清晰只有当递归深度可能有风险、或者性能要求极高时才改手动栈。为了“炫技”而把每个递归都改成迭代反而会让代码难维护。6. 调试递归的三个实用技巧打印、复杂度验证、边界用例6.1 分层打印看清每一次进入和退出递归函数出错时最难受的是不知道递归走到了哪一步。我调试递归的固定操作是在函数入口打印参数在 return 前打印返回值def factorial(n, depth0): print( * depth fenter n{n}) if n 0: print( * depth base case return 1) return 1 result n * factorial(n - 1, depth 1) print( * depth fexit n{n} result{result}) return result输出会清楚显示调用路径和返回路径。对于树形递归打印深度和参数能很快发现“哪个分支没有收敛”或者“哪些参数反复出现”。如果加了打印后输出非常长可以只打印到某个深度或者限制参数取值避免刷屏。调试完成后记得删掉这些调试语句或者用专门的日志开关控制。6.2 用输入规模验证复杂度假设理论推导完复杂度后我会用运行时间做快速验证。比如归并排序输入规模从 10000 涨到 40000运行时间大约变为 4 倍以下因为 nlogn 中 logn 变化很小。如果实测时间涨了接近 16 倍那很可能是退化成了 O(n²)比如快速排序遇到已有序数组且每次选端点作为枢轴。这种验证不需要精确计时只需要看“规模翻倍时间大致翻几倍”就能判断复杂度量级。注意测试时要把语言本身的递归深度限制考虑进去。Python 默认递归深度 1000因此用递归实现归并排序测试几万规模时会直接触发 RecursionError。解决方法是先设置sys.setrecursionlimit(1000000)或者改用迭代版本测试。这个坑本身就是“递归工程化”的典型案例递归在作业和面试里很优雅在真实大规模数据上却可能因为栈限制而无法运行。所以不要只在纸上算复杂度一定要实测一次。6.3 边界用例空输入、单元素、全相同、已有序、逆序我写递归和分治算法时习惯先列一个边界用例清单再开始写代码。至少包括空输入、单元素输入、两个元素输入、所有元素相同、已经有序、完全逆序。这些用例看似简单却能暴露大量隐藏问题。比如快速排序中如果所有元素相同固定取最后一个元素做枢轴的 partition 每轮只排除一个元素复杂度会退化到 O(n²)。解决方式是在 partition 中适当处理相等元素或者用随机化枢轴。归并排序则不受输入初始顺序影响这也是它性能稳定的原因。更重要的经验是边界用例不应该只放在测试最后一步而应该在写递归前帮助思考。拿到一个问题先把这些极端输入在脑子里过一遍很多实现缺陷会提前暴露。例如写递归时如果空输入会导致索引越界那就需要在函数开头加空值保护如果单元素会导致递归没有进入分支就要确认基准情形覆盖了所有终止条件。这个习惯能显著减少调试时间。最后分享一个我自己的习惯遇到一个可以用递归解决的问题第一件事不是立刻写函数而是在纸上画递归树并写出T(n)递推式。如果递归树里出现大量重复节点就考虑记忆化或循环如果子问题之间相互独立且需要合并才考虑分治策略。这套判断流程看起来简单但确实帮我避免了不少无效编码。你可以先拿归并排序和最近点对练手再回过头看课本上的习题会发现递归与分治其实是一套很有章法的问题拆解工具。