假设你是一位古老家族的家谱管理员。家族有个奇怪的传统：每一代的人数从不由人丁册直接登记，而是由前两代的人数相加得出——第一代和第二代各只有 1 人，那么第三代就是 1+1=2 人，第四代 2+1=3 人……这就是斐波那契兔子家族的由来。在数学里，这种“后一代由前一代（或前几代）的取值推算”的规则，叫作递推关系。 给家族编谱时你会发现，有的家族只靠内部繁衍（齐次递推），有的家族每代都有外姓迁入（非齐次递推），还有的家族喜欢分家，一房变两房、规模逐代缩减（分治递推）。本文就顺着这条“血脉线”展开：先学会用特征方程破解内生家族的繁衍密码，再处理外姓迁入的非齐次问题，接着学习把整本族谱压缩进一张“档案卷宗”的生成函数法，最后用 Master 定理一眼看出分家家族的总开销。学完这些，你就能像老练的家谱师一样，只凭几条规则，算出任意一代的人数。

岗位关联

递推关系是算法复杂度的标尺。掌握它，你才能在写码之前预判递归算法的表现，这是算法工程师、数据科学家与密码学工程师共同的基本功。

目录
  1. 可视化演示
  2. 递推概念建模
  3. 线性齐次递推
  4. 非齐次递推
  5. 生成函数法
  6. 分治递推
  7. Master定理
  8. 经典应用实例
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

递推关系描述数列项间的依赖关系，是算法分析的重要工具。本文详解线性齐次与非齐次递推、特征方程法求解常系数递推、... 切换模式查看不同维度。

本节配有交互动效（进入视口后自动加载，约 3KB）。

递推关系的基：核心原理 动态展示关键流程与数据流动 交互控件调节参数实时渲染 f(x) = transform(x) 核心概念的可视化呈现

递推概念建模

接任家谱管理员的第一天，老管家递给你一张羊皮纸，上面只有一行字：“本族每一代的人数 = 上一代人数 + 上上代人数。”你愣住了——没有登记簿，怎么知道第 100 代有多少人？老管家笑笑：“把最初两代的人数记下来，剩下的一代一代推就是了。”这张羊皮纸上的规则，就是递推关系；最初两代的人数，就是初值条件。

在数学上，递推关系就是用数列前若干项定义后一项的等式。最常见的线性形式是：当前项等于前 k 项各自乘上固定系数后求和，再加上一个只与 n 有关的外部项。若外部项恒为零，说明家族完全内生繁衍，称为齐次递推；否则称为非齐次递推。斐波那契家族就是最纯净的齐次家族——没有任何外来迁入，每一代都严格由前两代相加而来。

一个完整的递推问题由三要素构成：递推关系本身、初值条件、目标（求通项或某一特定项）。递推的“阶”指它回看几代：一阶只依赖前一项，二阶依赖前两项。按依赖是否线性，又分为线性与非线性递推。本文聚焦常系数线性递推，它是算法分析中最常见、也最成体系的一类。

有了这张“羊皮纸”和祖先的初值，任意一代的人数都能一步步推出。但连推 100 代实在太累——这正是后面各节要解决的：把连推的苦力活，变成一眼看穿的公式。

an=c1an−1+c2an−2+⋯+ckan−k+f(n),n≥k\displaystyle a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} + f(n),\qquad n \geq k
这条式子把“每一代由前几代推算”的家规浓缩成一行，是所有递推问题建模的起点。
  1. 当前项 a_n第 n 代家族人口，是我们要推算的目标。
    ana_n
  2. 祖先回看项前 k 代的人口，共同决定当前代的内生基数。
    an−1, an−2, ⋯ , an−ka_{n-1},\ a_{n-2},\ \cdots,\ a_{n-k}
  3. 权重系数 c_i家族规矩里写死的常数，表示各代祖先的影响力度。
    c1, c2, ⋯ , ckc_1,\ c_2,\ \cdots,\ c_k
  4. 外部迁入项 f(n)每代额外迁入的外姓人口；恒为 0 时就是齐次递推。
    f(n)f(n)
  5. 生效范围 n ≥ k从第 k 代起递推才生效，前 k 代由初值条件单独给出。
    n≥kn \geq k

