递推关系与递归过程

上一章用递归定义描述了对象怎样从基础情形一步步长出来。这一章把同一个想法往前推一步：如果我们关心的是“第 $n$ 个对象的值是多少”“处理规模 $n$ 的问题要做多少工作”，就要把生成规则写成递推关系。

递推关系把一个大下标的值交给较小下标的值。它只说局部规则，却能确定整条序列。递归过程也会把大问题交给较小的问题，但它描述的是计算时发生了哪些调用。两者长得很像，回答的问题却不同：一个描述值，一个描述过程。

本章会从“递推式为什么必须配初值”开始，练习展开、猜测和归纳验证，再处理一阶与二阶线性递推。最后把递推关系放回递归算法，借调用树看清重复计算和增长速度。到章末，递推式还会自然地变成下一章计数问题的建模工具。

---

一条递推定义怎样站稳

先看一个很短的定义：

$$a_0=2,\qquad a_n=2a_{n-1}+1\quad(n\ge 1)$$

从 $a_0$ 出发，后面的值没有选择余地：

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

这里有三个缺一不可的部分。

• $a_n$ 表示什么，或者至少说明它是一条以 $n$ 为下标的序列。
• 初始条件告诉我们从哪里开始，例如 $a_0=2$。
• 递推规则和适用范围告诉我们怎样继续，例如规则从 $n=1$ 开始。

很多初学者只盯着中间那条公式，觉得 $a_n=2a_{n-1}+1$ 已经定义完了。其实没有初值时，$a_0$ 可以任取；每一个不同的 都会产生一条不同序列。递推式给的是“走法”，初值给的是“起点”。

阶数决定需要多少初值

递推式的阶数看的是它要回看多远。

$$a_n=3a_{n-1}-2$$

只回看一项，是一阶递推，通常给一个初值就够。

$$b_n=b_{n-1}+b_{n-2}$$

要回看两项，是二阶递推，通常要给两个相邻初值。若只知道 $b_0$，连 $b_2$ 都算不出来，因为 $b_1$ 还没有确定。

“阶”与幂次没有关系。$c_n=(c_{n-1})^3+1$ 仍是一阶递推；它虽然有三次方，却只依赖前一项。

基础情形为什么有时不符合第一眼直觉

定义长度为 $n$ 的二进制字符串数目为 $s_n$。每个长度为 $n-1$ 的字符串末尾都能接 $0$ 或 $1$，所以

$$s_n=2s_{n-1}\quad(n\ge 1)$$

这时最合适的初值不是 $s_1=2$，而是

$$s_0=1$$

长度为 $0$ 的字符串没有字符，但“空字符串”本身是一种字符串。有了这个初值，递推式从第一步就能工作，并给出 $s_n=2^n$。离散数学里常把空对象算作一个合法结构，因为它让递归定义在边界处保持一致。下一章数空选择、空排列时还会再次遇到这种做法。

不合格的递归定义会发生什么

考虑

$$f(n)=2+f(n-1)$$

它没有基础情形，因此不能唯一确定 $f$。若一条函数满足它，把所有函数值同时加上 $10$，仍然满足它。

再看

$$g(0)=0,\qquad g(n)=g(n+1)\quad(n\ge 1)$$

它虽然写了基础情形，但递归调用朝着更大的下标走。为了求 $g(1)$，要先求 $g(2)$；为了求 $g(2)$，又要先求 $g(3)$。过程永远到不了 $g(0)$。一个适合计算的递归规则，必须沿着某种严格变小的度量靠近基础情形。

先亲手生成几项

下面的工具处理一阶递推 $a_n=ra_{n-1}+b$。调整初值、倍数和常数项，观察同一条局部规则怎样生成整条序列。

列出前几项不是证明，却是很好的体检。下标错一位、初值抄错、加号写成减号，通常会立刻暴露出来。它还能给闭式提供线索，但有限个已知项永远不能单独证明后面所有项的规律。

---

从递推式往回展开

现在考虑

$$a_0=1,\qquad a_n=3a_{n-1}+2\quad(n\ge 1)$$

我们已经知道怎样向前算 $a_1,a_2,a_3$。为了直接得到第 $n$ 项，方向要反过来：从 $a_n$ 开始，把旧项一次次替换掉。

$$\begin{aligned} a_n &=3a_{n-1}+2\\ &=3(3a_{n-2}+2)+2\\ &=3^2a_{n-2}+2(3+1)\\ &=3^3a_{n-3}+2(3^2+3+1) \end{aligned}$$

先别急着把数字全算完。保留 $3^2,3^3$ 和括号里的和，模式反而更清楚。展开 $k$ 层后，应该是

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

