递归与分治
递归与分治
递归描述函数怎样调用自身,分治描述问题怎样分解、求解与合并。本专题从函数任务和返回值出发,串联数值汇总、字符串处理、树构造、排序计数、空间划分及代数计算。新增十题按简单、中等、中高难度和高难度递进;各题的完整代码、执行过程和练习集中在独立题目文档中。
从递归任务到分治结构
设计递归函数时,先说明一次调用负责什么任务,再给出能够直接处理的边界,并保证每次子调用都会接近边界。
例如猴子吃桃每次把剩余天数减少1,汉诺塔把移动圆盘的任务交给两个规模更小、柱子角色不同的子任务。调用次数、调用深度与输出量需要分别分析;使用递归本身不保证高效。
分治通常将原问题分解成若干较小的同类子问题,求出它们的结果,再合成为当前答案。分析时应明确:
- 分解后是否覆盖原问题,是否遗漏或重复处理元素?
- 子调用的输入与返回值是什么,两个子任务是否真的需要分别求解?
- 当前层凭什么能从子问题结果得到正确答案?
- 子问题是否严格变小,边界能否正确处理?
子任务的执行顺序还要服从题目约束。汉诺塔必须按顺序执行两个移动任务;排序和下面的基础题则分别汇总左右位置区间的结果。
快速幂按幂的性质分解表达式后,只求一次半次幂并复用结果。按广义分治讲解,它体现“分解、求解、合成”;按一次只进入一个更小子问题的分类,它也具有减半减治结构。分析复杂度时,应按实际执行的一次子调用计费。
分治基础 三种返回值
建议按以下顺序学习,重点比较返回值设计与合并工作量:
| 学习顺序 | 题目 | 子调用返回什么 | 当前层怎样合并或连接 |
|---|---|---|---|
| 1 | 同时求数组的最大值与最小值 | 两个极值 | 分别比较两侧的最小值和最大值 |
| 2 | 最长公共前缀 | 一组字符串的公共前缀 | 从首字符开始合并两个前缀 |
| 3 | 有序数组构造平衡二叉搜索树 | 一棵子树的根节点 | 创建当前根,连接左右子树 |
第一题训练固定大小摘要的汇总;第二题的摘要长度可变,合并需要字符比较;第三题直接构造一种数据结构,结果是节点及其连接关系。
这三题都按中点划分,但需要检查的边界不同:极值题拒绝空列表,公共前缀题对空列表返回空字符串,树构造对空区间返回 None。边界应由任务含义决定。
从基础题进入合并、空间与代数专题
合并与统计
合并排序分别求解左右排序子问题,再线性合并有序列表。逆序对沿用这个结构,在取出右侧较小元素时,批量统计它与左侧剩余元素的配对。
学习路线为:最大最小值的常数工作合并 → 合并排序的线性合并 → 逆序对的排序与计数合并。算法中出现两次规模减半的子调用时,总时间还取决于当前层的额外工作。
合并k个有序数组(中等)把线性归并推广到多个已有序输入,通过按数组个数均衡划分,控制每个元素经历的合并层数。
重要逆序对(中高难度)沿用普通逆序对的三类位置划分,但条件变为 。排序与配对判断需要分开,当前层先用单调双指针计数,再合并列表;不能直接复用普通逆序对的取元素计数规则。
快速排序、数组中第k个最大元素和两个有序数组的中位数可用于进一步比较分区、选择与缩小候选范围的规则。
构造与空间划分
平衡搜索树通过中点划分构造左右子树;棋盘覆盖把空间分成四个区域,并通过当前层的骨牌安排,使子区域满足同类问题的条件。循环赛日程表则用较小规模的安排构造整体赛程。
对构造题,除了证明结果合法,还需计算输出本身的规模。返回一棵含 个节点的树,需要线性的节点存储,即使递归栈只有对数深度。
四叉树构建与二值图像压缩(中等)在区域一致时停止,否则四分。它用前缀和避免重复扫描区域,输出树的大小随图像结构变化,完整预处理仍需访问全部像素。
二维有序矩阵查找(中等)在中间列确定分界行,排除左上、右下区域,再递归查找左下、右上。先证明哪些位置可以排除,才能确定正确的子问题范围。
平面最近点对(高难度)按横向位置均衡划分,合并时必须检查跨侧点对。几何约束把条带中每个点的候选限制为常数个;子调用还返回纵向顺序,避免每层重新排序。这是“先证明合并工作量,再实现分治”的进阶实例。
用代数关系减少乘法分支
从快速幂的结果复用出发,继续学习 Karatsuba大整数乘法和 Strassen矩阵乘法(均为高难度)。前者把四个半长乘法改为三个,后者把八个半阶矩阵乘法改为七个;增加的加减工作必须与减少的乘法一起计费。
两题可按“展开原公式 → 构造较少的子乘积 → 重组并验证 → 分析递推”学习。整数乘法的规模是位数,矩阵乘法的规模是阶数;减少递归分支能降低渐近指数,但不能由此断言教学实现对所有小输入都更快。
递推与候选排除
约瑟夫环通过较小圆环的答案及编号映射构造当前答案;木材加工依靠可切段数的单调性二分候选长度;费解的开关枚举第一行的按法,再逐行唯一确定后续操作。
这些题目共同训练“利用结构减少工作”,具体依据分别是编号关系、单调性和状态约束。应说明各题实际使用的方法,而不是将目录中的全部题目都归为同一种分治算法。
比较复杂度时同时看三个因素
对于均衡划分的典型分治结构,可以用运行时间递推式表示:
其中 是实际执行的子调用数量, 是子问题规模, 是分解与合并等当前层额外工作。它描述的是时间,不是题目答案的数值递推式;应用时还需要补充边界及不均匀划分的情况。
| 实例 | 实际子调用 | 当前层工作 | 时间结论 |
|---|---|---|---|
| 快速幂 | 一次,指数约减半 | 常数次算术操作 | 单位成本模型下 |
| 最大最小值 | 两次,区间约减半 | 常数次极值比较 | |
| 最长公共前缀 | 两次,字符串个数约减半 | 比较并生成两个前缀的公共部分 | 上界 , 为最长字符串长度 |
| 平衡搜索树构造 | 两次,选根后分成左右区间 | 创建一个节点并连接子树 | 非空输入 |
| 合并排序与逆序对 | 两次,元素个数约减半 | 线性合并或归并计数 | 至少两个元素时 |
| 合并k个有序数组 | 两次,数组个数约减半 | 合并两组有序结果 | , 为总元素数 |
| 二维有序矩阵查找 | 至多两次,列数约减半且行范围分开 | 扫描中间列并排除区域 | 非空矩阵上界 , 为行列数 |
| 四叉树构建 | 非一致区域四次,边长减半 | 用前缀和判断区域并连接四子树 | 含预处理 , 为边长 |
| 重要逆序对 | 两次,元素个数约减半 | 双指针计数后线性归并 | 至少两个元素时 |
| 平面最近点对 | 两次,点数约减半 | 纵向归并与有限条带候选检查 | ,含初始排序 |
| Karatsuba大整数乘法 | 三次,位数约减半,和可能多一位 | 线性位数成本的加减与移位 | 按位成本 , 为最大位数 |
| Strassen矩阵乘法 | 七次,补齐矩阵阶数减半 | 矩阵加减与块重组 | 单位标量成本 |
各题中的 表示各自的输入规模。只看递归深度会漏掉其他分支的工作,只看子调用数量又会漏掉合并成本。
空间分析同样要分开考虑调用栈、中间结果与输出。下标区间可以避免复制输入列表,但返回前缀可能创建新字符串,构造树则会创建新节点;具体实现决定哪些存储同时存活。
学习与核对方式
阅读每道题时,先用主示例手画调用关系,再按程序返回顺序核对结果;之后运行文档中的 Python 主实现,并检查空输入、单元素、重复值或奇数长度等适用边界。
新增十题的建议顺序是:三道基础题 → 多路合并与二维查找 → 四叉树 → 重要逆序对 → Karatsuba → 最近点对 → Strassen。进入重要逆序对前先完成普通逆序对;进入最近点对前先掌握合并排序中的有序结果维护。最后横向比较各题的子问题数、合并成本和输出规模。
用题目文档的“易错点”检查自己的理解,再独立完成“课堂练习”后展开参考答案。方法串联可结合2026年秋第4次课,整体分类可参考算法概览。
