第七章：递推、递归与分治

许多问题都可以从规模更小的同类问题出发。区别在于：递推先确定小规模答案，再按依赖顺序逐步扩大；递归让函数暂时等待子问题返回；分治则把一个较大的问题拆成若干部分，分别求解后再合并。

本章先用同一个走楼梯问题比较递推与递归，再从合并两个有序序列出发建立分治和归并排序。逆序对与快速幂用于说明：掌握一种结构后，更重要的是识别它还能解决哪些问题。

阅读前需要掌握数组、函数和参数传递。

1. 从小规模答案递推到大规模答案

1.1 递推的四个组成部分

考虑下面的问题：一段楼梯共有 $n$ 级，每次只能向上走 $1$ 级或 $2$ 级，求恰好走到第 $n$ 级的方案数。

数据范围为 $1\le n\le45$ 。

直接列举每一步走一级还是两级，会反复遇到相同的剩余楼梯。可以换一个角度，按最后一步分类：

最后走 $1$ 级，此前必须已经到达第 $i-1$ 级；
最后走 $2$ 级，此前必须已经到达第 $i-2$ 级。

两类走法互不重叠，并且覆盖了到达第 $i$ 级的全部方案。令 $f_i$ 表示到达第 $i$ 级的方案数，便有

f_i=f_{i-1}+f_{i-2}.

还需要确定最小规模的答案。到达第 $0$ 级表示一步也不走，这是一种空方案，所以 $f_0=1$ ；到达第 $1$ 级只能走一步，所以 $f_1=1$ 。

从小到大计算时，求 $f_i$ 所需的 $f_{i-1}$ 和 $f_{i-2}$ 都已经得到。以下用全局数组 $f$ 保存各级答案。

int f[50];

f[0] = 1;
f[1] = 1;
// f[i] 只依赖前两个已经求出的状态
for (int i = 2; i <= n; ++i)
{
    f[i] = f[i - 1] + f[i - 2];
}

前几个状态依次为 $1,1,2,3,5$ 。例如，到达第 $4$ 级的五种走法为

1+1+1+1
1+1+2
1+2+1
2+1+1
2+2

这个例子包含递推的四个基本部分：

状态： $f_i$ 表示什么；
初值：最小规模的答案是什么；
转移：怎样由较小状态得到当前状态；
顺序：计算当前状态时，它依赖的状态是否已经得到。

本题的时间复杂度为 $O(n)$ ，数组空间为 $O(n)$ 。只求最终答案时，可以只保留相邻的两个状态，把额外空间降为 $O(1)$ 。本题中 $f_{45}=1836311903$ ，可以用 $\texttt{int}$ 保存；若继续扩大 $n$ ，需要重新检查数值范围。

2. 同一个关系也可以写成递归

2.1 让函数等待子问题返回

上一节的关系也可以直接写成函数：要求第 $n$ 级的方案数，就分别求第 $n-1$ 级和第 $n-2$ 级的方案数，再把两者相加。

long long solve(int n)
{
    // 递归出口：最小规模可以直接得到答案
    if (n == 0 || n == 1)
    {
        return 1;
    }
    return solve(n - 1) + solve(n - 2);
}

调用 $solve(4)$ 时，函数不会立刻得到答案，而是继续提出更小的问题：

solve(4)
├── solve(3)
│   ├── solve(2)
│   └── solve(1)
└── solve(2)

当参数缩小到 $0$ 或 $1$ 时，函数可以直接返回。随后各层调用从下向上取得子问题的结果，最终得到 $solve(4)=5$ 。

一段递归通常需要回答三个问题：

当前函数负责解决什么规模的问题；
它怎样把任务交给规模更小的同类问题；
哪些最小规模可以直接回答，使递归停止。

证明递归一定结束时，应找出一个每次严格减小并且存在下界的量。本例中这个量就是 $n$ 。

2.2 递归表达关系，递推安排计算

递归代码与上一节的递推式表达了同一个关系，但计算过程不同。上面的调用树中， $solve(2)$ 被计算了两次；规模继续增大时，同一个参数会被反复调用，总调用数呈指数增长。递归深度虽然只有 $O(n)$ ，工作量却远大于 $O(n)$ 。

递推把每个 $f_i$ 只计算一次，因此更适合直接求本题答案。二者不是互相替代的两个公式，而是两种组织计算的方式：