当 $k=n$ 时，下标恰好降到 $0$：

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

利用等比和并代入 $a_0=1$，得到

$$a_n=3^n+2\frac{3^n-1}{3-1}=2\cdot3^n-1$$

这就是从递推定义得到的闭式。闭式不再引用前面的项，可以直接计算第 $n$ 项，也更容易看出序列按指数速度增长。

展开法其实藏着一次归纳

上面写出“展开 $k$ 层后的形式”时，我们已经做了一个猜测。这个猜测不能只靠省略号撑住，最好验证一次：若

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

那么再展开一层，$a_{n-k}=3a_{n-k-1}+2$，于是

$$\begin{aligned} a_n &=3^k(3a_{n-k-1}+2)+2(1+3+\cdots+3^{k-1})\\ &=3^{k+1}a_{n-(k+1)}+2(1+3+\cdots+3^k) \end{aligned}$$

形式完全相同，只是 $k$ 换成了 $k+1$。原递推式给出 $k=1$ 的起点，这次代入给出归纳步骤。所以“反复展开直到看见模式”不是随意跳步；把模式写清楚后，它本身就能用归纳法站稳。

一个可复用的展开流程

设

$$x_0=4,\qquad x_n=5x_{n-1}-8\quad(n\ge1)$$

我们完整走一次。

---

猜到闭式以后怎样证明

观察与展开负责找到候选公式，归纳法负责确认它对所有下标成立。两者分工不同。只写“前五项符合，所以公式成立”不是证明；只写一段归纳推导却不解释公式从哪来，也会让读者不知道该怎样独立解题。

对递推定义验证闭式，一般检查两件事：

1. 候选闭式给出的初始值是否正确。
2. 假设较早项符合闭式，代入原递推式后，新项是否也符合闭式。

例题：验证一个一阶闭式

已知

$$a_0=2,\qquad a_n=2a_{n-1}+1\quad(n\ge1)$$

由前几项和展开可以猜出

$$a_n=3\cdot2^n-1$$

现在证明它。

这个证明有一个很实用的阅读方法：盯住等号链的第一行。它必须来自原递推式。若证明直接从 $3\cdot2^{k+1}-1$ 开始变形，最后变回自己，却没有碰到 $a_{k+1}=2a_k+1$，那就没有证明候选公式与这条递推定义相连。

二阶闭式要验证两个基础情形

若递推式依赖前两项，归纳步骤会同时使用两个较早下标。对应地，闭式验证通常要先检查两个基础情形，再用强归纳，或使用“同时假设 $P(k)$ 与 $P(k-1)$”的二阶归纳写法。

---

一阶线性递推：旧量乘一下再加一点

最常见的一阶线性递推是

$$a_n=ra_{n-1}+b\quad(n\ge1)$$

它描述的过程很直白：旧量先乘以 $r$，每一步再加入固定量 $b$。账户每期增长后固定存款、库存保留一部分后补货、误差每轮缩放后加入固定偏差，都可能出现这种形式。

连续展开会得到

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

当 $r\ne1$ 时，等比和给出

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

当 $r=1$ 时，原递推式变成每次加 $b$，所以

$$a_n=a_0+nb$$

这个分情况不能省。把 $r=1$ 直接代入含有 $r-1$ 的分母，会得到没有意义的 $0/0$。

固定点视角：为什么有些序列会稳定下来

设存在一个值 $L$，放进递推式后不会改变：

$$L=rL+b$$

当 $r\ne1$ 时，

$$L=\frac{b}{1-r}$$

把递推式两边都减去 $L$：

$$a_n-L=r(a_{n-1}-L)$$

这句话比原式更能说明长期行为：序列与固定点的距离，每一步都乘以 $r$。继续迭代便得到

$$a_n-L=r^n(a_0-L)$$

• 若 $|r|\lt1$，距离越来越小，序列趋近 $L$。
• 若 $|r|\gt1$，除非一开始正好在 $L$，距离通常越来越大。
• 若 $r\lt0$，距离的正负会交替，序列可能在固定点两侧来回摆动。

所以闭式不只是为了算第 $n$ 项。它把“反复做同一件事”压缩成一个幂，让长期趋势直接显出来。

用交互对照递推计算与闭式计算

调整参数后，下面的工具会同时用逐项递推和闭式计算。两列结果应该一致。尤其可以试试 $r=1$、$r=0$ 和负数 $r$，看看为什么公式要分情况。

用变量平移处理常数项

对于

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

固定点满足 $L=3L+2$，所以 $L=-1$。令

$$u_n=a_n-(-1)=a_n+1$$