线性齐次递推

治下的家族若是纯内生繁衍——没有外来迁入，每一代人口只由前代按固定比例合成——我们称它为齐次家族。齐次家族的谱牒有个奇妙之处：只要找到一种“人口增长节奏” r（每一代人口乘以 r），任何按此节奏增长的分支叠加起来，仍是合规的家族轨迹。家族史可以看作若干种基本节奏的混音。

把 a_n = r^n 代入递推式 a_n = c_1 a_{n-1} + c_2 a_{n-2}，两边除以 r^{n-2}，立刻得到 r^2 = c_1 r + c_2。这个方程叫特征方程，它的根就是家族血脉的“基本节奏”——每种节奏对应一族按它繁衍的分支。特征方程是 k 次方程，有 k 个根。若根互不相同，通解是各根幂次的线性组合；若出现重根，则要补上 n 的因子，例如二阶重根的通解为 (A + Bn) r^n。

常数 A、B 由初值条件确定，就像用祖辈档案校准谱系。以斐波那契家族为例，特征方程 r^2 - r - 1 = 0 的两个根一正一负，正根就是黄金比例 φ，于是家族任意一代的人口都能用 φ 的幂表示——这就是下一节要讲的比内公式的雏形。

特征方程就像破译家族基因的手工图——把“子孙如何继承”翻译成“代数方程有哪些根”。斐波那契家族正是靠它，被一眼看到第 1000 代的人口规模。

rk−c1rk−1−c2rk−2−⋯−ck=0\displaystyle r^k - c_1 r^{k-1} - c_2 r^{k-2} - \cdots - c_k = 0
特征方程把“血脉继承规则”翻译成“代数方程求根”，是求解线性齐次递推的第一把钥匙。
  1. 成长节奏假设血脉按等比方式繁衍，设第 n 代人口与 r 的 n 次幂成正比。
    an=rna_n = r^n
  2. 代入约分把假设代入递推式，两边同除以公因子 r^{n-2}，得到关于 r 的二次方程。
    rn=c1rn−1+c2rn−2  ⟹  r2=c1r+c2r^n = c_1 r^{n-1} + c_2 r^{n-2} \;\Longrightarrow\; r^2 = c_1 r + c_2
  3. 特征多项式k 阶递推对应 k 次特征方程，恰有 k 个根（含重根与复根）。
    rk−c1rk−1−⋯−ck=0r^k - c_1 r^{k-1} - \cdots - c_k = 0
  4. 通解叠加每个特征根对应一种血脉节奏，通解是这些节奏的线性组合。
    an=A1r1n+A2r2n+⋯+Akrkna_n = A_1 r_1^n + A_2 r_2^n + \cdots + A_k r_k^n

非齐次递推

有些家族没那么纯粹，每隔一代就有一批外姓人迁入：第 n 代迁入 f(n) 人。这条外部规则，让单纯的节奏叠加失了效。老管家教你一个诀窍：把家族轨迹拆成两部分——一部分是纯内生血脉（齐次通解），一部分是外来移民的单独贡献（特解），合起来就是真实人口。

数学上这叫叠加原理：非齐次递推的通解 = 对应齐次递推的通解 + 一个特解。特解怎么找？最常用的是待定系数法：按 f(n) 的形状设一个待定形式——f(n) 是常数就设常数型，是多项式就设同次多项式，是 d^n 就设 A·d^n——代回原式反解系数。

有个细节像“共振”：如果 f(n) 的形状恰好撞上齐次通解的节奏（比如 f(n) = A·2^n 而 2 恰是特征根），设的特解必须乘上 n 的若干次方才行。这个修正因子 n，是初学者最容易漏掉的关键。汉诺塔的僧侣家族正是非齐次的活例子：每代固定迁入 1 人（搬一次底座盘），最终人口为 2^n - 1。

把“内生血脉 + 外来贡献”看成一次简单的相加，非齐次就不再可怕。汉诺塔的 2^n - 1，就是这条法则最漂亮的产物。

