“这道题能不能递归”通常不是最有价值的问题。只要愿意维护状态，很多循环都能写成递归，很多递归也能改成循环。真正要问的是：哪种组织方式最清楚、复杂度可接受、边界可证明，并符合题目要求的输出。
五个概念先分开
| 概念 | 核心关注 | 典型信号 |
|---|---|---|
| 递归 | 用更小实例定义当前实例 | 树结构、自相似、嵌套语法 |
| 分治 | 独立求子问题并合并 | 对半、象限、有序两半、跨区间关系 |
| 迭代 | 显式维护推进状态 | 单链式依赖、规模很深、状态很少 |
| 动态规划 | 复用重叠子问题 | 相同参数反复出现、最值/计数状态 |
| 回溯 | 枚举选择并撤销状态 | 需要所有方案、约束满足、剪枝 |
这些类别可以组合。记忆化搜索是递归 + DP；归并排序是递归实现的分治；用显式栈做 DFS 是迭代实现的搜索；表达式所有括号化结果既有分治，也枚举了所有组合。
递归还是迭代
优先递归的情况：
- 数据本身是树或嵌套结构；
- 每层合同简单，深度有可靠上界；
- 返回阶段需要自然地组合子结果；
- 递归写法能直接对应正确性证明。
优先迭代的情况：
- 每次只有一个下一状态，返回阶段只做简单累积；
- 深度可能达到十万或更多；
- 需要精确控制内存和暂停/恢复；
- 自底向上顺序可以自然生成子问题。
ANTI反例 · 链表很“递归”，所以一定递归
单链表结构确实自相似，但遍历百万结点时递归深度也可能是一百万。普通循环既保留线性语义，又避免调用栈溢出，通常更稳妥。
分治还是动态规划
关键区别不是有没有递推式，而是子问题是否大量重叠：
| 观察 | 分治倾向 | DP 倾向 |
|---|---|---|
| 子问题范围 | 通常不相交或交互很少 | 不同路径反复到达相同状态 |
| 子结果使用 | 当前层合并后结束 | 多个状态持续复用同一答案 |
| 常见结构 | 左右半区、象限 | 状态 DAG、前缀、容量、位置 |
| 优化重点 | 均衡拆分与 Combine | 状态定义、转移与计算顺序 |
12E01 · Function虽然写成递归，但核心优化是缓存重叠状态，属于记忆化 DP 的入口。归并排序的左右区间不重叠，缓存没有意义，属于标准分治。
WARN易错点 · 看到递归式就称为分治
fib(n)=fib(n-1)+fib(n-2) 描述了数学递归，却产生大量重叠子问题。若不辨认重复状态，“Divide–Conquer”标签会掩盖指数复杂度。
分治还是回溯
分治把多个子问题的答案组合成一个原问题答案；回溯沿决策树尝试候选，需要在返回时撤销选择，以继续探索其他方案。
例如：
- 棋盘覆盖：四个象限都必须解决，彼此独立，属于分治；
- N 皇后：某行放在哪一列是候选选择，失败要撤销并尝试别列，属于回溯；
- 表达式括号化：按最后运算符拆左右子表达式，并组合全部结果，兼有分治与枚举特征。
判断题眼是：当前层是在拆解必做组件，还是在尝试互斥候选？
IDEA直觉 · 分治是拼图，回溯是岔路
分治的子问题像拼图的不同区域，通常都要完成；回溯的分支像岔路，选择一条后可能失败，再退回尝试下一条。
何时只沿一侧
若划分能确定答案只可能位于一个子区间，就不应递归全部子问题。12E07 · 求第 k 小的数划分后只进入包含目标秩的一侧；二分查找也是同样原则。
但排序必须让所有元素有序，所以归并排序和快速排序都需要处理两侧。是否能丢弃一侧，由最终输出合同决定。
何时避免构造完整对象
如果题目只查询一个位置、一个计数或一个摘要，先寻找逆向映射或聚合量：
- 巨大递归字符串查字符：只追踪目标下标；
- 区间和计数：转成前缀和数对；
- 统一区域判断：可用前缀和避免反复扫描；
- 只求第 k 小：无需完整排序。
PROP性质 · 输出合同决定必要工作
输出完整数组通常至少需要线性时间；只输出一个值可能允许丢弃大量子结构。先读清“要输出什么”，再决定是否真的要构造题面描述的全部过程。
方法选择决策表
| 问题 | 若答案为“是” | 下一步 |
|---|---|---|
| 数据或定义天然自相似吗？ | 可先写递归合同 | 检查深度与规模递减 |
| 能拆成近似独立的小问题吗？ | 尝试分治 | 明确 Combine 与递推式 |
| 相同参数状态会重复出现吗？ | 尝试记忆化/DP | 定义状态与缓存键 |
| 需要枚举互斥选择并恢复现场吗？ | 尝试回溯 | 定义选择、约束、撤销与剪枝 |
| 每次只有唯一下一状态且深度很大吗？ | 优先迭代 | 找循环不变量 |
| 只查询完整生成物的一小部分吗？ | 尝试逆向定位或摘要 | 避免指数构造 |
从递归到 DP 的迁移示例
设 ways(n) 表示走到第 n 级的方案数，递归式为：
朴素递归重复求相同 ways(k)；加入缓存后每个状态求一次；进一步按 0..n 顺序填表，便得到迭代 DP。三种写法使用同一状态合同，差别在计算图是否展开、是否缓存、以何种顺序执行。
从递归到显式栈的迁移示例
对二叉树后序处理，帧除了结点还需保存“孩子是否已经处理”。一种常见做法是把 (node,visited) 入栈：
- 第一次弹出时，把自身以
visited=true压回，再压入孩子； - 第二次弹出时，孩子结果已经就绪，执行 Combine。
这个标记正是递归调用中“返回地址和当前阶段”的显式版本。
工程边界
在竞赛与课程 Lab 中还要检查：
- C++ 不保证尾递归优化；
- 深递归可能栈溢出；
- 中点建议写成
left+(right-left)/2； - 计数、前缀和与倍乘比较常需 64 位；
- 多解输出必须固定顺序，或使用合适的 Special Judge；
- 大输出题的时间和输出上限应与题意匹配。
地毯填补原题允许多种合法方案，本地 Lab 明确只接受固定“中心优先、四象限固定顺序”的规范输出。这不是算法理论的变化，而是自动评分合同需要可复现的 oracle。
自检
- 记忆化搜索与分治可以同时出现在一个算法里吗？
- 为什么 N 皇后通常称为回溯，而棋盘覆盖称为分治？
- 把递归改为迭代后，正确性证明是否全部作废？
参考答案
- 可以。算法可先分解问题；若子问题状态重叠，再缓存结果。分类用于指出主要结构，不是互斥标签。
- N 皇后在每一行尝试互斥候选，冲突后必须撤销；棋盘覆盖的四个象限都是完整答案不可缺少的独立组成部分。
- 不会。函数契约常可转化为循环不变量，状态依赖和数学递推仍然成立；需要重新证明的是显式执行顺序与状态更新保持这些不变量。
参考与下一步
- OI Wiki：分治用于复核分治的适用结构与复杂度。
- Hello 算法：分治提供分治与其他策略的直观对照。
- 完成本章后，可进入贪心算法与动态规划，继续比较“局部选择”“状态复用”和“独立子问题”三种结构。