则

$$u_n=3u_{n-1}$$

常数项消失了，问题变成等比递推。若 $a_0=1$，则 $u_0=2$，所以

$$u_n=2\cdot3^n,\qquad a_n=2\cdot3^n-1$$

展开法是在追踪每一步加入的常数；平移法是在寻找一个不会移动的中心。两种方法得到同一个闭式，却展示了不同的结构。

---

二阶常系数递推：为什么会出现特征根

二阶齐次常系数递推的一般形式是

$$a_n=pa_{n-1}+qa_{n-2}\quad(n\ge2),\qquad q\ne0$$

“二阶”表示要记住前两项，所以最高滞后项 $a_{n-2}$ 的系数 $q$ 必须非零；若 $q=0$，它实际退化成一阶递推。“常系数”表示 $p,q$ 不随 $n$ 改变；“齐次”表示右边没有额外加上的、只依赖 的项。

直接展开二阶递推，分支会越来越多。更整齐的想法是先问：有没有一种序列，向后移动一位时只差一个固定倍数？指数序列 $a_n=\lambda^n$ 正好有这种性质。

把它代入递推式：

$$\lambda^n=p\lambda^{n-1}+q\lambda^{n-2}$$

除以 $\lambda^{n-2}$，得到

$$\lambda^2-p\lambda-q=0$$

这叫特征方程。它把“下标移动”的问题变成了一个代数方程。

两个不同特征根

若特征方程有两个不同根 $\lambda_1,\lambda_2$，那么

$$a_n=A\lambda_1^n+B\lambda_2^n$$

会满足递推式。两个初始条件用来确定 $A,B$。

看一个算得干净的例子：

$$a_0=2,\qquad a_1=3,\qquad a_n=3a_{n-1}-2a_{n-2}\quad(n\ge2)$$

特征方程为

$$\lambda^2-3\lambda+2=0$$

两个根是 $1$ 和 $2$，所以先写

$$a_n=A+B2^n$$

再代入两个初值：

$$A+B=2,\qquad A+2B=3$$

解得 $A=B=1$，于是

$$a_n=1+2^n$$

它生成 $2,3,5,9,17,\ldots$，与递推式吻合。

重根为什么多出一个 $n$

若特征方程只有一个二重根 $\lambda$，只写 $A\lambda^n+B\lambda^n$ 其实仍只有一个自由形状，无法一般地满足两个独立初值。这时第二个基本形状要换成 $n\lambda^n$：

$$a_n=(A+Bn)\lambda^n$$

在本课程里，先理解“二阶需要两种独立形状”就够了。以后处理更高阶递推时，同样会看到：不同根贡献不同指数项；根若重复，就会额外乘上 $n,n^2$ 等因子。

斐波那契递推揭示了什么

斐波那契数列定义为

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

它的特征方程是

$$\lambda^2-\lambda-1=0$$

两个根为

$$\lambda_1=\frac{1+\sqrt5}{2},\qquad \lambda_2=\frac{1-\sqrt5}{2}$$

因此 $F_n$ 可以写成这两个指数项的线性组合。第二个根的绝对值小于 $1$，它的幂会逐渐变小；第一个根大于 $1$，长期增长主要由它决定。这解释了为什么斐波那契数虽然由“相加”产生，规模却按指数增长。

---

递推关系和递归过程不是一回事

斐波那契递推式定义的是一列数：

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

它没有规定计算机必须怎样求 $F_n$。我们至少有三种过程可以计算同样的值。

直接递归

最直译的过程是：求 $F(n)$ 时，分别求 $F(n-1)$ 和 $F(n-2)$，到 $n=0$ 或 $$ 停止。

求 $F(5)$ 会先产生 $F(4)$ 与 $F(3)$。而 $F(4)$ 内部又需要一个 $F(3)$。同一个子问题出现多次，后面还会继续重复。数学定义没有错，浪费来自“每次遇见都从头再算”的执行方式。

下面的调用树可以切换 $n$。圆点表示一次实际调用；同样的 $F(k)$ 出现多次时会被标出。再和右侧的表格项数量比较。

记忆化递归

记忆化仍从 $F(n)$ 向下递归，但第一次算出 $F(k)$ 后就把结果保存起来。以后再遇到同一个 $k$，直接读取，不再展开子树。

对于 $F(n)$，真正不同的子问题只有

$$F(0),F(1),\ldots,F(n)$$

共 $n+1$ 个。调用关系仍然是递归的，但每个状态最多完成一次实际计算。

自底向上

也可以完全不展开调用树。从 $F_0,F_1$ 开始，依次填出 $F_2,F_3,\ldots,F_n$。如果只需要最终的 ，连整张表都不必保留，只存最近两项即可。