an=A r1n+B r2n+an(P)\displaystyle a_n = A\, r_1^n + B\, r_2^n + a_n^{(P)}
非齐次问题的答案分两层：内生血脉按老规矩走，外来迁入单独算一份，两者相加互不干扰。
  1. 内生部分先忽略外部迁入项，按特征方程求出纯血脉的齐次通解。
    an(H)=A r1n+B r2na_n^{(H)} = A\, r_1^n + B\, r_2^n
  2. 外来部分找一个特解，单独负责满足含 f(n) 的原方程，与初值无关。
    an(P)=nm dn Q(n)a_n^{(P)} = n^m\, d^n\, Q(n)
  3. 谐振修正若 d 恰好是特征根，特解必须乘上 n^m 的修正因子，避免被齐次通解“吸收”。
    nmn^m
  4. 叠加定参通解 = 齐次通解 + 特解，最后用初值确定系数 A、B。
    an=an(H)+an(P)a_n = a_n^{(H)} + a_n^{(P)}

生成函数法

老管家还有一本更神气的家谱——不是一页页登记，而是把整支家族压缩成一张“档案卷宗”：一个幂级数 G(x)，x^n 的系数就是第 n 代的人口。卷宗看似无穷长，但递推关系能让它“卷”成一个简洁的闭合式。

对斐波那契家族（F_0 = 0，F_1 = 1），把 G(x) 乘以 (1 - x - x²)，利用递推关系逐项抵消，几乎所有项都消掉，剩下的只有开头一项 x，于是得到 G(x) = x / (1 - x - x²)。这就是生成函数法的四步套路：构造幂级数 → 用递推化简 → 得闭合式 → 展开取系数。

闭合式看着清爽，但要读到第 n 代人口，还得“打开卷宗”：把它拆成部分分式之和，每一个分式对应一个几何级数展开。于是 x^n 的系数一望可知——比内公式正是这样从生成函数里“解压”出来的。生成函数法尤其擅长处理卷积型递推，比如后面会遇到的卡特兰数。

生成函数法像把整本族谱扫描进一台“压缩档案机”：递推是扫描规则，闭合式是压缩包，部分分式是解压算法，最后取系数等于“解压出那一代人的花名册”。下次遇到难缠的递推，别忘了那台卷宗机。

G(x)=∑n=0∞Fnxn=x1−x−x2\displaystyle G(x) = \sum_{n=0}^{\infty} F_n x^n = \frac{x}{1 - x - x^2}
生成函数像一个压缩档案，把无穷多代人口装进一个式子，取 x^n 系数就是解压第 n 代。
  1. 谱牒卷宗把数列整体装进幂级数，x^n 的系数承载第 n 代信息。
    G(x)=∑n=0∞FnxnG(x) = \sum_{n=0}^{\infty} F_n x^n
  2. 递推化简乘以 (1 - x - x²) 后逐项抵消，只剩开头一项 x。
    (1−x−x2) G(x)=x(1 - x - x^2)\, G(x) = x
  3. 闭合式得到紧凑的封闭表达式，整本族谱收进一个分式。
    G(x)=x1−x−x2G(x) = \frac{x}{1 - x - x^2}
  4. 部分分式分母因式分解，拆成两个一阶分式，便于逐项展开回取系数。
    x1−x−x2=A1−r1x+B1−r2x\frac{x}{1-x-x^2} = \frac{A}{1-r_1 x} + \frac{B}{1-r_2 x}

分治递推

还有一种家族，规矩是“分家”：每一代把全部人口平均分成 b 份，其中 a 份各自独立繁衍成新的家族分支，此外每代还有一笔公共开销 f(n)——祠堂祭祀、账目合并。这类家族的人口函数 T(n) 满足 T(n) = aT(n/b) + f(n)，是算法复杂度分析中最常见的递推形态。

把分家过程画成家族树（递归树）：根节点是规模 n 的总开销，下一层有 a 个规模 n/b 的子家族，再下一层有 a² 个规模 n/b² 的子家族……直到规模缩到 1。每一层的总开销逐层相加，就是整个家族的总工作量。递归树是理解分治递推最直观的工具。

