递归与递推

这一页教你两件事：一是把”用自己定义自己”的对象和算法写对——为什么基例不是可选项，以及怎样让递归程序不重复劳动；二是把递推关系当方程解——迭代展开、特征方程、主定理三套工具，足以应付本科离散数学和日常算法分析里遇到的绝大多数递推式。学完之后，给你 $a_n=5a_{n-1}-6a_{n-2}$ 这类式子你能写出通项，给你 $T(n)=2T(n/2)+n$ 你能一句话报出复杂度，给你一段”兔子每月生一对”的文字你能立出递推式并求解。

递归定义与良基性

递归定义分两句写：基础情形直接给出最小规模的答案，递归情形把任意规模的定义归约到更小的同类规模。阶乘的标准定义是

$$n!=\{\begin{array}{ll}1,& n=0,\\ n\cdot (n-1)!,& n\ge 1,\end{array}$$

斐波那契数列是 $F_0=0,F_1=1$，$F_n=F_{n-1}+F_{n-2}(n\ge 2)$。两句缺一不可，而且缺的那句各有各的坏法。

只写递归句不写基例，定义根本没有落地的地方：$n!=n\cdot (n-1)!$ 会永远展开成 $n(n-1)(n-2)\cdots$，永远到不了头。在程序里这就是无限递归，直到调用栈溢出。数学上这违反良基性（well-foundedness）：合法递归的每一步，问题的某个”规模度量”必须严格变小，且这个度量不能无限降下去。对以自然数为下标的递推来说，度量就是下标本身——每次递归必须把下标推向基例。判断一个递归定义是否合法的最实用问题：每次调用，哪样东西在严格变小？它有没有下界？

只写基例不写递归句则覆盖不了无穷多个输入，定义不完整。反过来，一个 $k$ 阶递推关系（右边最多依赖前 $k$ 项，如斐波那契是二阶）必须配 $k$ 个初始值才能唯一确定数列：$a_n=2a_{n-1}$ 配上 $a_0=1$ 是 $2^n$，配上 $a_0=7$ 是 $7\cdot 2^n$，递推式本身分不出谁对谁错。做题时”漏写初值”和”漏写基例”是同一类错误的两张脸。

递归算法的代价：调用栈与记忆化

递归程序的执行要理解调用栈：每次函数调用压入一帧（记录局部变量和返回位置），返回时弹出。递归的深度就是栈上同时存在的帧数。汉诺塔的递归深度是 $n$；而朴素斐波那契的递归树深度也是 $n$，但总调用次数是另一回事。

比较斐波那契的两种写法。朴素递归：

F(n): 若 n < 2 返回 n，否则返回 F(n-1) + F(n-2)

设调用次数为 $C(n)$，则 $C(n)=C(n-1)+C(n-2)+1$，立刻看出 $C(n)\ge F_n$。由比内公式（下文推导）$F_n$ 是 ${\phi }^n$ 量级，$\phi =\frac{1+\sqrt{5}}{2}\approx 1.618$，所以朴素递归是指数级 $\Theta ({\phi }^n)$ 的时间——算 $F_{50}$ 要调用约 $2\times 10^{10}$ 次。慢的原因一眼可见：$F(3)$ 这样的小结果被整个子树反复重算，重复劳动随深度爆炸。

记忆化（memoization）的思路是查表代替重算：算过的 $F(k)$ 存进数组，再遇到直接读表。每个 $F(k)$ 只真正计算一次，每次计算只做常数次加法和查表，总时间降到 $\Theta (n)$，空间 $\Theta (n)$。同一个递推式，加一个长度为 $n$ 的表，复杂度从指数降到线性——这是离散数学里最划算的交换之一。再往下走，保存全部历史其实浪费，滚动两个变量即可，见”递归与循环”一节。

线性递推的求解

迭代展开法

迭代展开法是最朴素也最通用的办法：把递推式右边的 $T(n-1)$ 再用递推式代进去，反复代入直到撞上基例，然后识别出求和的规律，最后用归纳法验证。它不需要任何理论，适合结构简单的递推，也是理解其他方法的起点。

例 1（汉诺塔） 把 $n$ 片大小各异的圆盘从一根柱搬到另一根柱，每次一片，大盘不能压小盘。设最少搬动次数为 $T(n)$。搬 $n$ 片必须先把上面 $n-1$ 片挪到辅助柱（$T(n-1)$ 次），把最大片搬过去（$1$ 次），再把 $n-1$ 片搬回最大片上（又是 $T(n-1)$ 次）。少于这个数是不可能的，因为最大片搬动之前 $n-1$ 片必须全部让开。所以

$$T(n)=2T(n-1)+1,T(1)=1.$$

解： 迭代展开：

$$\begin{array}{rl}T(n)& =2T(n-1)+1\\ & =2(2T(n-2)+1)+1=4T(n-2)+2+1\\ & =4(2T(n-3)+1)+3=8T(n-3)+4+2+1\\ & =\cdots \\ & =2^{n-1}T(1)+(2^{n-2}+\cdots +2+1).\end{array}$$

代入 $T(1)=1$，等比数列求和 $2^{n-2}+\cdots +1=2^{n-1}-1$，得

$$T(n)=2^{n-1}+2^{n-1}-1=2^n-1.$$

归纳验证： $n=1$ 时 $2^1-1=1$，成立。设 $T(n-1)=2^{n-1}-1$，则

$$T(n)=2T(n-1)+1=2(2^{n-1}-1)+1=2^n-1.$$

归纳步成立，故 $T(n)=2^n-1$ 对所有 $n\ge 1$ 成立。注意最后这一步不可省：展开法”看出”的规律必须归纳证明，否则只是猜测。$■$

这个答案也解释了汉诺塔作为教学例子的地位：$2^{64}-1$ 秒约等于五千八百亿年，“递归定义的算法可以极快地把规模推向不可行”。

一阶线性递推

一阶线性递推形如

$$a_n=r{a}_{n-1}+c(r\ne 0),$$

即”新值 = 旧值乘一个固定倍数 + 一个固定增量”。贷款、人口、折旧全是这个形状。求解有标准套路：找不动点 $a^{\ast }$，即代入后不再变化的值，$a^{\ast }=r{a}^{\ast }+c$，解得 $a^{\ast }=\frac{c}{1-r}$（$r\ne 1$ 时存在）。两式相减：

$$a_n-a^{\ast }=r(a_{n-1}-a^{\ast }).$$

也就是说数列 $b_n=a_n-a^{\ast }$ 是公比为 $r$ 的等比数列，$b_n=r^n{b}_0$，于是

$$a_n=r^n(a_0-a^{\ast })+a^{\ast }=r^n{a}_0+c\frac{r^n-1}{r-1}.$$

$r=1$ 时没有不动点，退化为等差数列，$a_n=a_0+nc$。可以把结论记成一句话：一阶线性递推 = 等比部分 + 不动点。

例 2（贷款余额） 贷款 $B_0$ 元，月利率 $r$，每月末还款 $p$ 元。写出余额递推式并求还清条件。

解： 上月余额生息后减去月供，$B_n=(1+r)B_{n-1}-p$。这是 $a_n=r^{\prime }{a}_{n-1}+c$ 形状，不动点 $B^{\ast }=p/r$。套用上面的公式：

$$B_n=(1+r{)}^n{B}_0-p\frac{(1+r{)}^n-1}{r}=(1+r{)}^n(B_0-\frac{p}{r})+\frac{p}{r}.$$

当 $p>r{B}_0$ 时 $B_0-\frac{p}{r}<0$，$(1+r{)}^n$ 指数增长也压不住负项，余额最终归零——即月供超过首月利息就能还清，还清月数由 $B_n=0$ 解出 $n=\frac{\ln p-\ln (p-r{B}_0)}{\ln (1+r)}$。当 $p\le r{B}_0$ 时余额不降反升，永远还不清。$■$

二阶常系数递推与特征方程

二阶常系数线性递推形如

$$a_n=c_1{a}_{n-1}+c_2{a}_{n-2}(c_2\ne 0).$$

求解的想法是猜解形为 $a_n=r^n$ 的等比数列，代入得 $r^n=c_1{r}^{n-1}+c_2{r}^{n-2}$，约去 $r^{n-2}$，得到特征方程

$$r^2=c_{1}r+c_2.$$

这是个一元二次方程。两个根 $r_1\ne r_2$ 时，由于递推式对数列是线性的，两个解的任意线性组合仍是解，通项为

$$a_n=A{r}_1^n+B{r}_2^n,$$

$A,B$ 由两个初始值定出（这正是”二阶要配两个初值”的呼应）。把这套机器开到斐波那契上，就得到完整推导。

比内公式推导： $F_n=F_{n-1}+F_{n-2}$ 的特征方程是 $r^2=r+1$，求根公式给出

$$\phi =\frac{1+\sqrt{5}}{2}\approx 1.618,\hat{\phi }=\frac{1-\sqrt{5}}{2}\approx -\mathrm{0.618.}$$

通项 $F_n=A{\phi }^n+B{\hat{\phi }}^n$。用初值定系数：$F_0=0$ 给出 $A+B=0$；$F_1=1$ 给出 $A\phi +B\hat{\phi }=1$。两式联立，$A(\phi -\hat{\phi })=1$，而 $\phi -\hat{\phi }=\sqrt{5}$，所以 $A=\frac{1}{\sqrt{5}}$，$B=-\frac{1}{\sqrt{5}}$。于是

$$F_n=\frac{1}{\sqrt{5}}({\phi }^n-{\hat{\phi }}^n).$$

值得停下来看一眼这个式子：右边是无理数的幂之差，左边却是整数，${\hat{\phi }}^n$ 的绝对值小于 $1$ 且交替变号，恰好把无理部分抵消干净。它还顺带给出 $F_n\sim \frac{{\phi }^n}{\sqrt{5}}$，前面朴素递归指数复杂度里用的就是这个估计。$■$

重根情形一句话带过：特征方程有重根 $r_0$ 时，$r_0^n$ 之外需要补一个 $n{r}_0^n$，通项为 $a_n=(A+Bn)r_0^n$，系数仍由初值定出。直观原因是重根时两个”独立解”塌缩成一个，要乘一个 $n$ 造出第二个。

例 3（用特征方程求通项） 解 $a_n=5a_{n-1}-6a_{n-2}$，$a_0=2$，$a_1=5$。

解： 特征方程 $r^2=5r-6$，即 $(r-2)(r-3)=0$，根 $r_1=2$，$r_2=3$。通项 $a_n=A\cdot 2^n+B\cdot 3^n$。代入初值：

$$A+B=2,2A+3B=5.$$

解得 $A=1$，$B=1$。故 $a_n=2^n+3^n$。检验： $n=2$ 时递推给出 $a_2=5\cdot 5-6\cdot 2=13$，公式给出 $4+9=13$，一致。$■$

分治递推与主定理

分治算法自然产生形如

$$T(n)=aT\left(\frac{n}{b}\right)+f(n),a\ge 1,b>1$$

的递推：把问题切成 $a$ 个规模为 $n/b$ 的子问题，$f(n)$ 是切分和合并的代价。递归树有 ${\log }_{b}n$ 层，第 $j$ 层有 $a^j$ 个子问题、每个代价 $f(n/b^j)$。逐项比大小太繁，主定理（Master Theorem）把判定压成一次比较。记 $n^{{\log }_{b}a}$——它是 $f(n)\equiv 1$ 时递归树叶子数的量级，即”子问题膨胀的速度”，三种情形如下：

1. $f$ 比它小得多：若 $f(n)=O\left(n^{{\log }_{b}a-\epsilon }\right)$ 对某个 $\epsilon >0$ 成立，则 $T(n)=\Theta \left(n^{{\log }_{b}a}\right)$。子问题数量压过每层代价，复杂度由叶子层主导。
2. $f$ 与它同阶：若 $f(n)=\Theta \left(n^{{\log }_{b}a}\right)$，则 $T(n)=\Theta \left(n^{{\log }_{b}a}\log n\right)$。每层代价几乎均摊，${\log }_{b}n$ 层各贡献一次，多出一个对数因子。
3. $f$ 比它大得多且自身规整：若 $f(n)=\Omega \left(n^{{\log }_{b}a+\epsilon }\right)$ 对某个 $\epsilon >0$ 成立，且满足正则条件 $af(n/b)\le cf(n)$ 对某个 $c<1$ 和充分大的 $n$ 成立，则 $T(n)=\Theta (f(n))$。合并代价压过子问题，复杂度由根主导。正则条件排除的是 $f$ 忽大忽小的病态函数，多项式、$n^k{\log }^{m}n$ 这类常见函数都满足。

直觉一句话：比较 $f(n)$ 与 $n^{{\log }_{b}a}$，谁大听谁的，一样大就乘个 $\log n$。前提是这个”大”要差出多项式量级 $n^{\epsilon }$，只差对数因子就不归管。

例 4 用主定理判定下列递推的渐近复杂度。

(a) $T(n)=2T(n/2)+n$（归并排序）。

$n^{{\log }_{2}2}=n$，$f(n)=n=\Theta (n)$，正是情形 2，$T(n)=\Theta (n\log n)$。

(b) $T(n)=4T(n/2)+n$。

$n^{{\log }_{2}4}=n^2$，$f(n)=n=O\left(n^{2-\epsilon }\right)$（取 $\epsilon =1$），情形 1，$T(n)=\Theta (n^2)$。直觉核对：四层分叉的递归树叶子数 $n^2$ 项远压过每层的 $n$，答案合理。

(c) $T(n)=3T(n/4)+n\log n$。

$n^{{\log }_{4}3}\approx n^{0.793}$，$f(n)=n\log n=\Omega \left(n^{0.793+\epsilon }\right)$（取 $\epsilon \approx 0.2$），趋向情形 3。检查正则条件：

$$af(n/b)=3\cdot \frac{n}{4}\log \frac{n}{4}=\frac{3}{4}n(\log n-\log 4)\le \frac{3}{4}n\log n$$

对充分大的 $n$ 成立（$c=3/4<1$）。故 $T(n)=\Theta (n\log n)$，由合并代价主导。$■$

主定理不是万能的，典型反例见”常见错误”一节。

从文字题到递推式

递推建模的关键动作是把文字描述里的”每一期变化”翻译成”新项与旧项的关系”，再单独把初始状态翻译成一个数。三个标准样板：

兔子问题（斐波那契的原始模型，1202 年）。 一对新生兔子两个月后成熟，之后每月生一对；兔子不死。设第 $n$ 个月共有 $F_n$ 对。第 $n$ 月的兔子 = 上月已有的（$F_{n-1}$）+ 新生的。只有两个月前就已存在的兔子本月才成熟生育，新生对数恰为 $F_{n-2}$。于是

$$F_n=F_{n-1}+F_{n-2},F_1=F_2=1.$$

建模的要害在第二句：想清楚”谁有资格变化”，资格由一个固定滞后（两个月）刻画，于是出现二阶项。

增长与贷款模型。 固定比率的增长：$a_n=(1+r)a_{n-1}$（无外部注入时是纯等比）。加入固定月供、移民、 harvesting 等常数项，就是一阶线性递推，解见例 2。

平面分割问题。 $n$ 条直线最多把平面分成多少区域？设最大区域数 $L_n$。第 $n$ 条直线若与前 $n-1$ 条都相交且交点互不相同，就被切成 $n$ 段，每段把一个旧区域劈成两个，于是净增 $n$ 个区域：

$$L_n=L_{n-1}+n,L_0=1.$$

迭代展开并求和：$L_n=1+{\sum }_{k=1}^{n}k=1+\frac{n(n+1)}{2}=\frac{n^2+n+2}{2}$。增量为什么是 $n$ 而不是 $1$，值得对着图想清楚——递推建模的能力几乎都长在”识别增量结构”这一步上。

递归与循环

任何递归都能改写成循环加显式栈：栈代替调用栈保存”待办”。反过来，许多尾部的、线性的递归可以直接改成简单循环，省掉函数调用的开销和栈溢出的风险。以斐波那契为例，记忆化保留了全部历史，其实只需最近两项：

a, b = 0, 1
重复 n 次: a, b = b, a + b
返回 a

尾递归是递归的一种特殊形态：递归调用是函数返回前的最后一个动作，其返回值不再参与额外运算。形如 return F(缩小后的问题)，没有”再加工”。编译器可以把尾递归直接复用当前栈帧，等价于一个循环；但书写上它仍然把终止条件写在分支里，结构清晰。不是所有递归都能尾递归化——汉诺塔、斐波那契都不天然是——能化就化，不能化就用循环加栈。

常见错误

• 漏写基例或初值。 递推式 $a_n=2a_{n-1}$ 配 $a_0=1$ 是 $2^n$，配 $a_0=7$ 是 $7\cdot 2^n$，不配初值则根本不定义唯一数列。$k$ 阶递推需要恰好 $k$ 个初值。
• 把 $T(n/2)$ 的 $n$ 当成永远偶数。 严谨的写法是 $T(n)=T(\lfloor n/2\rfloor )+T(\lceil n/2\rceil )+f(n)$ 之类。好消息是：渐近分析里只取 $n$ 为 2 的幂（或适当取整），结果不变，Rosen 教材对这一约定有标准说明。但要意识到这是一种约定，不是”递推式自己成立”。
• 主定理不适用时硬套。 典型是 $T(n)=2T(n/2)+n\log n$：$f$ 与 $n^{{\log }_{b}a}=n$ 只差一个对数因子，三种情形哪个都不满足，不能拍脑袋归到情形 2。这时只能回到递归树逐项展开：第 $j$ 层代价 $n\log (n/2^j)$，共 $\log n$ 层，求和得 $\Theta (n(\log n{)}^2)$。记住主定理的适用前提是 $f$ 与 $n^{{\log }_{b}a}$ 有多项式量级的差距。
• 迭代展开后不验证。 展开法中”看出”的规律是猜想，必须用归纳法证明，正如例 1 的验证步骤。
• 复杂度记号混用。 递推式求通项用等号（$T(n)=2^n-1$）；复杂度判定用 $\Theta$、$O$，不要把 $T(n)=O(n\log n)$ 写成 $T(n)=n\log n$。

练习

练习 1. 解递推式 $a_n=2a_{n-1}+1$，$a_0=0$。

答案：不动点 $a^{\ast }=\frac{1}{1-2}=-1$，套一阶公式 $a_n=2^n(0-(-1))+(-1)=2^n-1$。也可直接看出 $a_n+1=2(a_{n-1}+1)$，即 $a_n+1$ 是公比 2 的等比数列。与例 1 同式，可见汉诺塔递推的解就是”加一化等比”的样板。

练习 2. 用特征方程解 $a_n=6a_{n-1}-9a_{n-2}$，$a_0=1$，$a_1=6$。

答案：特征方程 $r^2-6r+9=0$，即 $(r-3{)}^2=0$，重根 $r_0=3$。通项 $a_n=(A+Bn)3^n$。代入初值：$A=1$；$3(A+B)=6$ 得 $B=1$。故 $a_n=(n+1)3^n$。检验：$a_2=6\cdot 6-9\cdot 1=27$，公式给出 $3\cdot 9=27$，一致。本题专门练习重根情形。

练习 3. 用主定理判定 $T(n)=2T(n/4)+\sqrt{n}$。

答案：$n^{{\log }_{4}2}=n^{1/2}=\sqrt{n}$，$f(n)=\sqrt{n}$ 恰与它同阶，是情形 2（不是情形 1 或 3——没有 $\epsilon$ 的余地）。故 $T(n)=\Theta \left(\sqrt{n}\log n\right)$。注意别因为 $\sqrt{n}$ “长得小”就误判成情形 1。

练习 4. 某活期账户月利率 $0.4\%$，月初存入 10 万元后不再存取。写出第 $n$ 个月末余额的递推式与通项，并回答大约多少个月后余额翻倍。

答案：设余额 $B_n$（万元），$B_n=1.004B_{n-1}$，$B_0=10$。等比数列，$B_n=10\times (1.004{)}^n$。翻倍要求 $(1.004{)}^n=2$，$n=\frac{\ln 2}{\ln 1.004}\approx 173.6$，约 174 个月（约 14.5 年）。对照”72 法则”估算 $72/0.4=180$，量级吻合。

学习路径

• 返回 离散数学总览
• 返回 数学基础专题首页
• PREV：数论初步
• NEXT：生成函数