调用树的节点数也是一条递推

设直接递归计算 $F(n)$ 时，函数总调用次数为 $C_n$。基础调用 $F(0),F(1)$ 各只产生一个节点，所以

$$C_0=C_1=1$$

当 $n\ge2$ 时，根调用本身算一次，下面有两棵子树：

$$C_n=C_{n-1}+C_{n-2}+1$$

这条递推和斐波那契递推几乎一样，因此 $C_n$ 也按指数规模增长。事实上可以验证

$$C_n=2F_{n+1}-1$$

而记忆化或自底向上只处理 $n+1$ 个不同下标；在把一次加法和一次表项读写计作常数成本的单位成本模型下，工作量随 $n$ 线性增长。这里第一次看见了一个很重要的区别：同一条数值递推，可以对应完全不同的计算复杂度。

---

用递推式分析递归过程的工作量

若算法处理规模 $n$ 的问题时，先处理一个规模 $n-1$ 的子问题，再做 $n$ 次额外操作，工作量可以写成

$$T(n)=T(n-1)+n\quad(n\ge1),\qquad T(0)=c$$

其中 $c$ 是与输入规模无关的固定基础成本。

展开得到

$$T(n)=T(0)+1+2+\cdots+n$$

而

$$1+2+\cdots+n=\frac{n(n+1)}{2}$$

所以工作量按 $n^2$ 的量级增长。这里闭式的价值不只是少写一个求和号，它让增长速度一眼可见。

汉诺塔：递归结构怎样变成精确递推

有三根柱子和 $n$ 个大小不同的圆盘。开始时圆盘都叠在第一根柱子上，大盘在下、小盘在上。每次只能移动最上面的一个圆盘，而且大盘不能放在小盘上。设把整塔移到目标柱所需的最少步数为 $H_n$。

为了移动最大的圆盘，必须先把上面的 $n-1$ 个圆盘移到辅助柱；然后移动最大圆盘一次；最后再把 $n-1$ 个圆盘移到目标柱。因此有一个可行过程：

$$H_n\le H_{n-1}+1+H_{n-1}$$

另一方面，任何合法过程在移动最大圆盘前，都必须挪开全部 $n-1$ 个小圆盘；移动后，又必须把它们叠回最大盘上。这两段各自至少要 $H_{n-1}$ 步。因此下界也是同一个数：

$$H_n\ge2H_{n-1}+1$$

上下界相遇，得到精确递推：

$$H_0=0,\qquad H_n=2H_{n-1}+1\quad(n\ge1)$$

展开：

$$H_n=2^nH_0+(1+2+\cdots+2^{n-1})=2^n-1$$

这段推理比单纯算出公式更重要。写算法只给了“至多需要多少步”；再证明任何算法都不可能更少，才得到“最少步数”的等号。

分成两个一半：为什么会出现 $n\log n$

设一个过程把规模 $n$ 的问题分成两个规模 $n/2$ 的子问题，再用 $n$ 步合并结果：

$$T(n)=2T(n/2)+n\quad(n\ge2),\qquad T(1)=c$$

其中 $n$ 取 $2$ 的幂，$c$ 是固定的基础成本。

调用树第 $0$ 层有一个规模 $n$ 的问题，额外工作为 $n$。第 $1$ 层有两个规模 $n/2$ 的问题，额外工作总计仍是

$$2\cdot\frac n2=n$$

第 $2$ 层有四个规模 $n/4$ 的问题，总计仍为 $n$。问题规模从 $n$ 连续除以 $2$，经过 $\log_2 n$ 层降到 。每层约做 的工作，共约 层，所以

$$T(n)=\Theta(n\log n)$$

这里比较的是渐近增长量级：忽略固定倍数和较低阶项后，$3n^2+100n+7$ 与 $n^2$ 同为 $\Theta(n^2)$； 则最终会远快于任何固定次数的多项式。大 只给上界，而 同时给出同阶的上界与下界，所以说“量级相同”时用 更准确。

读递归树时检查四件事

---

递推式也能从计数问题里长出来

下一章要系统学习加法原理、乘法原理、排列与组合。这里先看一个过渡问题：每次可以走 $1$ 级或 $2$ 级台阶，走完 $n$ 级共有多少种走法？

设答案为 $w_n$。不要先列出所有路线，先按最后一步分类。

• 最后走 $1$ 级，那么前面必须已经走完 $n-1$ 级，共有 $w_{n-1}$ 种。
• 最后走 $2$ 级，那么前面必须已经走完 $n-2$ 级，共有 种。