具体地，第 j 层有 a^j 个节点，每个节点规模为 n/b^j，若单节点开销为 f(n/b^j)，则该层总开销为 a^j f(n/b^j)。把从根到叶子的所有层加起来，再与“叶子层的数量”比较——你会发现，谁占主导，取决于 f(n) 与 n^{log_b a} 的相对大小。这正是下一节 Master 定理的直觉来源。

分治家族的家谱不是一条直线，而是一棵蓬勃的大树。递归树就是这棵树的俯视图——看清每一层有多少房、每房花多少，整棵树的开销便一目了然。

T(n)=a T ⁣(nb)+f(n),T(1)=Θ(1)\displaystyle T(n) = a\, T\!\left(\frac{n}{b}\right) + f(n),\qquad T(1) = \Theta(1)
分治递推刻画“大事化小、小事汇总”的过程，递归树把每一层的成本摊开来看。
  1. 分支数 a每代分家的房数，即子问题个数，要求 a ≥ 1 的整数。
    a≥1a \geq 1
  2. 规模缩减 b每房人口缩为原来的 1/b，b > 1 才能保证最终收敛到规模 1。
    b>1b > 1
  3. 合并成本 f(n)每代把各房账目合起来的开销，如归并排序中合并两个子数组的 O(n)。
    f(n)f(n)
  4. 递归树层数从规模 n 一路缩到 1，共约 log_b n 层。
    log⁡bn\log_b n

Master定理

老管家最后传授的，是“一眼断繁盛”的绝活：对分治家族 T(n) = aT(n/b) + f(n)，只看两股力量——合并成本 f(n) 和叶子规模 n^{log_b a}——谁大，总开销就由谁说了算。这就像赛马场上两匹马的较量，先到终点者主导全局。

记 c = log_b a。若 f(n) 明显小于 n^c（差一个多项式因子 n^ε），叶子层主导，T(n) = Θ(n^c)；若两者势均力敌，则每层开销旗鼓相当，共 log_b n 层，T(n) = Θ(n^c log n)；若 f(n) 明显大于 n^c，且满足正则条件 a·f(n/b) ≤ k·f(n)，则根层主导，T(n) = Θ(f(n))。

三个判据听起来像天平三态：左沉、平衡、右沉。归并排序 T(n) = 2T(n/2) + n 中 c = 1，f(n) = n 与 n^1 打平，落情形 2，复杂度 Θ(n log n)；二分查找 T(n) = T(n/2) + 1 中 c = 0，f(n) = 1 较小，落情形 1，复杂度 Θ(log n)。若 f(n) 恰好落在三情形之间的“缝隙”里，Master 定理失效，递归树便是兜底工具。

Master 定理就是家族相术中的“两股力量赛跑”：f(n) 是日常开销，n^c 是血脉分家的宿命扩张。谁跑得快听谁的，跑平了就数层数——三条口诀，胜过十页推算。

