递推关系与递归过程

前面两章已经把归纳法、强归纳和递归定义放在一起看过。现在我们把注意力转向另一类很常见的问题：一个对象不是一次写完，而是从初始状态出发，按照同一条规则一步一步生成。

每天账户余额的变化、算法每次调用后剩下的工作量、树的高度和节点数、斐波那契数列、动态规划表格，背后都可以出现递推关系。递推关系的语言很短：给出前面的值，再说明后面的值怎样由它们得到。真正要学会的是三件事：会生成序列，会把递推式展开成结构，会用归纳法验证得到的闭式。

递推关系从初始值和递推规则生成序列的示意图 — 递推关系由初始值和递推规则共同决定，缺少其中任何一部分都不能确定整条序列。

序列和递推定义

序列可以看成按自然数编号的一串对象。最常见的是数列：

a_0,a_1,a_2,a_3,\ldots

有些教材从 $a_1$ 开始编号，有些从 $a_0$ 开始编号。两种都可以，但同一道题里必须保持一致。本章主要使用 $a_0$ 作为起点，因为递归算法和计算机数组常把第一个位置记作 $0$ 。

递推定义通常包括两部分。第一部分是初始条件，例如 $a_0=2$ 。第二部分是递推规则，例如

a_n=2a_{n-1}+1,\quad n\ge 1

这两部分合在一起，才能逐项生成：

a_0=2,\quad a_1=5,\quad a_2=11,\quad a_3=23,\quad a_4=47

递推式中的下标范围不是装饰。写 $a_n=2a_{n-1}+1$ 时，必须说明它从哪个 $n$ 开始成立。若从 $n=1$ 开始，它使用的是已经给出的；若从开始，就会出现，除非题目另外定义了这个对象。

递推式不只是数列

递推关系也可以定义集合、字符串、树或算法运行时间。例如长度为 $n$ 的二进制字符串有多少个，可以记为 $b_n$ 。因为每个长度为 $n-1$ 的字符串后面可以接 $0$ 或 $1$ ，所以

b_n=2b_{n-1},\quad b_0=1

这里的 $b_0=1$ 表示空字符串只有一个。这个例子提醒我们，初始值常常不是“看起来最小的非空对象”，而是让递推规则从一开始就正确运转的基准对象。

用表格生成序列

给定递推式后，最稳妥的第一步常常是列出前几项。列项不是证明，但它能帮助我们检查定义是否理解正确，也能给闭式猜想提供线索。

例如递推式

a_0=3,\quad a_n=2a_{n-1}-1

生成的前几项是

3,5,9,17,33,\ldots

每一步都只看前一项，所以它是一阶递推。这个“一阶”不是说公式简单，而是说新项只依赖前一项。

前几项相同并不保证两条递推定义完全相同。递推关系要由初始条件、递推规则和适用范围共同决定。只比较前三四项，很容易把不同序列误认成同一个序列。

迭代展开

生成前几项之后，下一步常常是把递推式往回代入。这个动作叫迭代展开。它的目的不是机械地把式子写长，而是看清反复出现的结构。

考虑

a_0=1,\quad a_n=3a_{n-1}+2

先展开一次：

a_n=3a_{n-1}+2

再把 $a_{n-1}$ 替换成 $3a_{n-2}+2$ ：

a_n=3(3a_{n-2}+2)+2=3^2a_{n-2}+2(3+1)

再展开一次：

a_n=3^3a_{n-3}+2(3^2+3+1)

照这个模式继续到 $a_0$ ，得到

a_n=3^n a_0+2(1+3+3^2+\cdots+3^{n-1})

因为 $a_0=1$ ，所以

a_n=3^n+2(1+3+3^2+\cdots+3^{n-1})

等比和公式给出

1+3+3^2+\cdots+3^{n-1}=\frac{3^n-1}{2}

于是

a_n=2\cdot 3^n-1

递推关系逐层迭代展开到闭式线索的示意图 — 迭代展开把“上一项”不断替换下去，直到初始值出现，闭式的结构也随之浮出来。

例题：展开一个递推式

设 $a_0=4$ ，且对 $n\ge 1$ 有

a_n=5a_{n-1}-8

写出 $a_n$ 的展开形式。

先展开前两层，观察系数如何累积：

a_n=5a_{n-1}-8=5(5a_{n-2}-8)-8

迭代展开常常比直接猜闭式更可靠，因为它保留了每一步替换的来源。以后遇到更复杂的递推式时，也可以先展开几层，不急着套公式。

一阶线性递推

一阶线性递推最常见的形状是