比较项	递推	递归
计算方向	从已知的小状态推到大状态	从当前问题调用更小问题，再等待返回
必要条件	初值、转移和合法计算顺序	终止条件和严格缩小的问题规模
本题朴素实现	$O(n)$	指数级
常见优势	避免重复计算，运行过程清晰	代码贴近问题定义，适合描述分支与嵌套结构

若递归更容易描述问题，又存在重复子问题，可以保存已经算过的结果，这就是记忆化。它将在动态规划章节继续讨论。

2.3 每层调用都有自己的现场

递归函数的每次调用都会保存自己的参数、局部变量和返回位置。下层调用结束后，程序回到上层尚未完成的位置继续执行。

按值传递的参数在每层都有独立副本；全局数组和全局计数器则由所有层共同使用。修改局部参数不会改变上层保存的值，修改全局状态却不会在返回时自动恢复。这个区别是后续理解搜索与回溯的基础。

递归还会占用调用栈。线性递归若深入到 $10^5$ 层，可能在完成计算前就发生栈溢出。分析递归时，需要分别检查递归深度和总调用数，不能把两者混为一谈。

3. 先学会合并两个有序序列

分治中的“拆分”往往容易，真正决定算法是否高效的是“合并”。在讨论归并排序前，先解决一个更具体的问题：怎样把两个已经有序的序列合成一个有序序列。

以左序列 $[2,5,7]$ 和右序列 $[1,6]$ 为例。两个序列各自有序，所以它们尚未取出的最小元素一定在各自开头。每次只需比较这两个候选，取较小者放入结果。

左侧候选	右侧候选	本次取出	当前结果
$2$	$1$	$1$	$[1]$
$2$	$6$	$2$	$[1,2]$
$5$	$6$	$5$	$[1,2,5]$
$7$	$6$	$6$	$[1,2,5,6]$
$7$	右侧已空	$7$	$[1,2,5,6,7]$

用两个指针分别指向两段尚未取出的第一个元素，就能在线性时间内完成合并。以下片段把 $a[l\ldots mid]$ 和 $a[mid+1\ldots r]$ 合并到辅助数组 $b$ ，两段在合并前都已经有序。

int i = l, j = mid + 1, k = l;
// i 和 j 始终指向两段尚未取出的最小元素
while (i <= mid && j <= r)
{
    if (a[i] <= a[j])
    {
        b[k++] = a[i++];
    }
    else
    {
        b[k++] = a[j++];
    }
}
// 一段耗尽后，另一段的剩余部分可以直接接到末尾
while (i <= mid)
{
    b[k++] = a[i++];
}
while (j <= r)
{
    b[k++] = a[j++];
}

在循环过程中， $b[l\ldots k-1]$ 始终保存已经取出元素的有序结果。一侧取空后，另一侧剩余元素本来就有序，按原顺序接到末尾即可。

4. 分治与归并排序

4.1 把“排序”拆成三个阶段

现在回到一个无序区间。若直接合并，它的左右部分并不一定有序，上一节的方法无法使用。可以先把区间分成两半，分别排好，再合并两个有序结果：

分解：把当前区间分成左右两半
求解：分别把左右两半排好
合并：把两个有序区间合成一个有序区间

左右两半仍是排序问题，可以继续使用同样的方法；当区间只剩一个元素时，它天然有序，不必继续拆分。这就是归并排序中的分治结构。

[5, 2, 7, 1]
        ↓ 分解
[5, 2]        [7, 1]
  ↓              ↓
[5] [2]        [7] [1]
  ↓ 合并          ↓ 合并
[2, 5]        [1, 7]
        ↓ 合并
    [1, 2, 5, 7]

4.2 归并排序的核心实现

以下用全局数组 $a$ 保存待排序序列，用 $b$ 作为所有递归层共用的辅助数组。调用 $merge\_sort(1,n)$ 即可完成排序。

const int N = 500000 + 10;
int a[N], b[N];

void merge_sort(int l, int r)
{
    // 单元素区间天然有序
    if (l >= r)
    {
        return;
    }

    int mid = (l + r) / 2;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);

    // 递归返回后，左右两段已经分别有序
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r)
    {
        if (a[i] <= a[j])
        {
            b[k++] = a[i++];
        }
        else
        {
            b[k++] = a[j++];
        }
    }
    while (i <= mid)
    {
        b[k++] = a[i++];
    }
    while (j <= r)
    {
        b[k++] = a[j++];
    }
    // 写回原数组，供上一层继续合并
    for (int p = l; p <= r; ++p)
    {
        a[p] = b[p];
    }
}