T(n)={Θ(nlog⁡ba),f(n)=O(nlog⁡ba−ε)Θ(nlog⁡balog⁡n),f(n)=Θ(nlog⁡ba)Θ(f(n)),f(n)=Ω(nlog⁡ba+ε), af(n/b)≤kf(n)\displaystyle T(n) = \begin{cases} \Theta\left(n^{\log_b a}\right), & f(n) = O\left(n^{\log_b a - \varepsilon}\right) \\[4pt] \Theta\left(n^{\log_b a}\log n\right), & f(n) = \Theta\left(n^{\log_b a}\right) \\[4pt] \Theta(f(n)), & f(n) = \Omega\left(n^{\log_b a + \varepsilon}\right),\ a f(n/b) \leq k f(n) \end{cases}
Master 定理就是一张对照表：比较 f(n) 与 n^{log_b a} 的强弱，直接读出复杂度。
  1. 临界指数 c叶子层的增长指数，是一切比较的裁判基准。
    c=log⁡bac = \log_b a
  2. 情形1·叶子主导合并成本太小，总开销由最底层叶子数量决定。
    T(n)=Θ(nc)T(n) = \Theta\left(n^c\right)
  3. 情形2·势均力敌两层开销同阶，总开销 = 每层开销 × 层数。
    T(n)=Θ(nclog⁡n)T(n) = \Theta\left(n^c \log n\right)
  4. 情形3·根主导合并成本占优，还需额外满足正则条件 a f(n/b) ≤ k f(n)。
    T(n)=Θ(f(n))T(n) = \Theta(f(n))

经典应用实例

学到这里，老管家带你巡礼家族史上的几个名门。第一门是斐波那契的兔子家族：F_n = F_{n-1} + F_{n-2}，特征方程 r² - r - 1 = 0 给出黄金比例 φ，通解就是著名的比内公式——代数方法竟能写出无穷数列的“统一表达式”。

第二门是汉诺塔的僧侣家族：H_n = 2H_{n-1} + 1，是非齐次递推的标准样板，解出 H_n = 2^n - 1。第三门是卡特兰家族：C_n 满足卷积型递推 C_n = Σ C_i C_{n-1-i}，生成函数法把它化为二次方程，得到 C_n = C(2n, n) / (n+1)，括号匹配、二叉树形态、出栈序列的计数都归它管。

回到职业场景：算法工程师分析递归程序时，正是用这些工具把“程序跑多快”翻译成一句话。归并排序、二分查找、分治乘法……它们的复杂度表达式，统统是递推关系求解的产物。递推关系是连接数学与算法的第一座桥。

巡礼结束，你会发现所有名门的发家史都遵循同一套家谱法则：内生则有特征方程，外迁则加特解，分家则看 Master。递推关系这把钥匙，从此收在你算法工具箱的第一格。

Fn=15[(1+52)n−(1−52)n]\displaystyle F_n = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n} - \left(\frac{1-\sqrt{5}}{2}\right)^{n}\right]
比内公式是特征方程法的一个漂亮战果：斐波那契家族千代人口，一个根号公式全部装下。
  1. 特征根方程 r² - r - 1 = 0 的两个根，一正一负。
    φ=1+52,ψ=1−52\varphi = \frac{1+\sqrt{5}}{2},\qquad \psi = \frac{1-\sqrt{5}}{2}
  2. 通解组合F_n = A φ^n + B ψ^n，用初值 F_0 = 0、F_1 = 1 解出 A、B。
    Fn=A φn+B ψnF_n = A\,\varphi^n + B\,\psi^n
  3. 定出系数解得 A = 1/√5，B = -1/√5。
    A=15,B=−15A = \frac{1}{\sqrt{5}},\qquad B = -\frac{1}{\sqrt{5}}
  4. 比内公式代入即得封闭解，第 n 代人口一跃而出，无需逐代递推。
    Fn=φn−ψn5F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}

AI 应用场景

递归算法复杂度预评估

阶段：算法设计与性能分析

解决的问题：传统做法是先把递归程序写出来再压测，数据规模一上来才发现指数级爆炸，返工成本极高。AI 时代的工程实践要求在写码前先用递推关系建模：把候选算法的递归式写出来，套特征方程或 Master 定理，一分钟内判断它能否撑住百万级输入。

具体案例：某推荐系统团队重构排序模块，三个候选方案：归并排序 T(n)=2T(n/2)+n → Θ(n log n)，二分插入优化 T(n)=T(n/2)+1 → Θ(log n)，而一个“每次只减一个规模”的递归选择算法 T(n)=T(n-1)+n → Θ(n²)。工程师用 Master 定理当场淘汰第三个方案，节省了一周的无谓开发。

密码学中的线性反馈移位寄存器

阶段：数据加密与伪随机数生成

解决的问题：流密码需要周期长、统计均匀的密钥流。线性反馈移位寄存器（LFSR）本质上是在 GF(2) 上运行的线性齐次递推：s_{n+k} = c_1 s_{n+k-1} + …… + c_k s_n (mod 2)。用特征多项式（本原多项式）分析，可以让序列周期达到 2^k - 1 的理论上限。

具体案例：3GPP 通信标准中扰码序列的生成、蓝牙的跳频序列都基于 LFSR。安全工程师挑选本原多项式时，就是在求解“什么样的特征方程能把递推家族的序列周期拉到最长”。

