写递归前最重要的动作不是敲出函数名，而是补完一句话：

当参数为……时，这个函数保证返回……；或者保证完成……。

这句话决定基本情况、递归参数和返回阶段。若它含糊，代码通常会出现边界错一位、重复工作或“看似能跑但无法证明”的问题。

递归合同的四个组成部分

DEF定义 · 递归函数契约

递归函数契约至少包含：

1. 子问题语义：参数描述哪个范围、对象或状态；
2. 基本情况：哪些最小实例无需继续递归；
3. 规模递减：递归实参在什么度量下严格更小；
4. 组合规则：子调用返回后，当前调用怎样履行自己的承诺。

以半开区间求和为例，定义 sum(a,left,right) 为数组区间 [left,right) 的元素和。合同一旦确定，四部分自然得到：

• left==right 时空区间和为 0；
• 否则递归求 [left+1,right)；
• 当前答案是 a[left] + 子问题答案；
• 度量 right-left 每次减少 1。

long long rangeSum(const std::vector<int>& values, int left, int right) {
    if (left == right) return 0;
    return values[left] + rangeSum(values, left + 1, right);
}

recursive-range-sum.cpp

WARN易错点 · 合同与代码使用了不同区间

若口头说的是 [left,right)，基本情况却写成 left>right，函数会在 left==right 时访问越界。闭区间与半开区间都能正确，但一份实现只能选择一套语义并贯彻到底。

基本情况不是“随便拦一下”

基本情况有两个职责：给最小问题正确答案，并阻止继续访问不存在的子结构。检查它时要问：

• 空对象是否可能出现？
• 单元素是否已经足够简单？
• 输入越过正常定义域时，题目规定怎样归一化？
• 多个结束条件的顺序是否会影响数组下标安全？

12E01 · Function就是典型例子。参数可能为负数或超过 20，因此必须先应用定义中的边界规则，再访问 memo[a][b][c]。缓存只是优化，安全的定义域裁剪才是合同的一部分。

ANTI反例 · 先查缓存再判边界

if (ready[a][b][c]) return memo[a][b][c]; // a 可能为 -1 或 100
if (a <= 0 || b <= 0 || c <= 0) return 1;

这段程序的数学递归式可能记对了，执行却在进入递归前已经越界。基本情况的顺序属于正确性，而不只是性能细节。

怎样证明规模真的变小

“参数看起来变了”不能证明终止。应该选择一个取非负整数的度量 $m(state)$，并证明每个递归分支都满足：

$$0\le m(next)<m(current).$$

常见度量包括：

子问题	规模度量
数组区间 [l,r)	r-l
树结点	当前子树结点数或高度
整数快速幂	非负指数 e
棋盘覆盖	棋盘边长或指数 k
巨大递归字符串定位	当前覆盖长度

快速幂把指数 e 变成 e/2，所以深度为 $O(\log e)$。12E04 · Pow(x,n)还要求先把 32 位指数提升到 64 位，再对负指数取反，否则 INT_MIN 会在规模归一化阶段溢出。

返回值递归与副作用递归

递归不一定返回数值。12E02 · 幂次方可以让函数返回一段规范字符串；12E03 · 南蛮图腾可以让函数返回整张字符画；棋盘覆盖也可以在固定顺序下直接输出。

两种设计的权衡是：

方式	优点	风险
返回完整子结果	合同清楚，便于测试和重组	可能复制大量对象
修改共享对象/直接输出	避免部分复制，符合在线生成	顺序成为合同，回溯恢复更难

输出型递归尤其要明确“先输出当前层，还是先递归子层”。同一组递归调用若前后顺序不同，可能产生完全不同的标准输出。

重叠子问题与记忆化

如果不同调用路径会到达同一参数状态，朴素递归会建立一棵含大量重复结点的调用树。记忆化把“参数 → 返回值”保存下来，使每个状态只真正展开一次。

PROP性质 · 能缓存的前提

只有当函数返回值完全由参数决定，且调用没有影响答案的隐藏可变状态时，才能安全地按参数缓存。换言之，递归合同必须近似一个纯函数。

Function 的有效状态只有 21³ 个，即使输入有十万组，每个状态仍只需计算一次。但这不代表所有递归都属于动态规划：若子问题互不重叠，缓存不会带来收益；若任务要求枚举不同方案，合并时还必须保留每条方案而不能只缓存一个数值。

完整建模示例：二分求幂

令 power(x,e) 的合同为“返回 $x^e$，其中 $e$ 是非负整数”。

• 基本情况：e==0 时返回 1；
• 子问题：只计算一次 half=power(x,e/2)；
• 合并：先得到 half*half，若 e 为奇数再乘 x；
• 规模：e 变为 floor(e/2)。

PROOF正确性说明

若 $e=2q$，则 $x^e=(x^q{)}^2$；若 $e=2q+1$，则 $x^e=(x^q{)}^{2}x$。基本情况 $x^0=1$ 正确，且 $q<e$（当 $e>0$），因此按指数归纳可得所有非负指数都正确并终止。

O(·)复杂度 · 不要重复求同一个半幂

只求一次 half 时递推为 $T(e)=T(e/2)+O(1)=O(\log e)$。若代码直接写 power(x,e/2)*power(x,e/2)，递推变成 $2T(e/2)+O(1)=O(e)$，数学公式相同，程序复杂度却不同。

自检

1. factorial(n) 只写 if (n==1) return 1，在什么输入上会失效？
2. 为什么半开区间递归常把空区间作为基本情况？
3. 记忆化能否修复一个规模不递减的递归？

参考答案

1. n==0 时不会命中基本情况并继续走向负数；若合同允许 0，应使用 n==0 或覆盖 n<=1，同时明确负数是否非法。
2. 空区间 [l,l) 是拆分后的自然结果，给它单位元（和为 0、积为 1、结果集合按题意定义）能减少边界分支，并让左右子区间无重叠。
3. 不能。若状态在写入缓存前再次调用自身，仍可能无限递归；终止性必须先由规模严格递减保证，缓存只消除已经正确终止的重复计算。

延伸阅读

• Hello 算法：递归展示“递”与“归”的执行过程。
• 下一节调用栈、递归树和迭代改写把这份静态合同放到真实运行时中观察。