递归处理结束后， $a[l\ldots mid]$ 和 $a[mid+1\ldots r]$ 已经分别有序。合并循环每次取两个候选中的较小值，因此写入 $b$ 的部分始终有序；最后把 $b[l\ldots r]$ 写回 $a$ ，上层调用才能使用这一段的排序结果。

每次把区间大致分成两半，共有 $O(\log n)$ 层。每一层参与合并的区间总长度为 $n$ ，工作量为 $O(n)$ ，所以总时间复杂度为 $O(n\log n)$ 。辅助数组需要 $O(n)$ 空间，递归调用栈还需要 $O(\log n)$ 空间。

不能只看到“对半递归”就直接写出 $O(n\log n)$ 。这个结论还依赖于每层合并的总工作量为 $O(n)$ 。

5. 在归并时统计逆序对

例题：逆序对。

给定一个长度为 $n$ 的序列，统计满足 $i<j$ 且 $a_i>a_j$ 的位置对数量。相等元素不构成逆序对。

数据范围为 $1\le n\le5\times10^5$ ，元素是不超过 $10^9$ 的正整数。

逐个枚举数对需要 $O(n^2)$ 时间。归并排序在合并左右两段时，恰好能够集中处理跨越中点的逆序对。

仍以左段 $[2,5,7]$ 和右段 $[1,6]$ 为例。第一次比较时，右侧的 $1$ 小于左侧的 $2$ 。由于左段已经有序， $1$ 也一定小于左侧尚未取出的 $5$ 和 $7$ ，因此一次得到 $3$ 个逆序对。后来右侧的 $6$ 小于左侧剩余的 $7$ ，再得到 $1$ 个。

一般地，合并时若 $a_i>a_j$ ，那么 $a_i,a_{i+1},\ldots,a_{mid}$ 都大于 $a_j$ ，新增逆序对数量为

mid-i+1.

下面给出加入计数后的完整核心函数。函数返回当前区间中的逆序对数量，同时把当前区间排好。

const int N = 500000 + 10;
int a[N], b[N];

long long merge_sort(int l, int r)
{
    if (l >= r)
    {
        return 0;
    }

    int mid = (l + r) / 2;
    // 左右两段内部的逆序对由递归统计
    long long ans = merge_sort(l, mid) + merge_sort(mid + 1, r);

    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r)
    {
        if (a[i] <= a[j])
        {
            b[k++] = a[i++];
        }
        else
        {
            // a[j] 小于左段所有尚未取出的元素
            ans += mid - i + 1;
            b[k++] = a[j++];
        }
    }
    while (i <= mid)
    {
        b[k++] = a[i++];
    }
    while (j <= r)
    {
        b[k++] = a[j++];
    }
    for (int p = l; p <= r; ++p)
    {
        a[p] = b[p];
    }
    return ans;
}

一个逆序对只有三种位置关系：完全在左半、完全在右半，或跨越左右两半。前两类由递归统计，第三类由当前层的合并统计，因此每个逆序对恰好计算一次。

比较相等元素时优先取左侧，因为逆序对要求严格大于。最多可能有

\frac{n(n-1)}{2}

个逆序对；当 $n=5\times10^5$ 时，这个值超过 $\texttt{int}$ 范围，计数必须使用 $\texttt{long long}$ 。排序与统计同时完成，时间复杂度为 $O(n\log n)$ 。

6. 另一种“规模减半”：快速幂

给定非负整数 $a,b$ 和正整数 $m$ ，计算 $a^b$ 除以 $m$ 的余数。规定 $a^0=1$ 。

数据范围为 $0\le a\le10^9$ ， $0\le b\le10^{18}$ ， $1\le m\le10^9$ 。

按照乘方定义连续乘 $b$ 次，需要 $O(b)$ 时间。指数可以按二进制拆分。例如

13=8+4+1,

因此

a^{13}=a^8\cdot a^4\cdot a.

从 $a^1$ 开始不断平方，就能依次得到 $a^2,a^4,a^8,\ldots$ 。指数当前二进制位为 $1$ 时，把对应的幂乘入答案；处理完这一位后，将指数整除 $2$ 。

long long power(long long a, long long b, long long mod)
{
    long long ans = 1 % mod;
    a %= mod;
    while (b > 0)
    {
        // 最低位为 1 时，选取当前这一项
        if (b % 2 == 1)
        {
            ans = ans * a % mod;
        }
        // 推进到下一二进制位，并舍去已经处理的最低位
        a = a * a % mod;
        b /= 2;
    }
    return ans;
}

