4.1 递归定义与数学归纳：沿构造过程证明
树、表达式、目录和协议消息都能由更小的同类对象组成。递归定义描述这种构造；归纳法沿着同一构造方向证明性质。二者互相对应，但用途不同。
一个完整的递归定义需要什么
以阶乘为例：
0! = 1
n! = n·(n-1)!，n≥1这里包含：
- 定义域：非负整数；
- 基础情况：直接定义
0!； - 递归规则：用更小的
(n-1)!定义n!； - 良基性：参数每次减少，最终到达 0。
只写：
f(n)=f(n+1)-1既没有基础值，也没有保证沿递归方向靠近基础情况，不能唯一确定一个可计算函数。
例如在非负整数上，f(n)=n+c 对任意整数常数 c 都满足这条关系。缺少初值首先造成解不唯一；这不等于所有解都不可计算。
数列的递归定义
斐波那契数列：
F₀=0
F₁=1
Fₙ=Fₙ₋₁+Fₙ₋₂，n≥2它需要两个基础值，因为递归规则读取前两项。数学定义没有规定必须用朴素递归程序计算；迭代、矩阵快速幂和快速倍增都可以计算同一序列。
“定义是什么”与“算法怎样算”要分开。
递归数据类型
一棵二叉树可以定义为：
Tree ::= Empty | Node(value, left: Tree, right: Tree)一个算术表达式：
Expr ::= Number(n)
| Add(left: Expr, right: Expr)
| Multiply(left: Expr, right: Expr)递归定义给出最小闭包：从基础构造器出发，有限次应用构造规则得到的对象属于该类型，没有由规则生成的对象不属于它。
下面是可保存为 TreeDemo.java 的完整 Java 21 示例。sealed 限定构造器种类，record pattern 拆开节点，Empty 是对象而非 null；Node 构造时拒绝空子树引用。假设展开后的节点数不超过 Integer.MAX_VALUE，且深度与分配量能被运行环境容纳。Java 21 已正式支持这里使用的 record pattern 与 switch 模式匹配。
import java.util.Objects;
public class TreeDemo {
sealed interface Tree permits Empty, Node { }
record Empty() implements Tree { }
record Node(int value, Tree left, Tree right) implements Tree {
Node {
Objects.requireNonNull(left);
Objects.requireNonNull(right);
}
}
static int size(Tree tree) {
return switch (tree) {
case Empty ignored -> 0;
case Node(var value, var left, var right) ->
1 + size(left) + size(right);
};
}
static Tree mirror(Tree tree) {
return switch (tree) {
case Empty ignored -> tree;
case Node(var value, var left, var right) ->
new Node(value, mirror(right), mirror(left));
};
}
public static void main(String[] args) {
Tree e = new Empty();
Tree t = new Node(1, new Node(2, e, e), new Node(3, e, e));
System.out.println(size(t)); // 3
System.out.println(mirror(mirror(t)).equals(t)); // true
}
}这里递归下降到严格的子树。若数据结构允许环，就不再是普通有限树；遍历必须增加 visited 集合或其他终止机制。
运行 javac TreeDemo.java 后执行 java TreeDemo，输出 3 与 true。记录的相等性按字段比较，适合检查这个小型纯树示例。若两个分支共享同一个非空子树，size 会按出现次数重复计数；要统计不同对象数量，需要另一套带身份去重的规格。
普通数学归纳法
要证明对所有 n≥0，性质 P(n) 成立：
- 证明基础情况
P(0)； - 任取
k≥0，假设P(k)成立； - 在该假设下证明
P(k+1)。
例：
1+2+...+n = n(n+1)/2，n≥1基础 n=1：
1 = 1·2/2归纳步骤，假设：
1+...+k = k(k+1)/2则：
1+...+k+(k+1)
= k(k+1)/2 + (k+1)
= (k+1)(k+2)/2这正是 n=k+1 的公式。
归纳假设不是“假设结论已经对所有数成立”，而只是在证明当前步骤时暂时使用前一个规模的性质。
为什么基础情况不可省
考虑命题 P(n): n≥5。对所有 k≥0：
若 k≥5，则 k+1≥5归纳步骤成立，但 P(0) 不成立，所以不能推出所有非负整数都大于等于 5。归纳步骤只传递真值，基础情况才启动这条链。
若性质从 n₀ 开始，基础情况应是 P(n₀)，归纳步骤覆盖所有 k≥n₀。
强归纳法
强归纳在证明 P(k+1) 时可假设：
P(n₀), P(n₀+1), ..., P(k)它与普通归纳在逻辑证明能力上等价，但处理依赖多个更小规模的问题时更自然。
定理：每个大于 1 的整数都能写成质数乘积。
基础 n=2 成立，因为 2 是质数。对 n≥3，假设所有 2≤m<n 都已满足性质，再分两类：
- 若
n是质数，它本身就是质数乘积； - 若
n合数，则n=ab，其中1<a,b<n； - 由强归纳假设，
a、b都可写成质数乘积，所以n也可以。
当前 n 同时依赖两个不确定的更小整数，强归纳让所需假设直接可用。
结构归纳
对于递归定义的数据，证明应覆盖每个构造器。
定理：对任意有限二叉树 t：
mirror(mirror(t)) = t证明：
Empty：镜像两次仍为Empty；Node(v,l,r)：假设性质对l和r成立。第一次镜像交换并递归镜像左右子树，第二次再交换并镜像。由归纳假设，左右子树恢复，所以整棵树恢复。
结构归纳的假设跟随递归子结构，不必人为给树编号。编译器 AST、类型表达式和语法推导都常用这种证明。
递归程序的终止性
每个递归调用都应沿某个良基度量严格下降：
int gcd(int a, int b) {
if (a < 0 || b < 0) throw new IllegalArgumentException("nonnegative inputs required");
if (b == 0) return a;
return gcd(b, a % b);
}这个 Java 方法限定 a,b≥0，并约定 gcd(0,0)=0；负数由入口检查拒绝。若 b>0，Java 余数满足 0≤a%b<b，因此第二个参数严格下降。共同约数集合在 (a,b)→(b,a%b) 下保持，直到 b=0 时返回 a。下降证明负责终止，约数不变性负责结果正确。
对树可以用节点数，对列表用长度，对复杂状态可用二元组的词典序。若递归遍历图，沿边走并不保证结构变小，还需要记录已访问节点。
这是算法模型下的终止证明，不保证任意递归深度都能放进有限调用栈。Python 的 recursion limit 就是一个可见的运行时边界。
递归定义和递归执行的边界
- 递归定义可以由迭代或其他算法计算；
- 迭代也可以通过递归状态转换表达；
- 两种实现是否安全取决于语言调用栈、尾调用保证和输入规模；
- Java、Python 不保证把一般尾递归优化成常量栈，深递归可能耗尽调用栈；
- 把递归改成显式栈改变资源位置，不自动降低时间复杂度。
完成检查
- 给阶乘、列表长度和表达式求值写出递归定义；
- 用普通归纳证明前
n个奇数之和为n²； - 用强归纳证明金额大于等于某界限时能由两种硬币组合（先验证命题和基础范围）；
- 用结构归纳证明
size(mirror(t))=size(t)； - 为 Euclid 算法或树遍历写出明确的终止度量。