7.1 递归定义与结构归纳法

第 6 章通过描述一个完整结果如何构造来计数。不过，有些集合的构造阶段并不固定：二进制串可以具有任意有限长度，算术表达式里还可以嵌套更小的表达式。

要精确描述这样的集合，我们需要允许规则重复使用已经构造出的对象。这就是递归的基本思想。

递归定义在做什么

递归定义用同一类中规模更小的对象来描述新对象。一个完整的递归定义包含三部分：

1. 基础规则：给出一个或多个起始对象。

2. 构造规则：说明怎样用已经接纳的对象构造新对象。

3. 封闭规则：说明只有经过有限次基础规则和构造规则得到的对象才属于该集合。

“规模更小”非常重要。每个对象都必须拥有一段有限的构造历史，并最终回到基础对象；否则定义可能永远绕着自己打转，却没有真正生成任何东西。

第一个例子：递归生成字符串集合

设 $S$ 是由符号 $0$ 和 $1$ 组成的字符串集合。定义如下：

• 基础：空串 $\varepsilon$ 属于 $S$。
• 构造：若 $w\in S$，则 $w01\in S$。
• 封闭：除此以外，没有别的字符串属于 $S$。

符号 $\varepsilon$ 表示不含任何符号的字符串，因此其长度是 $0$。符号 $w$ 是一个占位符，代表任意一个已经确认属于 $S$ 的字符串。

从基础对象出发，规则依次生成

每次构造都在末尾添加一个 $01$ 块，因此也可以把这个集合写成

其中 $(01)^n$ 表示连续出现 $n$ 次的 $01$，而 $\mathbb N=\{0,1,2,\ldots\}$。

字符串 $0101$ 属于 $S$，因为它有一份有限的构造证明：

字符串 $0110$ 不属于 $S$。唯一的构造规则只能在末尾添加 $01$，所以任何合法构造都不可能以 $10$ 结尾。

判断成员资格就是寻找构造过程

对一个直接列举的普通集合，判断成员资格就是在列表中查找。对递归定义的集合，我们要回答的是：

> 能否从某个基础对象出发，经过有限次合法构造得到目标对象？

记录下来的合法步骤序列叫作推导。推导有两项作用：

• 它证明对象确实属于集合；
• 它揭示目标对象由哪些更小的对象构成。

以后进行结构归纳证明时，这些更小的对象会提供归纳假设。

数值函数也可以递归定义

递归不仅能定义集合，也能定义数值。第 6 章使用过的阶乘可以定义为

以及对每个整数 $n\ge1$，

第一条等式给出基础值，第二条把输入从 $n$ 缩小为 $n-1$。不断代入后，计算必须最终到达 $0!$。

例如，

这个计算也说明基础值并非可有可无。若没有 $0!=1$，缩减过程就永远得不到一个确定的数值答案。

良基缩减排除循环定义

考虑下面这个失败的定义：

它虽然再次提到了 $f$，但既没有缩小输入，也没有给出基础值。等式两边减去 $f(n)$ 甚至会得到 $0=1$，所以它不能定义函数。

有效的递归定义需要一个规模度量，沿依赖关系向后追溯时，这个度量必须严格减小。例如：

• 字符串的长度；
• 表达式中运算符的数量；
• 整数输入 $n$；
• 有限结构中的结点数。

非负整数不可能无限下降，因此反向追溯最终一定会到达基础情况。

进入递归语言工坊：选择基础字符块和构造规则，沿完整推导历史生成合法字符串，再把伪装的非法字符串交给成员扫描器。工坊会精确标出非法对象在哪一步失去了构造证书。

从构造规则走向证明方法

第 3 章介绍了普通数学归纳法。要证明每个整数 $n\ge n_0$ 都满足命题 $P(n)$，我们先证明基础情况，再证明从 $P(k)$ 可以推出 $P(k+1)$。

递归结构未必排成一条简单的链。一个表达式可能由两个更小的表达式构成，一棵树也可能包含多个子树。因此，我们要沿结构自身的构造规则进行证明，而不只是沿着整数前进。

这种方法叫作结构归纳法。

设递归集合 $R$ 具有若干基础对象和构造规则。要证明每个 $x\in R$ 都具有性质 $P(x)$，需要：

1. 对每个基础对象证明 $P(x)$； 2. 对每条构造规则，假设参与构造的所有较小对象都满足 $P$； 3. 利用这些假设证明新构造的对象也满足 $P$。

第 2 步中的假设叫作结构归纳假设。

最后由封闭规则完成论证：$R$ 中每个对象都有有限构造过程，而证明已经覆盖了每一种允许的构造步骤。

例子：递归定义的表达式

定义一个完全加括号的表达式集合 $E$：

• 基础：符号 $x$ 属于 $E$。
• 构造：若 $u\in E$ 且 $v\in E$，则 $(u+v)\in E$。
• 封闭：除此以外，没有别的对象属于 $E$。

例如：

对表达式 $e\in E$，定义：

• $L(e)$ 表示 $x$ 出现的次数；
• $P(e)$ 表示加号的数量。

我们要证明，对每个 $e\in E$ 都有

基础情况

对基础表达式 $e=x$，

所以

构造步骤

假设构造规则把两个更小的表达式 $u$ 和 $v$ 合并为

作出结构归纳假设：

新表达式包含 $u$ 和 $v$ 的全部叶子，所以

它包含两个子表达式内部的加号，还增加了一个最外层加号，所以

代入归纳假设：

因此该性质在构造规则下保持成立。基础情况与构造情况覆盖了 $E$ 中的全部表达式，所以结构归纳法证明了这个恒等式。

检查若干例子为什么还不算证明

我们可以验证几个表达式：

这些检查有助于发现规律，但集合 $E$ 是无限的。结构归纳法之所以能够证明规律，是因为它验证了表达式进入 $E$ 的每一种可能方式。

结构递归与结构归纳相互配合

函数 $L$ 和 $P$ 本身也是沿表达式结构定义的：

以及

按照基础条款和构造条款定义函数的方法叫作结构递归；按照相同条款证明性质的方法就是结构归纳。

三者一一对应：

通过合并已认证的小表达式来生长完整的表达式树。每次合并都会更新叶子数和运算符数，并要求你利用两个子表达式的假设组装对应的结构归纳步骤。实时证书会标出遗漏的基础情况或构造情况。

本节衔接

递归定义也可以生成数列。当下标 $n$ 处的值与前面的值满足某个关系时，这条定义等式叫作递推关系。第 7.2 节将学习怎样生成、建模并求解这样的数列。