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),

  • 深度10410^4,每帧 100 字节 → 1 MB,OK
  • 深度10610^6 → 爆栈(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 : 把子问题的解合并成原问题的解

Solve(n)=Combine(Solve(n1),Solve(n2),…)\text{Solve}(n) = \text{Combine}\big(\text{Solve}(n_1), \text{Solve}(n_2), \dots\big)

与纯递归的区别:分治强调"分成多个独立的子问题 + 合并",递归只是"自己调用自己"。

复杂度分析:主定理(Master Theorem)

对形如

T(n)=a T ⁣(nb)+f(n)T(n) = a\,T\!\left(\frac{n}{b}\right) + f(n)

的递推(a≥1a \ge 1 个子问题,每个规模n/bn/b,合并代价f(n)f(n)):

令c=log⁡bac = \log_b a(叶子数量级nlog⁡ban^{\log_b a}):

情形条件结果
1f(n)=O(nc−ϵ)f(n) = O(n^{c-\epsilon}),某个ϵ>0\epsilon > 0T(n)=Θ(nc)T(n) = \Theta(n^c)
2f(n)=Θ(nc)f(n) = \Theta(n^c)T(n)=Θ(nclog⁡n)T(n) = \Theta(n^c \log n)
3f(n)=Ω(nc+ϵ)f(n) = \Omega(n^{c+\epsilon}),且满足正则条件af(n/b)≤kf(n)af(n/b) \le kf(n)(k<1k<1)T(n)=Θ(f(n))T(n) = \Theta(f(n))

直觉:比较"子问题的总代价nlog⁡ban^{\log_b a}"和"合并代价f(n)f(n)"谁大:

比较结果
合并比叶子便宜Θ(nlog⁡ba)\Theta(n^{\log_b a})(叶子主导)
一样大Θ(nlog⁡balog⁡n)\Theta(n^{\log_b a} \log n)(每层一样,乘层数)
合并比叶子贵Θ(f(n))\Theta(f(n))(根主导)

例子

算法递推式a,ba, blog⁡ba\log_b a结果
二分查找T(n)=T(n/2)+O(1)T(n) = T(n/2) + O(1)1, 20O(log⁡n)O(\log n)
归并排序T(n)=2T(n/2)+O(n)T(n) = 2T(n/2) + O(n)2, 21情形 2 →O(nlog⁡n)O(n \log n)
快速排序(平均)T(n)=2T(n/2)+O(n)T(n) = 2T(n/2) + O(n)2, 21O(nlog⁡n)O(n \log n)
二叉树的遍历T(n)=2T(n/2)+O(1)T(n) = 2T(n/2) + O(1)2, 21O(n)O(n)
Karatsuba 乘法T(n)=3T(n/2)+O(n)T(n) = 3T(n/2) + O(n)3, 21.585O(n1.585)O(n^{1.585})
Strassen 矩阵乘法T(n)=7T(n/2)+O(n2)T(n) = 7T(n/2) + O(n^2)7, 22.807O(n2.807)O(n^{2.807})

递归树法(主定理不适用的情形)

当a,ba, b 不固定(如快排最坏T(n)=T(n−1)+T(0)+O(n)T(n) = T(n-1) + T(0) + O(n))时,画递归树:

快排最坏(每次选到最小/最大作 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);
}
  • 时间:O(nlog⁡n)O(n \log n),最好最坏都一样(稳定)
  • 空间:O(n)O(n)(辅助数组)
  • 稳定: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)是O(n)O(n) 的,"合"是O(1)O(1)(什么都不用做)。归并反过来。

  • 平均:O(nlog⁡n)O(n \log n)
  • 最坏:O(n2)O(n^2)(已排序数组 + 总是选最后一个作 pivot)
  • 空间:O(log⁡n)O(\log n)(递归栈),原地排序

快排实际更快的原因:常数小、缓存友好(顺序访问)、原地。虽然最坏复杂度差,但平均表现最好。

二分(在分治视角下)

T(n)=T(n/2)+O(1)T(n) = T(n/2) + O(1)——只递归一个子问题,所以不是典型分治,叫减治(Decrease and Conquer)。

快速幂

an=an/2⋅an/2(n 偶)a^n = a^{n/2} \cdot a^{n/2} \quad (n \text{ 偶})

分治,但只递归一半 →O(log⁡n)O(\log n)。

最近点对

平面上nn 个点,求最近的点对距离。

1. 按 x 排序,从中间切分成左右两半
2. 递归求左右的最近距离 d = min(dL, dR)
3. 关键:只需检查中间带状区域(宽 2d)内的点
   - 该区域内每个点最多只需和后继 7 个点比较(鸽笼原理)
4. 合并答案

复杂度:T(n)=2T(n/2)+O(n)T(n) = 2T(n/2) + O(n) →O(nlog⁡n)O(n \log n)。

第 3 步是分治的精髓:合并不能是O(n2)O(n^2),必须利用子问题的解把合并降到O(n)O(n)。

逆序对计数

归并排序的副产品:

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],贡献m−im - i 个逆序对。

线段树(分治数据结构)

线段树本身就是分治结构:每个节点管一个区间,分成左右两半递归。

查询/修改: O(log n)  —— 沿着分治树走
建树:      O(n)

分治优化 DP

形如dp[i]=min⁡j<i(dp[j]+w(j,i))dp[i] = \min_{j < i} (dp[j] + w(j, i)) 的转移,若ww 满足四边形不等式 / 决策单调性,可用分治优化到O(nlog⁡n)O(n \log n)。

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))
  • 爆栈:深度超过10510^5 就要警惕。树的退化链(一条链)会让"看起来O(log⁡n)O(\log n) 深"的递归变成O(n)O(n)
  • 重复计算:没有记忆化 → 指数复杂度(斐波那契朴素递归是O(2n)O(2^n))
  • 在递归里声明大数组:每帧都分配,栈迅速耗尽。用全局数组或堆
  • 分治的合并写成O(n2)O(n^2) → 总复杂度退化
  • mid 计算溢出:l + (r - l) / 2
  • 归并排序的稳定性:写成 a[i] < a[j] 会破坏稳定性(相等时取了右边)
  • 快排的 pivot 选择:总选 a[r] 在已排序数据上是O(n2)O(n^2)。用随机化或三数取中
  • 递归改循环时的边界:迭代版的中序遍历、归并排序的区间端点容易差一