设最初的底数、指数和模数分别为 $A$ 、 $B$ 和 $M$ 。每轮开始时都有

ans\cdot a^b\equiv A^B\pmod M.

若 $b$ 为奇数，先把当前的 $a$ 乘入 $ans$ ，剩余指数便成为偶数；随后把 $a$ 平方、把 $b$ 折半，上式仍然成立。循环结束时 $b=0$ ，所以 $ans$ 就是所求余数。

每轮都把 $b$ 折半，时间复杂度为 $O(\log(b+1))$ ，额外空间为 $O(1)$ 。初值写成 $1\bmod mod$ ，可以正确处理 $b=0$ 且 $mod=1$ 的情况。本节给定 $mod\le10^9$ ，两个余数相乘可以由 $\texttt{long long}$ 保存；若模数接近 $\texttt{long long}$ 上界，还需要专门处理乘法溢出。

快速幂和归并排序解决的问题不同，但都利用了“把规模缩小一半”。归并排序还要合并两个子问题的结果；快速幂只需根据指数的奇偶决定是否额外乘一次。

7. 递归构造：幂次方表示

例题：NOIP 1998 普及组·幂次方。

把一个正整数写成若干个不同的 $2$ 的幂之和，并按指数从大到小输出。 $2^0$ 写成 2(0)， $2^1$ 写成 2；指数大于 $1$ 时，指数本身也要按同样规则表示。

数据范围为 $1\le n\le20000$ 。

例如， $5=2^2+2^0$ ，所以 $5$ 表示为 2(2)+2(0)。若要表示 $32=2^5$ ，指数 $5$ 仍需按相同规则展开，于是结果为 2(2(2)+2(0))。

递归函数 $print(n)$ 负责输出整数 $n$ 的完整表示。它先从高到低枚举 $n$ 的二进制位：

指数为 $0$ 时，直接输出 2(0)；
指数为 $1$ 时，直接输出 2；
指数大于 $1$ 时，先输出 2(，递归输出这个指数，再输出 )。

#include <bits/stdc++.h>
using namespace std;

void print(int n)
{
    // first 只控制当前递归层中加号的输出
    bool first = true;
    for (int k = 30; k >= 0; --k)
    {
        if ((n >> k) & 1)
        {
            if (!first)
            {
                cout << '+';
            }
            first = false;
            if (k == 0)
            {
                cout << "2(0)";
            }
            else if (k == 1)
            {
                cout << '2';
            }
            else
            {
                // 指数大于 1 时，按同样规则递归展开
                cout << "2(";
                print(k);
                cout << ')';
            }
        }
    }
}

int main()
{
    int n;
    cin >> n;
    print(n);
    return 0;
}

变量 $first$ 属于当前这一层调用，只记录本层是否已经输出过一项，因此连接符只会出现在相邻两项之间。递归调用处理的是指数 $k$ 。只要第 $k$ 位为 $1$ ，就有 $n\ge 2^k$ ；当 $k>1$ 时又有 $2^k>k$ ，所以递归参数严格减小，最终会到达指数 $0$ 或 $1$ 的直接输出规则。

这个例子与楼梯计数不同。递归不再用于返回一个数值，而是用于生成具有嵌套结构的输出。问题定义本身存在嵌套时，递归通常比循环更自然。

8. 从递归定义得到递推：数的计算

例题：NOIP 2001 普及组·数的计算。

以 $n$ 开始构造数列，可以立即停止，也可以在末尾加入一个不超过当前末项一半的正整数，再按相同规则继续。求合法数列的数量。

数据范围为 $1\le n\le1000$ 。

若当前末项为 $i$ ，有两类选择：

立即停止，得到 $1$ 个合法数列；
选择 $1$ 至 $\lfloor i/2\rfloor$ 中的一个数 $j$ 作为下一项，后续方案数等于以 $j$ 开始的合法数列数。

令 $f_i$ 表示以 $i$ 开始的合法数列数，按第二项分类可得

f_i=1+\sum_{j=1}^{\lfloor i/2\rfloor}f_j.

第二项不同的方案互不重叠，所有非空扩展又一定会选择其中一个 $j$ ，所以转移不重不漏。右侧只依赖比 $i$ 小的状态，可以从小到大计算。

int f[1010];

for (int i = 1; i <= n; ++i)
{
    // 立即停止先贡献 1 种方案
    f[i] = 1;
    // 枚举第二项 j，后续方案数就是 f[j]
    for (int j = 1; j <= i / 2; ++j)
    {
        f[i] += f[j];
    }
}

