递归式求解与主定理

一句话定义

递归式（Recurrence）用「自身在更小输入上的代价 + 分解合并的代价」描述递归算法的总代价；主定理（Master Theorem）对 T(n) = a·T(n/b) + f(n) 型递归式给出按三情形直接读出 Θ 解的通用规则。

为什么重要

归并排序、二分查找、快速幂、Karatsuba 乘法、Strassen 矩阵乘法的复杂度全部由递归式刻画。不会解递归式，就无法回答「这个分治为什么是这个复杂度」，也无法在面试中推导算法代价。它同时是把 kp-002 的渐进语言与 kp-024 的分治框架连起来的桥。

前置知识

kp-002；递归函数的执行模型（函数调用自身、递归到基准情形）。

核心概念

• 递归式三要素：子问题个数 a、子问题规模缩减因子 b、跨子问题合并代价 f(n)；基准情形 T(常数) = O(1)。
• 递归树法：把递归展开成树，逐层求代价再求和，是理解一切的直观工具。
• 代入/猜想验证法：猜一个界，用数学归纳验证，适合主定理覆盖不到的形状。
• 主定理三情形：比较 f(n) 与临界函数 n^(log_b a) 谁占主导（见公式节）。
• 适用边界：主定理只覆盖 a·T(n/b) 形；减法型如 T(n)=T(n−1)+n 与不规则型不在其列。

原理与机制

解递归式的通用机制是递归树三步：①按递归式把调用展开成一棵树；②算每一层的总代价（子问题个数 × 单个代价）；③把各层代价相加并按层数分类求和。主定理是对这套机制的封装：它比较「叶子层总代价 n^(log_b a)」与「每层自身代价 f(n)」谁多项式级占优——叶子大听叶子的，f 大听 f 的，同阶则再多乘一个 log 因子。

直观类比

递归树像一张家族开销表：每一代有 a 个孩子，每个孩子的开销是父辈的 1/b；总开销 = 每一代的总开销之和。主定理做的事，就是比较「树深的衰减速度」与「每层自身开销 f(n)」谁更快——谁主导，总账就按谁算。

公式或模型

设 x = log_b a（叶子层的临界指数），则：

• 情形一：若 f(n) = O(n^(x−ε))（多项式慢于叶子），T(n) = Θ(n^x)。
• 情形二：若 f(n) = Θ(n^x·log^k n)（与叶子同阶，可差对数次幂），T(n) = Θ(n^x·log^(k+1) n)。
• 情形三：若 f(n) = Ω(n^(x+ε)) 且满足正则条件 a·f(n/b) ≤ c·f(n)（c<1），T(n) = Θ(f(n))。

三个标准例子：

T(n) = 2T(n/2) + n    x=log₂2=1，f=n 同阶 ⇒ Θ(n log n)   （归并排序）
T(n) = T(n/2) + 1     x=1，f=1 慢于 n     ⇒ Θ(log n)     （二分查找）
T(n) = 2T(n/2) + 1    x=1，f=1 慢于 n     ⇒ Θ(n)         （遍历二叉树）
T(n) = 3T(n/2) + n    x=log₂3≈1.585，f=n 慢 ⇒ Θ(n^log₂3) （Karatsuba）

图示

归并排序递归树（每层合计 n，共 log₂n 层）：

level 0:            n                     → 代价 n
level 1:      n/2       n/2              → 代价 n
level 2:   n/4   n/4  n/4   n/4          → 代价 n
   …                              共 log₂n 层
总计：n × log₂n ⇒ Θ(n log n)

实例或案例

• 归并排序：分解 O(1)，合并两有序数组 O(n)，得 T(n)=2T(n/2)+n ⇒ Θ(n log n)。
• 二分查找：只递归一侧，T(n)=T(n/2)+O(1) ⇒ Θ(log n)。
• 快速幂：a^n 直接乘 n 次是 O(n)；改为 a^(n/2) 平方后按奇偶调整，T(n)=T(n/2)+O(1) ⇒ O(log n)，是密码学大数运算的基元。
• T(n) = T(n−1) + n：递归树逐层递减，合计 n+(n−1)+…+1 = n(n+1)/2 ⇒ Θ(n²)，说明减法型必须用递归树/累加而非主定理。

常见误区

• 把 T(n)=T(n−1)+n 硬套主定理：它不是 a·T(n/b) 形，套出来毫无意义。
• 忘记加合并代价 f(n)：只看子问题个数会得到错误阶（如把归并排成 n）。
• 忽略取整与不平衡：n/2 取上下整、子问题规模不均（如快排最坏 0/n−1 划分）都超出主定理假设，需要另行分析。
• 情形比较必须「多项式级」差距，f(n)=n/log n 这类边界形状不可套用。

自测题

1. 用主定理求 T(n) = 4T(n/2) + n²。

答案要点：x = log₂4 = 2，f(n)=n² 同阶 ⇒ 情形二，T(n)=Θ(n² log n)。

1. 求 T(n) = 2T(n/2) + n log n。

答案要点：x=1，f=n log n = n^1·log¹n ⇒ 情形二 k=1，T(n)=Θ(n log²n)。

1. 说明 T(n) = T(n−1) + O(1) 的解并解释为什么主定理不适用。

答案要点：递归树是链，共 n 层合计 Θ(n)；自变量是 n−1 不是 n/b，不属于主定理形态。

与其他知识点的关系

kp-020 用主定理证明比较排序常见实现都是 O(n log n)；kp-024 的分治模板与递归树一一对应；kp-028 的区间 DP 则展示「子问题重叠」时该放弃分治改用 DP 的分界。

延伸阅读

《算法导论》第 4 章「分治策略」；MIT 6.006 Lecture 2–3（递归式与分治）。