a_n=ra_{n-1}+b

其中 $r$ 和 $b$ 是常数。它可以描述“旧量按比例保留，再加上固定新量”的过程。账户每期按利率增长后再存入固定金额，库存每期保留一部分后再补货，算法规模每步按比例缩小后增加固定开销，都能写出这种结构。

一阶线性递推公式的结构图 — 一阶线性递推把旧量乘以 $r$ ，再在每一步加入 $b$ 。

通过迭代展开，可以得到统一形式：

a_n=r^n a_0+b(1+r+r^2+\cdots+r^{n-1})

当 $r\neq 1$ 时，等比和给出

a_n=r^n a_0+b\frac{r^n-1}{r-1}

当 $r=1$ 时，递推式变成

a_n=a_{n-1}+b

所以

a_n=a_0+nb

一阶线性递推有两个常用视角。迭代展开适合找闭式；固定点视角适合理解长期趋势。若 $a_n=ra_{n-1}+b$ 有固定值 $L$ ，满足 $L = r L +$ ，那么。这说明序列与固定值的距离每步乘以。

递推计算和闭式计算的对照

递推式擅长说明“下一步怎么来”，闭式擅长直接计算“第 $n$ 项是多少”。下面的工具把两种计算放在同一张表里，适合用来检查展开是否正确。

注意闭式不是比递推式“更真实”的定义。很多问题天然就是按步发生的，递推式反而更贴近问题本身。闭式的好处是计算和比较更方便；递推式的好处是建模和证明更直接。

二阶递推的直觉

如果下一项需要前两项一起决定，就得到二阶递推。典型形式是

a_n=p a_{n-1}+q a_{n-2}

这时只给一个初始值不够。因为要算 $a_2$ ，需要知道 $a_1$ 和 $a_0$ ；要算 $a_3$ ，需要知道和。所以二阶递推通常要给两个初始条件。

二阶递推由前两项共同决定下一项的示意图 — 二阶递推带有“两项记忆”：下一项由前两项共同决定。

斐波那契数列是最常见的二阶递推：

F_0=0,\quad F_1=1,\quad F_n=F_{n-1}+F_{n-2}\quad(n\ge 2)

前几项是

0,1,1,2,3,5,8,13,21,\ldots

它的规则很朴素，却已经展示了二阶递推的关键特征：当前位置不是只看上一项，而是同时保留两个相邻状态。

为什么二阶递推需要更多初始信息

设

a_n=2a_{n-1}+a_{n-2}

如果只知道 $a_0=1$ ，仍然无法确定 $a_1$ 。不同的 $a_1$ 会生成不同序列：

1,0,1,2,5,\ldots

和

1,3,7,17,41,\ldots

都满足同一条递推规则，却不是同一条序列。这说明递推规则本身不是完整定义，初始条件的数量要和依赖的历史长度相匹配。

不要把“递推式的阶数”和“公式里最高次幂”混在一起。 $a_n=2a_{n-1}^3+1$ 仍然是一阶递推，因为它只依赖 $a_{n-1}$ ；是二阶递推，因为它依赖前两项。

递归过程和递推式

递推式描述值之间的关系；递归过程描述计算时如何调用自己。二者经常写成相似的形式，但含义不同。

例如斐波那契数列的递推定义是数学对象：

F_n=F_{n-1}+F_{n-2}

如果把它直接翻译成递归计算，就会出现这样的过程：要算 $F(5)$ ，先算 $F(4)$ 和 $F(3)$ ；要算 $F(4)$ ，又要算 $F(3)$ 和。同一个、会被多次计算。

斐波那契递归树与自底向上表格保存的对照图 — 递归树揭示重复子问题；表格法把已经算过的值保存起来。

数学定义不等于高效程序

递归定义很适合表达对象本身。它短、清楚、贴近结构。但计算同一个对象时，可以有不同过程：

直接递归：照定义向下拆分，容易重复计算。
记忆化递归：仍然按递归结构写，但把已经算过的结果保存下来。
自底向上表格：从初始值开始，按下标逐项填表。

这三种过程可以计算同一条数列，但运行时间差别很大。离散数学关心的不只是“值是什么”，也关心“过程为什么正确”和“过程会花多少步”。

看到递归定义时，不要立刻把它等同于低效程序。低效的往往不是递归思想本身，而是不保存重复子问题的直接计算方式。递推关系、递归过程和具体实现要分开判断。

用递推式描述递归算法的工作量

递归算法的运行时间也常用递推式描述。若某个算法处理规模为 $n$ 的问题时，会递归处理一个规模为 $n-1$ 的子问题，并额外做 $n$ 步工作，那么可以写成

