递归与分治是算法设计与分析里最绕不开的一对组合拳。我刚带团队做项目评审时发现不少工程师写了两三年业务代码遇到“汉诺塔”“全排列”这类问题还是发怵递归函数一写就爆栈分治边界一处理就错。说白了递归是一种思维方式分治是一种解决问题的策略两者经常一起出现但很多人把它们混为一谈。这篇文章我想从本质出发把递归的运行机制、分治的适用条件、经典案例的代码实现、递归转非递归的实战方法以及复杂度分析的套路全部捋一遍尤其是“快速排序非递归”这个被频繁问到的点我会给出可以直接抄作业的显式栈实现。无论你是正在准备算法面试的在校生还是想系统补课的后端开发都应该能从里面捞到点干货。1. 递归一个函数怎么自己调用自己1.1 递归的本质是“重复结构”不是“重复执行”很多人以为递归就是函数调用自身这个理解没错但太表层了。真正驱动我使用递归的判断标准是一个问题能否被拆解成“规模更小、结构相同”的子问题并且这个拆解过程能一直持续到一个可以直接返回答案的“最小单元”。举一个最朴素的生活例子。你在电影院坐到第N排想知道自己是第几排但黑灯瞎火看不清。你只需要问前一排的人“你是第几排”他再问前一排一直问到第一排第一个人说“我是第一排”然后答案像接力棒一样传回来。这个过程里每一排的人都在做同一件事——问前一排、等答案、加一、传回去。这就是递归的完整闭环递推阶段不断把问题传递给更小的子问题问前一排。到达边界最小的子问题有明确答案第一排。回归阶段逐层携带答案返回并做简单加工加一。翻译成代码几乎所有的递归函数都长一个样def fn(n): # 终止条件边界情况 if n 最小规模: return 直接答案 # 递归调用规模更小的子问题 sub_result fn(n - 1) # 结果合并可选 return sub_result 简单加工我不止一次在评审代码时看到有人把终止条件写在递归调用之后或者写漏了终止条件导致无限递归——这是递归最容易犯的错误。终止条件不是“可选项”它是递归的刹车。没有刹车的递归就像没有绳子的井绳会一直掉到底最后把系统栈砸穿报StackOverflowError。1.2 递归与数学归纳法一个硬币的两面我第一次体会“递归为什么是对的”是在复习数学归纳法时悟到的。后来我带实习生只要他数学归纳法学得扎实递归理解得就快。两者几乎是一一对应的归纳基础 ↔ 终止条件证明当n等于最小值比如n1时命题成立。归纳假设 ↔ 递归假设假设规模为n-1时命题成立。归纳步骤 ↔ 递推关系基于n-1的假设证明n成立。比如斐波那契数列数学上定义 f(0)0, f(1)1递推式 f(n)f(n-1)f(n-2)。代码几乎就是定义本身def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)你不需要从头到尾推演整个计算过程只要验证边界正确、递推关系正确递归就是“自动正确”的。这也是递归最大的价值——用极少的代码表达极复杂的逻辑。但这里有个极其重要的性能警示朴素递归计算 fib(50) 在普通笔记本上可能要算到天荒地老因为它把同一个子问题算了无数遍。递归这种“自我重叠”特性如果没有记忆化memoization兜底会从优雅的数学定义变成灾难性的性能黑洞。后面讲到动态规划和递归转非递归时我会再展开这层关系。1.3 递归调用栈理解“栈溢出”的先决条件递归的每一步调用系统都会在内存中为当前函数分配一块“栈帧”存放参数、局部变量、返回地址。递推阶段像往箱子栈里一个个摞盘子回归阶段再把盘子一个个取出来。盘子摞得越多递归深度越大占用的内存越大超过系统限制就爆栈。举个例子对一个10万长度的链表题目如果你用递归遍历并做累加递归深度就是10万层大概率直接爆栈。这就是为什么很多生产环境的代码规范里明确要求“禁止无限制深度递归”。计算递归深度的经验公式很简单每次调用消耗约几百字节到几KB视参数和局部变量而定系统默认栈空间通常是8MBLinux或1MBWindows。我实战中总结的几条经验递归深度超过 10^4 就要警惕。递归深度超过 10^5 基本必然爆栈。深度可预知但很大时优先考虑非递归改写显式栈或循环。可以把递归调用放在函数尾部优化成尾递归但Python默认不支持尾递归优化Java、C通常也不做所以别指望编译器救你。2. 分治策略三分天下而后合2.1 分治的完整流程分治策略Divide and Conquer的核心思想是把一个复杂问题分解成若干规模较小但结构与原问题相同的子问题递归地解决这些子问题再把子问题的结果合并成原问题的解。标准的三个步骤分解Divide将原问题拆成若干个规模更小的同类问题。解决Conquer递归地求解每个子问题。若子问题足够小直接求解。合并Combine将各子问题的结果合并为原问题的解。听起来和递归几乎一样没错分治是“策略”递归是实现手段之一。分治的精髓在于“分解”如何做、“合并”怎么做这两个环节往往是算法优化的胜负手。别把分治和平凡的“分解成两步并分别处理”混为一谈。真正需要分治的是那些分解出的子问题彼此独立、可递归解决、合并结果有明确规则的问题。我经常和同事讨论一个判断标准如果你分解出来的子问题之间需要交换信息、互相依赖那就不符合分治的独立假设硬套分治只会让代码和效率双双崩盘。2.2 哪些问题适合分治我总结了四个适用条件前两个是硬性的后两个是效率层面的原问题可以缩小规模但不改变本质结构数学结构相同。子问题的解可以合并出原问题的解。子问题相互独立不包含重复子问题如果包含重复子问题动态规划可能更合适。分解和合并在时间上有收益至少不能比直接求解更慢。一个经典的适用案例是归并排序。原始数组排好序可以分解成左半部分和右半部分分别排序然后合并两个有序数组——合并过程 O(n)递归深度 O(log n)总复杂度 O(n log n)。而快速排序同样是分治但它的关键在“分解”partition这一步合并几乎什么都不做。另一个容易被误解的点分治和动态规划有时候看起来很像因为都是“大问题变小问题”。但动态规划讲究子问题重叠分治讲究子问题独立。比如斐波那契数列用朴素递归就是“分治式”的自顶向下实际上它更适合动态规划因为子问题大量重叠用迭代就是自底向上填表。所以当子问题被重复计算时就该考虑在分治骨架上加记忆化或者直接切换为动态规划。3. 经典案例拆解归并、快排与最大子数组3.1 归并排序稳定的分治骨架代码我给过很多人这里再给一次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 result [] while i len(left) and j len(right): if left[i] right[j]: result.append(left[i]) i 1 else: result.append(right[j]) j 1 result.extend(left[i:]) result.extend(right[j:]) return result归并排序之所以是“稳定”排序是因为left[i] right[j]时优先取左半部分值相等时保持了原始相对次序。如果你把改成稳定性就没了。这个细节在面试里经常被追问。实现时有个巨大的“坑”是切片带来的额外空间。上面的 Python 实现每层递归都创建新切片数组空间复杂度 O(n log n)但实际上归并排序的标准空间复杂度是 O(n)。要优化到 O(n)需要用一个全局的辅助数组并在递归函数里操作下标而不是频繁切片。我在工程中用到的版本都是传入temp数组def merge_sort_inplace(arr, left, right, temp): if right - left 1: return mid (left right) // 2 merge_sort_inplace(arr, left, mid, temp) merge_sort_inplace(arr, mid, right, temp) # 合并 arr[left:mid] 和 arr[mid:right] 到 temp再复制回 arr i, j, k left, mid, left while i mid and j right: if arr[i] arr[j]: temp[k] arr[i] i 1 else: temp[k] arr[j] j 1 k 1 while i mid: temp[k] arr[i] i 1 k 1 while j right: temp[k] arr[j] j 1 k 1 arr[left:right] temp[left:right]注意终止条件right - left 1表示区间内至多一个元素天然有序。这种“左闭右开”区间写法[left, right)能避免一堆 1/-1 的边界错误强烈推荐。3.2 快速排序分治思想的另一个极致快速排序的核心是 partition——选一个主元pivot把数组分成小于等于主元和大于主元的两部分然后递归处理两部分。它的“合并”几乎为零因为主元已经在正确位置上子问题排序完整个数组就排完了。快排平均 O(n log n)最坏 O(n²)比如输入已经有序而每次选最左或最右元素做 pivot。最坏情况正是快速排序最大的弱点因此工业实现普遍使用随机化 pivot或三数取中法来避免退化。基础版的递归快排def quick_sort(arr, left, right): if left right: return pivot_index partition(arr, left, right) quick_sort(arr, left, pivot_index - 1) quick_sort(arr, pivot_index 1, right) def partition(arr, left, right): pivot arr[left] # 取第一个元素做pivot i, j left 1, right while i j: while i j and arr[i] pivot: i 1 while i j and arr[j] pivot: j - 1 if i j: arr[i], arr[j] arr[j], arr[i] arr[left], arr[j] arr[j], arr[left] return j这个双指针版本的好处是它原地交换不需要额外数组。partition 返回的是 pivot 最终落位的下标此时 pivot 左边都不大于它右边都大于它。我先声明一个几乎每个人都会踩的坑partition 之后递归区间千万别把 pivotIndex 本身再包含进去。有人写quick_sort(arr, left, pivot_index)结果 pivot 被反复处理直接死循环或者结果不对。正确的区间是[left, pivot_index - 1]和[pivot_index 1, right]。3.3 最大子数组问题分治的收益来自“跨中点”的合并最大子数组问题给定一个数组可能含负数找一个连续子数组使其和最大。暴力解法 O(n²)分治可以做到 O(n log n)。思路是把数组从中间分成两半最大子数组要么完全在左半要么完全在右半要么跨越中点。前两种递归求第三种单独求从中间向左扩展找最大和从中间向右扩展找最大和加在一起。def max_subarray(arr, left, right): if left right: return arr[left] mid (left right) // 2 left_sum max_subarray(arr, left, mid) right_sum max_subarray(arr, mid 1, right) cross_sum max_crossing(arr, left, mid, right) return max(left_sum, right_sum, cross_sum) def max_crossing(arr, left, mid, right): sum_left float(-inf) total 0 for i in range(mid, left - 1, -1): total arr[i] sum_left max(sum_left, total) sum_right float(-inf) total 0 for j in range(mid 1, right 1): total arr[j] sum_right max(sum_right, total) return sum_left sum_right你注意看这个max_crossing的写法我做了两遍单向遍历分别从中间向左、从中间向右累积最大值。这里必须从中间出发不能从边缘出发否则你统计的就不一定是“跨中点”的子数组。我之前在面试别人时遇到过不少候选人在这里想当然地写了个双指针滑动窗口——那是另一种方法不是分治的正确姿势。分治的核心优势在这里体现得很明显暴力解需要枚举所有子数组的起点和终点O(n²)个组合分治把问题拆成两个子数组和一个跨中点的线性扫描复杂度从 O(n²) 降到 O(n log n)。我实际带项目时的观察是分治法最适合“分解简单、合并有复杂度”的题目。如果你发现某个题的分解很别扭、合并又很麻烦多半是这个题本来就不适合分治换个思路反而高效。4. 快速排序非递归打破系统栈的束缚4.1 为什么要转非递归快速排序用递归代码清晰。但递归的深度在极端情况下比如几乎有序且pivot选得很差可能接近 n比如对 10 万长度的近乎有序数组如果每次pivot都选在端点递归深度10万层系统栈很可能爆掉。尤其是在嵌入式、后端高并发环境里栈空间被严格控制递归逻辑稍有不慎就把线程栈顶穿。业界常规做法是用显式栈模拟系统递归栈。说白了就是自己维护一个“待处理的子区间”列表循环弹出区间、partition、再把新的子区间压栈。系统栈换成堆内存中的显式栈深度只受堆内存限制能扛的规模大得多。4.2 显式栈模拟的完整实现我写过一个可以放心上生产的版本直接用栈存左右边界左闭右闭每次处理一个区间然后按“先右后左”或“先左后右”的顺序压栈都可以只是顺序会影响处理次序但不影响结果def quick_sort_non_recursive(arr): if len(arr) 1: return arr stack [(0, len(arr) - 1)] while stack: left, right stack.pop() if left right: continue pivot_idx partition(arr, left, right) # 左子区间入栈 if pivot_idx - 1 left: stack.append((left, pivot_idx - 1)) # 右子区间入栈 if pivot_idx 1 right: stack.append((pivot_idx 1, right)) return arrpartition 函数复用前面递归版的实现。逻辑上唯一需要小心的是压栈前做检查区间长度大于1才压栈避免压入无数个无意义区间。你可能会问“先压左还是先压右”有没有讲究。我的经验是先压右再压左这样左区间先被弹出处理更贴合递归版本“先处理左半边”的顺序。但如果你不 care 处理顺序压栈顺序随缘即可反正最终排序结果一致。当然如果你想额外控制空间也可以只压大区间小区间继续递归混合策略——这是另一个非常实用的优化后续展开。4.3 更进一步的压栈策略只压大区间快速排序非递归还有一个小优化每次partition后比较两个子区间的长度把较长的区间压栈较短的区间继续循环处理。这样做可以把显式栈的最大深度限制在 O(log n) 级别。为什么因为每次循环处理一个小区间栈里最多积累 O(log n) 个“较大区间”。def quick_sort_non_recursive_v2(arr): left, right 0, len(arr) - 1 stack [] while True: while left right: pivot_idx partition(arr, left, right) # 长度较大的区间入栈 if pivot_idx - left right - pivot_idx: stack.append((left, pivot_idx - 1)) left pivot_idx 1 else: stack.append((pivot_idx 1, right)) right pivot_idx - 1 if not stack: break left, right stack.pop() return arr这段代码初学者看容易懵我建议你结合一个具体数组手动模拟一遍。核心变化就是不再把两个子区间都入栈而是把短的区间直接迭代处理长的留到后面。摊还下来空间效率逼近递归版的期望水准甚至更稳。这个优化在面试聊到“非递归快排”时非常加分因为大部分人只会“无脑压栈”能讲出“只压大区间”的人说明真的理解快排的分治本质和空间复杂度。5. 复杂度分析递归树与主定理5.1 递归树把代价画出来每次写递归算法我都建议先在草稿纸上画一棵递归树。树的每个节点代表一次递归调用节点的开销就是除递归调用外的代价也就是“分解合并”的开销。把所有节点的开销加起来就是总复杂度。以归并排序为例。第一层有1个节点开销O(n)第二层有2个节点每个开销O(n/2)总开销O(n)第三层4个节点每个O(n/4)总开销还是O(n)。树高O(log n)每层O(n)总共O(n log n)。斐波那契朴素递归就不一样了每个节点分裂出两个子节点树高O(n)节点数O(2^n)总复杂度O(2^n)——这就是为什么朴素递归斐波那契慢得离谱。递归树还是设计算法的启发工具。我经常用递归树来“猜”复杂度再用主定理验证。面试时你先画树再说结论比直接报公式显得更有底气。5.2 主定理快速判定形如 T(n) aT(n/b) f(n) 的复杂度主定理是处理分治复杂度的利器。形式是 T(n) aT(n/b) f(n)其中 a 是子问题数量n/b 是子问题规模假设均匀拆分f(n) 是分解和合并的代价。结论分三种情况反复出现我直接给出记忆法如果 f(n) 比 n^(log_b a) 增长得慢多项式意义则 T(n) Θ(n^(log_b a))。如果 f(n) 比 n^(log_b a) 增长得快且满足正则条件 af(n/b) ≤ c f(n)c1则 T(n) Θ(f(n))。如果两者同阶相差多项式因子 n^k则 T(n) Θ(n^(log_b a) log n)。举例归并排序T(n) 2T(n/2) O(n)a2, b2log_b a 1f(n)n 与 n^1 同阶 → O(n log n)。二分搜索T(n) T(n/2) O(1)a1, b2log_b a 0f(n)1 与 n^0 同阶 → O(log n)。朴素递归斐波那契T(n) T(n-1) T(n-2) O(1)这个不满足 n/b 的均匀划分形式主定理不适用用递归树估计 O(2^n) 即可。主定理不是万能钥匙它要求子问题等规模。如果代码里n-1而不是n/2主定理直接失效换递归树或代入法。5.3 代入法证明和验证的手艺活最后再提一个被我工作中反复用来“验证”复杂度的技巧先猜复杂度再用归纳假设证明。这招叫代入法Substitution。比如你已经由递归树猜出 T(n) O(n log n)接下来就要证明存在 c0 使 T(n) ≤ c n log n 对足够大的 n 成立。代入法最常见的陷阱是归纳假设的强度不够或者常数取小了。我第一次做人人都绕不开的“矩阵乘法分治”时就吃了这个亏证明到一半发现式子撑不住返工调整常数后又推导了下界才把思路理顺。这类问题一定要留出草稿纸反复凑常数别指望一次成功。6. 常见坑位与排查实录6.1 栈溢出和“明明没错却崩了”最常见的是递归深度过大。你感觉逻辑没错边界也对为什么一跑就RecursionError大概率是终止条件在数据规模很大时依然太深。比如链表题递归处理10万元素系统栈直接爆掉。排查方法在递归函数入口打印或记录当前深度。把递归改为循环或显式栈。用sys.setrecursionlimit(1000000)之类临时调高Python递归上限治标不治本不推荐上生产。我见过一个线上服务半夜挂掉的案例就是有个定时任务对大数据量做了递归处理深度超过预期直接把线程栈打穿。从那以后凡是递归深度不可控的代码我都要求写成非递归版本。6.2 边界条件到底该不该用 分治代码里边界“差1”是最难调的东西。我的经验是统一选择一种区间表示法并且坚持到底。我推荐左闭右闭 [left, right] 用于容易理解或左闭右开 [left, right) 用于避免一些 1 的繁琐。最怕的是同一个函数里混用两种表示法那等于自爆。以快速排序为例如果用左闭右闭递归区间是[left, pivot_idx-1]和[pivot_idx1, right]如果用左闭右开递归区间是[left, pivot_idx)和[pivot_idx1, right)。两种写法都能跑通但混着写必错。6.3 重复子问题导致性能雪崩有些看起来“正确”的递归实际在重复计算大量子问题。斐波那契是典型。这时候你要判断子问题是否重叠重叠的话无脑加记忆化或者改成动态规划。我常用的一个判断方法在递归函数里加一个打印看看同一个参数被调用了多少次。一旦发现高频重复立刻上记忆化from functools import lru_cache lru_cache(maxsizeNone) def fib_memo(n): if n 1: return n return fib_memo(n - 1) fib_memo(n - 2)加了这一行装饰器fib(50) 从“天荒地老”变成“瞬间出结果”。这是递归分治类问题里性价比最高的优化手段没有之一。下面我把这一路遇到的高频问题整理成一张自查表方便你调试时逐项对照症状常见原因排查方法无限递归或溢出终止条件缺失/不对检查最小规模时是否有明确返回结果差一点区间边界写错统一区间表示法逐层打印边界速度极慢重复子问题打印调用次数加记忆化排序结果部分错partition后递归区间包含pivot复查递归区间是否排除pivot_idx非递归快排仍爆内存压栈过多只压大区间缩短栈深度合并结果出错合并时下标与原数组错位用临时数组并检查复制区域6.4 快速排序非递归的实际踩坑记录最后聊一个非常具体的快排非递归的坑。有一次我在实现显式栈快排时partition 里用了数组最后一个元素做 pivot然后我递归区间用的是[left, pivot_idx-1]和[pivot_idx1, right]看起来没什么问题但当数组中大量元素重复时出现了“分区不均衡”导致的性能退化。原因是单一的“小于等于pivot放左边大于放右边”策略在重复值多的情况下会让pivot偏移到某一端递归深度变大。解决方法是双路快排两路partition或三路快排三路partition。双路快排在遇到相等元素时依然会交换位置避免把相等元素全聚到一边。三路快排则是把相等元素单独放中间一段然后递归处理严格小于和严格大于的两段。处理重复值多的数组时三路快排明显更稳。我把这个经验记到今天就是因为当时线上报表任务卡的快排性能问题最后是三路快排救了场def quick_sort_3way(arr, left, right): if left right: return pivot arr[left] lt left # arr[left:lt] pivot i left 1 gt right # arr[gt1:right] pivot while i gt: if arr[i] pivot: arr[lt], arr[i] arr[i], arr[lt] lt 1 i 1 elif arr[i] pivot: arr[i], arr[gt] arr[gt], arr[i] gt - 1 else: i 1 quick_sort_3way(arr, left, lt - 1) quick_sort_3way(arr, gt 1, right)这个版本可以照样改成非递归思路一致把中等段放在中间不动只对左右两端做显式栈处理。带组员这一年多我最大的体会是递归与分治不是“背模板”而是建立一种“规模缩放”的思维模型。遇到一个问题先把规模缩小到人能一眼看穿的程度搞清楚极简情况下怎么解再想怎么把大规模拆成同样的小规模。递归负责把“拆解—回归”的结构写出来分治负责把“拆—解—合”的流程定下来。这套组合拳几乎可以用在排序、搜索、树、图、数值计算等各个领域。如果你正被某道递归题卡住不要先急着写代码拿一张A4纸画出递归树和调用栈标清楚终止条件、递推关系和合并方式。画完之后你会发现绝大多数问题难在“合并那一步”而不是“递归本身”。这和我当初第一次手推归并排序的感受一模一样——想明白“两个有序数组合并成一个有序数组”整个归并排序就通关了。最后分享一个小技巧调试递归函数时别瞎打日志在函数入口加一个depth参数并打印 * depth ffn({n}) enter这样看日志就能清晰看出整个递归树的展开过程。我后来写一切递归相关代码第一件事就是加这个缩进打印定位边界问题快得惊人。