例如， $f_1=1$ ， $f_2=f_3=2$ ，因此

f_6=1+f_1+f_2+f_3=6.

直接按照转移求和的时间复杂度为 $O(n^2)$ ，空间复杂度为 $O(n)$ ，足以处理本题范围。若维护 $f$ 的前缀和，每个状态的区间求和还能降到 $O(1)$ ，总时间变为 $O(n)$ 。

这个过程再次说明：递归定义常常更接近题意，但真正计算时，可以根据依赖关系改写为递推，避免重复求解相同状态。

9. 复用有序结果：瑞士轮

例题：NOIP 2011 普及组·瑞士轮。

共有 $2n$ 名选手，排名规则为总分从高到低，总分相同时编号从小到大。每轮由当前排名相邻的两人比赛，实力较高者得 $1$ 分。经过 $R$ 轮后，输出第 $Q$ 名选手的编号。

数据范围为 $1\le n\le10^5$ ， $1\le R\le50$ ， $1\le Q\le2n$ ；选手实力互不相同。

最直接的做法是每轮比赛后重新排序，时间复杂度为 $O(Rn\log n)$ 。不过，一轮比赛并没有完全破坏上一轮的顺序。

按旧排名依次收集本轮胜者。所有胜者都增加 $1$ 分，因此任意两名胜者之间的分数差和编号优先级都没有改变，胜者序列仍然有序。败者都不加分，同理，败者序列也仍然有序。

于是，一轮结束后得到的不是一个任意乱序序列，而是两个分别有序的序列。使用本章开头的双指针合并，就能在线性时间内生成新排名。

#include <bits/stdc++.h>
using namespace std;

const int N = 200000 + 10;

struct Player
{
    int id, score, power;
};

int n, R, Q;
Player a[N], win[N], lose[N];

bool cmp(const Player &x, const Player &y)
{
    if (x.score != y.score)
    {
        return x.score > y.score;
    }
    return x.id < y.id;
}

int main()
{
    scanf("%d%d%d", &n, &R, &Q);
    for (int i = 1; i <= 2 * n; ++i)
    {
        scanf("%d", &a[i].score);
        a[i].id = i;
    }
    for (int i = 1; i <= 2 * n; ++i)
    {
        scanf("%d", &a[i].power);
    }

    // 先得到第 1 轮比赛所需的初始排名
    sort(a + 1, a + 2 * n + 1, cmp);
    for (int round = 1; round <= R; ++round)
    {
        int x = 0, y = 0;
        // 所有对局都按本轮开始时的排名进行
        for (int i = 1; i <= 2 * n; i += 2)
        {
            if (a[i].power > a[i + 1].power)
            {
                ++a[i].score;
                win[++x] = a[i];
                lose[++y] = a[i + 1];
            }
            else
            {
                ++a[i + 1].score;
                win[++x] = a[i + 1];
                lose[++y] = a[i];
            }
        }

        // win 和 lose 各自有序，线性合并即可得到新排名
        int i = 1, j = 1, k = 1;
        while (i <= n && j <= n)
        {
            if (cmp(win[i], lose[j]))
            {
                a[k++] = win[i++];
            }
            else
            {
                a[k++] = lose[j++];
            }
        }
        while (i <= n)
        {
            a[k++] = win[i++];
        }
        while (j <= n)
        {
            a[k++] = lose[j++];
        }
    }

    printf("%d\n", a[Q].id);
    return 0;
}

初始排序需要 $O(n\log n)$ 时间，每轮比赛和合并各需要 $O(n)$ 时间，总时间复杂度为 $O(n\log n+Rn)$ ，额外空间为 $O(n)$ 。

比赛必须先按照本轮开始时的名次全部完成，再统一合并胜者与败者。若处理一场比赛后立刻改变排名，就会影响本轮后续选手的配对。

这个例子没有把“归并”局限在归并排序中。只要一次更新后仍能得到少量有序序列，就可以考虑复用原顺序，再用线性合并恢复整体顺序。

10. 本章小结

递推需要明确状态、初值、转移和计算顺序。
递归需要明确函数职责、规模缩小方式和终止条件，并分别分析深度与总调用数。
分治包含分解、求解和合并；复杂度取决于递归层数与每层总工作量。
归并的核心是复用两个序列已经有序这一条件。
学会一个算法后，应继续寻找它维护的信息还能解决什么问题。逆序对复用了归并过程，瑞士轮复用了有序结果，快速幂则复用了规模减半的思想。