两类互不重叠，所以

$$w_n=w_{n-1}+w_{n-2}\quad(n\ge2)$$

边界也要仔细定。走完 $0$ 级有一种方式：什么都不做。因此

$$w_0=1,\qquad w_1=1$$

于是

$$1,1,2,3,5,8,\ldots$$

又出现了斐波那契型递推。它不是因为台阶长得像兔子，而是因为“最后一步”恰好把所有结果分成两个互斥类别，并分别与更小问题一一对应。

从模型到解答的完整检查

---

章末练习

基础题

1. 已知 $a_0=3$，$a_n=2a_{n-1}-1\ (n\ge1)$。写出前五项，猜测闭式并证明。

查看参考解

前五项是 $3,5,9,17,33$。观察 $a_n-1$ 得到 $2,4,8,16,32$，猜测 。当 时闭式给出 。若 ，则 ，所以闭式对所有 成立。

2. 递推式 $b_n=4b_{n-1}+3\ (n\ge1)$ 没有给初值。它能否唯一确定序列？若补上 $b_0=2$，求闭式。

查看参考解

没有初值时不能唯一确定，因为任取 $b_0$ 都会生成一条满足规则的序列。补上 $b_0=2$ 后，展开得 $b_n=4^n{b}_0+3(1+4+\cdots +4^{n-1})=2\cdot 4^n+(4^n-1)=3\cdot {}^{}$。

3. 设 $c_0=7$，$c_n=0.6c_{n-1}+8\ (n\ge1)$。求固定点，并说明序列长期会怎样。

查看参考解

固定点满足 $L=0.6L+8$，所以 $L=20$。又有 $c_n-20=0.6(c_{n-1}-20)$，因此 。因为 ，这个差趋近 ，所以 趋近 ，并且从低于 的一侧接近。

方法题

4. 已知

$$d_0=1,\qquad d_1=4,\qquad d_n=5d_{n-1}-6d_{n-2}\quad(n\ge2)$$

用特征根法求闭式。

查看参考解

特征方程是 $\lambda^2-5\lambda+6=0$，根为 $2,3$，所以 $d_n=A2^n+B3^n$。由 得 ；由 得 。解得 ，因此 。

5. 汉诺塔递推 $H_0=0$、$H_n=2H_{n-1}+1$ 中，为什么不能只凭递归过程就直接写等号？

查看参考解

递归过程只证明存在一个使用 $2H_{n-1}+1$ 步的方案，因此先得到的是上界。要写“最少步数等于”，还要证明任何方案都必须先挪开 $n-1$ 个小盘、移动最大盘、再把小盘叠回去，因而至少也需要 $2H_{n-1}+1$ 步。

6. 直接递归计算斐波那契数的调用次数满足 $C_0=C_1=1$、$C_n=C_{n-1}+C_{n-2}+1$。计算 ，并解释记忆化为什么能消除大部分调用。

查看参考解

$C_2=3$、$C_3=5$、$C_4=9$、。直接递归的不同分支会反复请求同一个 ；记忆化在第一次完成 后保存结果，后续请求直接读取。真正不同的下标只有 到 ，因此不再保留指数增长的重复子树。

建模题

7. 长度为 $n$ 的二进制字符串中，不允许出现连续两个 $1$。设这样的字符串数为 $s_n$，建立递推关系和初始条件。

查看参考解

按最后一位分类。若最后一位是 $0$，前 $n-1$ 位可以是任意合法字符串，有 $s_{n-1}$ 种；若最后一位是 $1$，倒数第二位必须是 $0$，删去末尾的 $$ 后剩下任意长度 的合法字符串，有 种。因此 。空字符串有一种，故 ；长度 有 两种，故 。

8. 一个过程满足 $T(1)=1$、$T(n)=2T(n/2)+n$，其中 $n$ 是 $2$ 的幂。用递归树说明它的增长量级。

查看参考解

第 $i$ 层有 $2^i$ 个规模 $n/2^i$ 的子问题，该层额外工作总量为 $2^i\cdot(n/2^i)=n$。从规模 降到 共有 次减半，因此共有约 层，每层工作为 ，故 。叶子层有 个常数成本节点，不改变这个量级。

本章把上一章的递归定义变成了可以计算、可以求闭式、也可以分析工作量的语言。看到递推式时，先问起点和依赖是否完整；想求第 $n$ 项时，用展开暴露结构，再用归纳把猜想钉牢；看到递归过程时，则画出调用关系，数清子问题与额外工作。下一章开始计数时，我们会反复用“按最后一步分类”的办法建立递推，同时也会学习不经递推、直接数出答案的基本原则。