组合计数与状态空间分析

阶段：模型结构探索与组合优化

解决的问题：AI 系统常遇到“合法的组合结构有多少种”这类计数问题——括号匹配、二叉树形态、出栈序列、矩阵链加括号。这类问题收敛到卡特兰数的卷积型递推 C_n = Σ C_i C_{n-1-i}，用生成函数法才能干净地得到闭式。

具体案例：设计语法解析器时，统计 n 对括号能组成多少合法括号串；在神经网络结构搜索中枚举合法表达式树的数量；在概率模型中计算分支过程的灭绝概率——全部由递推关系与生成函数来回答。

Python 演示

python51 行
import math def fib_recurrence(n):    a, b = 0, 1    for _ in range(n):        a, b = b, a + b    return a def fib_closed_form(n):    s = math.sqrt(5)    phi = (1 + s) / 2    psi = (1 - s) / 2    return round((phi ** n - psi ** n) / s) def solve_linear_homogeneous(c1, c2, a0, a1, n):    disc = c1 * c1 + 4 * c2    r1 = (c1 + math.sqrt(disc)) / 2    r2 = (c1 - math.sqrt(disc)) / 2    if disc == 0:        A = a0        B = a1 / r1 - A        return (A + B * n) * (r1 ** n)    B = (a1 - a0 * r1) / (r2 - r1)    A = a0 - B    return A * (r1 ** n) + B * (r2 ** n) def hanoi_moves(n):    return 2 ** n - 1 def master_classify(a, b, k):    c = math.log(a, b)    if k < c - 1e-9:        return "T(n) = Theta(n^log_b a) = Theta(n^{:.2f})".format(c)    if abs(k - c) < 1e-9:        return "T(n) = Theta(n^log_b a * log n) = Theta(n^{:.2f} log n)".format(c)    return "T(n) = Theta(f(n)) = Theta(n^{})".format(k) if __name__ == "__main__":    for n in range(15):        assert fib_recurrence(n) == fib_closed_form(n)    print("Fibonacci: recurrence == Binet, n = 0..14")     for n in range(8):        v = solve_linear_homogeneous(1, 1, 0, 1, n)        assert abs(v - fib_recurrence(n)) < 1e-9    print("Characteristic equation verified for Fibonacci")     print("Hanoi(3) =", hanoi_moves(3))    print("Merge sort   T(n)=2T(n/2)+n   :", master_classify(2, 2, 1))    print("Binary search T(n)=T(n/2)+1   :", master_classify(1, 2, 0))    print("Strassen      T(n)=7T(n/2)+n^2:", master_classify(7, 2, 2))
目的：用三种工具（逐代递推、比内公式、特征方程）求解同一递推并互相验证，再用 Master 定理秒判常见递归算法的复杂度。
  1. a, b = b, a + b一代代顺推，等价于递推公式 F_n = F_{n-1} + F_{n-2} 的编程表达。
  2. phi = (1 + s) / 2黄金比例，即特征方程 r² - r - 1 = 0 的正根，家族人口的“成长节奏”。
  3. return round((phi ** n - psi ** n) / s)比内公式：跳过所有中间代，直达第 n 代。
  4. disc = c1 * c1 + 4 * c2特征方程判别式，判断两根相异还是重根。
  5. B = (a1 - a0 * r1) / (r2 - r1)用初值反解通解系数，像用祖辈档案校准家谱。
  6. if disc == 0:重根情形：两房节奏相同，通解需乘 n 因子区分。
  7. return (A + B * n) * (r1 ** n)重根通解 (A + Bn)r^n 的落地实现。
  8. c = math.log(a, b)计算临界指数 log_b a，Master 定理的裁判基准。
  9. if k < c - 1e-9:情形一：合并成本低于叶子扩张，总复杂度取 Θ(n^c)。
  10. print("Merge sort T(n)=2T(n/2)+n:", master_classify(2, 2, 1))归并排序落入情形 2，输出 Θ(n log n)。

常见误区