T(n)=T(n-1)+n

若它把问题拆成两个规模为 $n/2$ 的子问题，并额外做 $n$ 步合并工作，就可能写成

T(n)=2T(n/2)+n

本章不展开算法复杂度的完整理论，只要先抓住一点：递推式可以描述数列本身，也可以描述一个递归过程的成本。

从递推式到闭式

闭式是不用前面各项就能直接表示 $a_n$ 的公式。例如

a_n=4+3n

就是闭式；而

a_n=a_{n-1}+3,\quad a_0=4

是递推定义。它们描述的是同一条序列：

4,7,10,13,16,\ldots

从递推式到闭式，常见路线有三步：先算前几项，观察差、比或重复结构；再迭代展开；最后用归纳证明闭式确实满足原递推定义。

由递推式猜测闭式并用归纳验证的流程图 — 闭式可以从观察和展开中猜出，但必须回到初始值和递推式中验证。

猜测闭式时看什么

不同递推式会留下不同痕迹：

每步加同一个数，常出现等差形式。
每步乘同一个数，常出现等比形式。
每步“乘旧量再加常数”，常出现等比和。
下一项依赖前两项，常需要保留两项状态。
递归算法反复拆分问题，常可以画递归树或写工作量递推式。

这些只是线索，不是证明。线索帮我们提出候选公式，证明要检查候选公式是否真的覆盖所有 $n$ 。

用归纳验证闭式

要证明一个闭式和递推定义一致，最常用的方法是数学归纳法。证明时需要检查两件事：闭式是否给出正确初始值；如果前一项符合闭式，代入递推式后下一项是否也符合闭式。

例题：验证一阶递推的闭式

设

a_0=2,\quad a_n=2a_{n-1}+1

证明

a_n=3\cdot2^n-1

先检查初始值。当 $n=0$ 时，闭式右边为

3\cdot2^0-1=2

这与一致。

这个证明的关键是：归纳步骤必须使用原来的递推式。如果只把闭式自己变形一遍，没有说明它和递推定义如何连接。

验证闭式时，只要闭式满足同一组初始条件和同一条递推规则，就确定了同一条序列。递推定义的“唯一生成”性质，正是归纳法在背后起作用。

建立递推模型的检查清单

先定义 $a_n$ 表示什么。不要只写公式，要说明下标 $n$ 代表时间、规模、长度、步数还是对象数量。

写出足够的初始条件。一阶递推通常需要一个初始值，二阶递推通常需要两个初始值，分段递推可能需要更多说明。

章末练习

设 $a_0=3$ ， $a_n=2a_{n-1}-1$ 。写出前五项，并猜测闭式。

前五项是 $3,5,9,17,33$ 。观察 $a_n-1$ ：它们是 $2,4,8,16,32$ ，所以可以猜测。这个闭式可以用归纳法验证。

设 $b_0=5$ ， $b_n=b_{n-1}+4$ 。写出的闭式。

每一步增加 $4$ ，从 $5$ 开始，所以 $b_n=5+4n$ 。也可以展开为 $b_n=b_0+4+4+\cdots+4$ ，共有个。

设 $c_0=1$ ， $c_n=3c_{n-1}+2$ 。证明。

当 $n=0$ 时， $2\cdot3^0-1=1$ ，与 $c_0$ 一致。假设，则。由归纳法，闭式成立。

为什么递推式 $d_n=d_{n-1}+d_{n-2}$ 不能只给就确定整条序列？

因为要计算 $d_2$ ，需要同时知道 $d_1$ 和 $d_0$ 。只给 $d_0$ 时，仍然可以取不同值，而不同的会生成不同序列。二阶递推通常需要两个初始条件。

直接递归计算斐波那契数 $F(5)$ 时，为什么会出现重复计算？

因为 $F(5)$ 会调用 $F(4)$ 和 $F(3)$ ，而 $F(4)$ 又会调用 $F(3)$ 和。这样已经出现两次，还会在多个分支中继续出现。若使用表格保存每个，每个子问题只需要计算一次。

本章的重点不是记住某个万能公式，而是把“按步生成”的对象说清楚。递推关系给出局部规则，递归过程展示计算结构，闭式帮助直接计算，而归纳法负责把猜出的公式重新固定在递推定义上。

b

L=rL+b

F(2)

a_0=2

d_{0}

d_0

F(2)

离散数学与证明 I：逻辑、集合、归纳、计数与图论入门｜第 11 章：递推关系与递归过程 | 自在学