递归关系式

概述

递归关系式（Recurrence Relation）是用递归方式定义序列的数学方程，也是描述递归算法运行时间的核心工具。在算法分析中，最常见的递归关系形式为 $T(n)=aT(n/b)+f(n)$，可通过代入法、递归树法或主定理求解。

定义

递归关系式（Recurrence Relation）

递归关系式是将序列的第 $n$ 项用前面的项来表示的方程。在算法分析中，$T(n)$ 表示规模为 $n$ 的问题的运行时间，递归关系式描述了 $T(n)$ 如何依赖于更小规模的子问题的运行时间。

一般形式：

$T(n)=a\cdot T(n/b)+f(n)$

其中：

• $a\ge 1$：子问题的个数
• $b>1$：子问题的规模缩小因子
• $f(n)$：分解和合并步骤的代价

求解方法

方法	描述	适用场景
代入法	猜测解的形式，用数学归纳法证明	通用方法，但需要先猜出答案
递归树法	将递推展开为树，逐层求和	直观理解，适合推导猜测
主定理法	直接套用主定理的三种情形	形如 $aT(n/b)+f(n)$ 的标准形式
特征方程法	对齐次线性递推求特征根	如Fibonacci递推

核心性质

性质	描述	备注
初始条件	需要指定基本情况（如 $T(1)=\Theta (1)$）	缺少初始条件则递推无唯一解
边界效应	当 $n/b$ 不是整数时需取上界或下界	通常用 $\lceil n/b\rceil$ 或 $\lfloor n/b\rfloor$
齐次 vs 非齐次	齐次递推无常数项，非齐次有	非齐次递推的解 = 齐次通解 + 特解
线性 vs 非线性	线性递推中 $T(n)$ 线性依赖于前面的项	算法递推通常是非线性的

常见递推关系

算法	递推关系	解
归并排序	$T(n)=2T(n/2)+\Theta (n)$	$\Theta (n\log n)$
快速排序（期望）	$T(n)=2T(n/2)+\Theta (n)$	$\Theta (n\log n)$
快速排序（最坏）	$T(n)=T(n-1)+\Theta (n)$	$\Theta (n^2)$
二分搜索	$T(n)=T(n/2)+\Theta (1)$	$\Theta (\log n)$
Strassen	$T(n)=7T(n/2)+\Theta (n^2)$	$O(n^{\lg 7})$
Fibonacci	$T(n)=T(n-1)+T(n-2)+\Theta (1)$	$O({\varphi }^n)$

参见

• 主定理 — 求解标准形式递推关系的直接工具
• 递归树 — 递推关系的可视化分析方法
• 分治法 — 产生递推关系的算法策略
• 特征方程 — 求解齐次线性递推关系的代数方法
• Fibonacci数 — 经典递推关系的示例
• 归并排序 — 递推关系分析的经典案例