误区我把递推式里的系数直接抄进方程，比如 a_n = 3a_{n-1} + 2a_{n-2} 就写成 x² + 3x + 2 = 0，结果求出来的通解怎么代初值都不对。

正解正确做法是“移位再变号”：递推式是 r^n = c_1 r^{n-1} + c_2 r^{n-2}，约去 r^{n-2} 得 r² = c_1 r + c_2，移项后是 r² - c_1 r - c_2 = 0。家族规律是“当前代 = 回看代的加权和”，写成方程要把所有项挪到一侧，符号自然就出来了。

为何常见：教材常把结论压缩为“特征方程”三个字，学生只背不推，符号自然串位。

误区f(n) 是常数，我就设特解为常数 C；f(n) 是 2^n，我就设 A·2^n。可有时代回原式却永远解不出系数，怎么算都不对。

正解当 f(n) 的形状撞上特征根时（如 a_n = a_{n-1} + 1，特征根恰为 1），设常数特解会被齐次通解“吸收”，必须乘 n 修正为 C·n。这就像外姓移民的迁入节奏恰好踩中家族的繁衍节拍，族谱上得单独加注“撞期”。

为何常见：初学阶段只做 f(n) 与特征根不相撞的题，根本没建立“共振”的概念。

误区递推关系求解不就是写个递归函数吗？斐波那契用递归复杂度就是 O(2^n)，所以这个数列问题本身就是指数级的。

正解数学递推（recurrence）是描述项与项依赖的等式，求解目标是通项闭式；编程递归（recursion）是函数自调用的实现手段，两者名字像、层次不同。斐波那契数列有 O(1) 的比内公式，递推关系只是“定义”，不是“复杂度”。家谱上的一行规则，不等于抄谱要抄几百年。

为何常见：中文里“递推/递归”读音相近，英文 recurrence/recursion 也让初学者混淆。

误区只要是 T(n) = aT(n/b) + f(n) 的形式，我三步往情形里一对就完事，从不检查前提条件。

正解Master 定理要求 a、b 为正常数（b > 1）、f(n) 渐近为正，且比较的是“多项式差距”；情形 3 还要求正则条件 a·f(n/b) ≤ k·f(n)。当 f(n) 夹在两种情形之间的缝隙（如 n log n 与 n^c 不差多项式因子）时，定理不适用，得退回递归树逐层求和。

为何常见：三个漂亮结论太好用，教材又很少展示反例，学生默认它是万能公式。

误区我用生成函数法得到了 G(x) = x/(1 - x - x²)，答案不就出来了？至于 x^n 的系数，交给计算机就好。

正解生成函数只是“压缩档案”，灵魂在最后一步“系数提取”：把闭合式拆成部分分式、展开成幂级数，x^n 的系数才是第 n 代人口。只停在闭合式，等于只把族谱压缩没解压，数列通项并未真正写出。

为何常见：部分分式运算繁琐，学习者急于收工，把中间产物当成了最终答案。

面试题

Q1. 斐波那契数列满足 F_n = F_{n-1} + F_{n-2}，且 F_0 = 0，F_1 = 1，那么 F_6 的值是？

单选题 · easy

  • A.5
  • B.8← 正确答案
  • C.13
  • D.21

答案：B。逐代推：F_2=1，F_3=2，F_4=3，F_5=5，F_6=8。这就像家族人口一代代叠加，第六代恰好是 8 人，属于递推关系的直接代入。

Q2. 汉诺塔问题满足 H_n = 2H_{n-1} + 1，H_1 = 1，则移动 3 个圆盘最少需要多少次？

单选题 · easy

  • A.3
  • B.5
  • C.7← 正确答案
  • D.15

答案：C。H_2 = 2×1+1 = 3，H_3 = 2×3+1 = 7。非齐次递推逐代代入即可，不必先求通项公式也能算特定项。

Q3. 递推式 a_n = 5a_{n-1} - 6a_{n-2} 对应的特征方程是？

单选题 · easy

  • A.x² + 5x - 6 = 0
  • B.x² - 5x + 6 = 0← 正确答案
  • C.x² - 5x - 6 = 0
  • D.x² + 5x + 6 = 0

