Recursion & Divide and Conquer
递归
递归是用函数自己定义自己。一个正确的递归需要两样东西:
1. 基础情形(Base Case):最小规模直接给出答案,不再递归
2. 递归情形(Recursive Case):把问题化归为更小的同类问题缺了 base case → 无限递归;递归情形没有"变小" → 也是无限递归。
int factorial(int n) {
if (n == 0) return 1; // base case
return n * factorial(n - 1); // 规模变小
}递归的三要素
| 要素 | 说明 |
|---|---|
| 定义(信什么) | 明确"这个函数返回什么"。先相信它是对的,用它的结果构造当前层 |
| 拆解(怎么变小) | 怎么把当前问题变成更小的子问题 |
| 出口(何时停) | base case |
最关键的是第一条:不要试图在脑子里展开整个递归树。只需假设 f(n-1) 已经正确返回,然后用它算 f(n)。这叫递归信任(recursive leap of faith)。
递归的代价
每次调用:
- 压栈:返回地址、参数、局部变量
- 跳转
返回时:
- 弹栈、恢复栈空间:深度 × 每帧大小。默认栈 8 MB(Linux)/ 1 MB(Windows),
- 深度,每帧 100 字节 → 1 MB,OK
- 深度 → 爆栈(Stack Overflow)
优化:
| 手段 | 做法 |
|---|---|
| 尾递归 | 递归调用是函数最后一步 → 编译器可优化成循环(C++ 不保证,要开 -O2) |
| 改迭代 | 显式用栈/循环 |
| 减小帧 | 大对象放堆上,别放栈 |
| 增大栈 | ulimit -s / 链接器选项(不推荐,治标) |
// 尾递归:可以优化成循环
int sum(int n, int acc = 0) {
return n == 0 ? acc : sum(n - 1, acc + n);
}
// 但 GCC 在 -O2 下才会真的优化,别依赖它分治(Divide and Conquer)
分治是结构化的递归,三步:
1. Divide : 把问题分成若干规模更小的子问题
2. Conquer : 递归解决子问题(规模小到一定程度直接解)
3. Combine : 把子问题的解合并成原问题的解与纯递归的区别:分治强调"分成多个独立的子问题 + 合并",递归只是"自己调用自己"。
复杂度分析:主定理(Master Theorem)
对形如
的递推( 个子问题,每个规模,合并代价):
令(叶子数量级):
| 情形 | 条件 | 结果 |
|---|---|---|
| 1 | ,某个 | |
| 2 | ||
| 3 | ,且满足正则条件() |
直觉:比较"子问题的总代价"和"合并代价"谁大:
| 比较 | 结果 |
|---|---|
| 合并比叶子便宜 | (叶子主导) |
| 一样大 | (每层一样,乘层数) |
| 合并比叶子贵 | (根主导) |
例子
| 算法 | 递推式 | 结果 | ||
|---|---|---|---|---|
| 二分查找 | 1, 2 | 0 | ||
| 归并排序 | 2, 2 | 1 | 情形 2 → | |
| 快速排序(平均) | 2, 2 | 1 | ||
| 二叉树的遍历 | 2, 2 | 1 | ||
| Karatsuba 乘法 | 3, 2 | 1.585 | ||
| Strassen 矩阵乘法 | 7, 2 | 2.807 |
递归树法(主定理不适用的情形)
当 不固定(如快排最坏)时,画递归树:
快排最坏(每次选到最小/最大作 pivot):
T(n) = T(n-1) + O(n)
展开: n + (n-1) + (n-2) + ... + 1 = O(n^2)
归并排序:
层数 log n,每层总代价 n
→ O(n log n)递归树法永远可用,主定理只是快捷方式。
经典分治算法
归并排序(Merge Sort)
void merge_sort(vector<int>& a, int l, int r, vector<int>& tmp) {
if (r - l <= 1) return; // base case
int m = l + (r - l) / 2;
merge_sort(a, l, m, tmp); // 分
merge_sort(a, m, r, tmp);
// 合并两个有序段 [l,m) 和 [m,r)
int i = l, j = m, k = l;
while (i < m && j < r)
tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
while (i < m) tmp[k++] = a[i++];
while (j < r) tmp[k++] = a[j++];
copy(tmp.begin() + l, tmp.begin() + r, a.begin() + l);
}- 时间:,最好最坏都一样(稳定)
- 空间:(辅助数组)
- 稳定:
a[i] <= a[j]取左边,保证相等元素相对顺序不变
归并排序的分治味道最正:子问题完全独立,合并是核心。
快速排序(Quick Sort)
void quick_sort(vector<int>& a, int l, int r) {
if (l >= r) return;
int p = partition(a, l, r); // 划分:小于 pivot 的放左边
quick_sort(a, l, p - 1);
quick_sort(a, p + 1, r);
}分治结构不同:快排的"分"(partition)是 的,"合"是(什么都不用做)。归并反过来。
- 平均:
- 最坏:(已排序数组 + 总是选最后一个作 pivot)
- 空间:(递归栈),原地排序
快排实际更快的原因:常数小、缓存友好(顺序访问)、原地。虽然最坏复杂度差,但平均表现最好。
二分(在分治视角下)
——只递归一个子问题,所以不是典型分治,叫减治(Decrease and Conquer)。
快速幂
分治,但只递归一半 →。
最近点对
平面上 个点,求最近的点对距离。
1. 按 x 排序,从中间切分成左右两半
2. 递归求左右的最近距离 d = min(dL, dR)
3. 关键:只需检查中间带状区域(宽 2d)内的点
- 该区域内每个点最多只需和后继 7 个点比较(鸽笼原理)
4. 合并答案复杂度: →。
第 3 步是分治的精髓:合并不能是,必须利用子问题的解把合并降到。
逆序对计数
归并排序的副产品:
long long inv = 0;
void merge_sort(vector<int>& a, int l, int r) {
if (r - l <= 1) return;
int m = (l + r) / 2;
merge_sort(a, l, m); merge_sort(a, m, r);
int i = l, j = m; vector<int> tmp;
while (i < m && j < r) {
if (a[i] <= a[j]) tmp.push_back(a[i++]);
else { tmp.push_back(a[j++]); inv += m - i; } // 关键
// a[j] 比 a[i..m-1] 都小 → 产生 (m-i) 个逆序对
}
...
}为什么:合并时,若 a[j] < a[i],则 a[j] 小于左半段剩余的所有元素 a[i..m-1],贡献 个逆序对。
线段树(分治数据结构)
线段树本身就是分治结构:每个节点管一个区间,分成左右两半递归。
查询/修改: O(log n) —— 沿着分治树走
建树: O(n)分治优化 DP
形如 的转移,若 满足四边形不等式 / 决策单调性,可用分治优化到。
solve(l, r, optL, optR):
mid = (l + r) / 2
在 [optL, optR] 里枚举 j,求 dp[mid] 的最优决策 optMid
递归 solve(l, mid-1, optL, optMid)
递归 solve(mid+1, r, optMid, optR) ← 决策单调,右半的决策不早于 optMid分治 vs DP
| 分治 | DP | |
|---|---|---|
| 子问题 | 独立、不重叠 | 重叠(同一子问题被反复计算) |
| 典型 | 归并排序、快排、二分 | 斐波那契、背包、LCS |
| 优化 | 无(本来就不重复) | 记忆化 / 递推 |
判断:画递归树,看有没有重复节点。有 → DP(加记忆化);无 → 分治。
实际上:分治 + 记忆化 = DP。很多 DP 就是"分治 + 缓存"。
写递归的套路
Ret solve(State s) {
// 1. 出口
if (isBase(s)) return baseAnswer(s);
// 2. (可选)记忆化
if (memo.count(s)) return memo[s];
// 3. 拆解 + 递归 + 合并
Ret ans = init;
for (State sub : split(s))
ans = combine(ans, solve(sub));
// 4. 存记忆化
return memo[s] = ans;
}常见坑
- 忘了 base case → 无限递归 / 栈溢出
- 递归情形没有让规模变小 → 无限递归(如
f(n) = f(n)或f(n) = f(n+1)) - 爆栈:深度超过 就要警惕。树的退化链(一条链)会让"看起来 深"的递归变成
- 重复计算:没有记忆化 → 指数复杂度(斐波那契朴素递归是)
- 在递归里声明大数组:每帧都分配,栈迅速耗尽。用全局数组或堆
- 分治的合并写成 → 总复杂度退化
mid计算溢出:l + (r - l) / 2- 归并排序的稳定性:写成
a[i] < a[j]会破坏稳定性(相等时取了右边) - 快排的 pivot 选择:总选
a[r]在已排序数据上是。用随机化或三数取中 - 递归改循环时的边界:迭代版的中序遍历、归并排序的区间端点容易差一