递归与分治
2.1 递归与分治：把大问题拆小
本节摘要：递归是策略进化的起点。本节建立"基准情形加自我调用"的思维模型，用斐波那契亲眼看到重复计算如何把复杂度推向指数级，用归并排序展示分治"拆、解、合"的标准节奏，并交代递归深度、调用栈与尾递归这些实战边界。
递归不是技巧，是思维方式
第一章的排序一节已经用过递归（归并排序），本节把它正式讲透——它是动态规划与回溯共同的祖先，不先把递归想清楚，后面两节寸步难行。递归的核心只有两句话：问题存在更小规模的同款问题；最小规模的答案可以直接给出。前者叫递归关系，后者叫基准情形。写递归函数时永远先写基准情形，再写递归关系——顺序反了，代码多半会无限自我调用直到栈溢出。
最经典的入门案例是阶乘与斐波那契。阶乘的递归是单链式的：n 的阶乘等于 n 乘 n 减一的阶乘，基准是 1。斐波那契则是分叉式的：每一项等于前两项之和，基准是前两项。分叉式的才是本节真正的主角，因为它藏着一个大问题。
def fib_slow(n): if n <= 1: return n return fib_slow(n - 1) + fib_slow(n - 2) print(fib_slow(10)) # 输出 55，还算得动 # fib_slow(40) 在普通笔记本上要等好几秒，fib_slow(50) 基本等不到结果
慢在哪？画递归树一目了然：求 fib_slow(5) 要先求 4 和 3，求 4 又要先求 3 和 2——3 被算了两遍，2 被算了三遍，越往下重复越密集。节点总数是指数级的，时间复杂度 O(2 的 n 次方)。这棵递归树是全章最重要的图景：动态规划的全部魔法，就是把"树上的重复节点只算一次"。记不住公式没关系，"重复节点只算一次"这句话必须刻进脑子。
一、记忆化：给递归装上备忘录
第一代优化朴素得可爱：开一张表，算过的直接查。改动只有两行，复杂度却从指数坍缩到 O(n)——每个 n 只会真正计算一次。
from functools import lru_cache memo = {} def fib_memo(n): if n <= 1: return n if n in memo: return memo[n] memo[n] = fib_memo(n - 1) + fib_memo(n - 2) return memo[n] print(fib_memo(50)) # 输出 12586269025，瞬间完成 # Python 内置装饰器可以直接干同样的事 @lru_cache(maxsize=None) def fib(n): return n if n <= 1 else fib(n - 1) + fib(n - 2) print(fib(100)) # 输出 354224848179261915075
Java 版本对照，用数组当备忘录：
public long fibMemo(int n, long[] memo) { if (n <= 1) return n; if (memo[n] != 0) return memo[n]; memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo); return memo[n]; } // 调用：fibMemo(50, new long[51]) 返回 12586269025
注意这笔账的两面：时间从 O(2 的 n 次方) 降到 O(n)，但空间从 O(n) 的调用栈（朴素版其实也是 O(n) 栈深）增加到栈加备忘录两份 O(n)。递归深度还受系统调用栈限制，Python 默认递归上限约一千层，深度过大直接抛异常——这就是为什么工业代码里深度递归常被改写成显式栈的迭代。
二、分治：拆、解、合
递归只解决"怎么缩小"，分治补上"拆完怎么拼"。标准三段式：拆（把问题分成若干独立同款子问题）、解（递归求解每个子问题）、合（把子解拼成原问题的解）。归并排序是分治的完美标本：拆是对半劈，解是递归排序两半，合是线性归并两个有序段。它的复杂度可以现场推导：n 个元素拆 log n 层，每层合并总工作量 O(n)，合计 n log n。这道推导题面试官极爱现场提问，务必练到脱口而出。
分治有个隐含前提：子问题必须相互独立。如果不独立——比如排序问题里拆成"前一半的所有子集"这种交叉关系——合并阶段会灾难性爆炸。这个前提的正反两面，恰好对应第二章接下来的两个主题：子问题独立选分治，子问题重叠选动态规划。
递归的实用边界再强调几点。基准情形必须先写且必须能到达，否则无限递归；递归深度等于空间开销的一部分，估算空间复杂度时把调用栈算进去；能用简单循环写清楚的问题（阶乘、求和）就用循环，递归留给树形结构与分治场景，为递归而递归只会让读者痛苦。
四、实战演练：一道分治题的完整过程
用多数元素题把分治流程走完整：数组中存在一个出现次数超过一半的元素，找出它。暴力解逐个元素计数比对，平方级；哈希计数线性但吃 O(n) 空间；分治的解法别具一格——把数组对半分，分别找左右两半的多数元素（递归解），若两者相同直接返回，不同则各自在整个区间里数一遍出现次数，多者胜出。正确性论证依赖分治的独立性：真多数元素必然也是至少一半区间的多数元素，否则它的总票数撑不住过半。复杂度推导套用归并的账本：log n 层、每层计数工作 O(n)，合计 n log n，空间 O(log n) 递归栈。
def majority_element(nums, lo=None, hi=None): if lo is None: lo, hi = 0, len(nums) - 1 if lo == hi: return nums[lo] mid = (lo + hi) // 2 left = majority_element(nums, lo, mid) right = majority_element(nums, mid + 1, hi) if left == right: return left left_count = sum(1 for i in range(lo, hi + 1) if nums[i] == left) right_count = sum(1 for i in range(lo, hi + 1) if nums[i] == right) return left if left_count > right_count else right print(majority_element([2, 2, 1, 1, 1, 2, 2])) # 输出 2
这个案例的价值不在解法本身（存在更巧的摩尔投票法），而在示范"递归关系怎么写、合并阶段怎么补救、复杂度怎么现场推导"的完整节奏——面试官要求"用分治解"时，考察的正是这套流程而不是答案。易错点也有代表性：合并阶段忘记处理左右结果相同的情况会漏剪枝；计数范围必须覆盖整个当前区间而不是半区，写错范围的结果是对一半输入都正确、对另一半悄悄出错——这类 bug 恰好要用上一章末尾讲的对拍法抓出来。
本节要点回顾
- 递归两要素：先写能到达的基准情形，再写缩小规模的递归关系；
- 递归树是分析工具：重复节点在树上的密度决定了朴素递归的指数级灾难；
- 记忆化的性价比：两行代码把指数压到线性，代价是多一份备忘录空间；
- 分治三段式：拆、解、合，复杂度等于层数乘每层合并工作量；
- 分治的前提：子问题独立；重叠了就该交给下一节的动态规划。
下一节顺着记忆化往前走一大步：当所有子问题都被记下来，递归可以彻底改成递推——那正是动态规划的形态。