答案：B。设 a_n = r^n，原式化为 r² = 5r - 6，移项得 r² - 5r + 6 = 0。特征方程的符号取决于“移项方向”，不能照抄系数。

Q4. 线性齐次递推的特征方程出现重根 r 时，二阶通解的形式是？

单选题 · mid

  • A.A·r^n + B·r^n
  • B.A·r^n + B·n·r^n← 正确答案
  • C.(A + B)·r^n
  • D.A·n·r^n + B·n²·r^n

答案：B。重根时两条血脉节奏相同，若仍设 A·r^n + B·r^n 会合并成一个待定系数。补乘 n 得到 (A + Bn)·r^n，两房节奏虽同，但相位差一档仍可区分。

Q5. 对非齐次递推 a_n = 2a_{n-1} + 3，a_0 = 1，其通项公式为？

单选题 · mid

  • A.2^n + 3
  • B.2^(n+2) - 3← 正确答案
  • C.3·2^n - 2
  • D.2^(n+1) + 1

答案：B。设常数特解 c：c = 2c + 3 得 c = -3；齐次通解为 A·2^n，故 a_n = A·2^n - 3。由 a_0 = 1 得 A = 4，即 a_n = 2^(n+2) - 3。特解 + 齐次解叠加是标准路径。

Q6. 用 Master 定理分析 T(n) = 2T(n/2) + n²，其渐近复杂度为？

单选题 · mid

  • A.Θ(n)
  • B.Θ(n log n)
  • C.Θ(n²)← 正确答案
  • D.Θ(n² log n)

答案：C。c = log₂2 = 1，f(n) = n² 比 n^1 大一个多项式因子，属情形 3：T(n) = Θ(f(n)) = Θ(n²)。合并成本占主导，子问题再快也追不上每层的开销。

Q7. 设斐波那契数列 F_0 = 0，F_1 = 1，其生成函数 G(x) = Σ F_n x^n 为？

单选题 · hard

  • A.x / (1 - x - x²)← 正确答案
  • B.1 / (1 - x - x²)
  • C.x / (1 + x - x²)
  • D.1 / (1 - 2x)

答案：A。用递推化简：G - xG - x²G = F_0 + (F_1 - F_0)x = x，故 G = x/(1 - x - x²)。若初值取 F_0 = F_1 = 1，分子则变为 1——生成函数与初值绑定得很紧。

Q8. 关于递推关系的求解，下列说法正确的有？

多选题 · mid

  • A.线性齐次递推的通解可表示为特征根幂次的线性组合← 正确答案
  • B.非齐次递推的通解等于对应齐次通解加上一个特解← 正确答案
  • C.任何递推关系都存在闭合形式通项公式
  • D.生成函数法的最后一步是提取幂级数系数← 正确答案

答案：ABD。A、B 是齐次与非齐次递推的叠加原理，D 是生成函数法的收官动作；C 错误——大量非线性或变系数递推没有闭合通项，只能靠数值或渐近分析。

Q9. 下列递推式中，适合直接用 Master 定理分析复杂度的是？

多选题 · hard

  • A.T(n) = 2T(n/2) + n← 正确答案
  • B.T(n) = T(n-1) + n← 正确答案
  • C.T(n) = T(n/2) + 1← 正确答案
  • D.T(n) = T(n-1) + 1
  • E.情形 1 要求 f(n) 比 n^(log_b a) 慢一个多项式因子，结果取 Θ(n^(log_b a))
  • F.情形 2 要求 f(n) 与 n^(log_b a) 同阶，结果取 Θ(n^(log_b a) log n)
  • G.情形 3 除了要求 f(n) 快一个多项式因子，还需满足正则条件 a·f(n/b) ≤ k·f(n)
  • H.只要递归式能写成 aT(n/b) + f(n) 的形式，Master 定理就一定适用

答案：ABC。A、B、C 分别命中三种情形的完整条件；D 错误——当 f(n) 与 n^c 的差距不是多项式量级（如 f(n) = n log n 介于 n 与 n^(1+ε) 之间）或正则条件不满足时，Master 定理失效，应改用递归树逐层求和。