1 基本概念
1.1 递推关系的定义
递推关系是用已知的前若干项来定义序列后续项的规则。与直接给出通项公式不同，递推方式强调“由前推后”的构造过程，常用于描述按阶段演化的对象。若一个序列满足某种固定的递推式，并配合初始数据，就可以逐步计算出整个序列。
1.2 齐次与非齐次的区别
齐次递推是指递推式右侧只含序列项本身及其组合，不包含额外的独立项。与之相对，非齐次递推通常在右侧额外加入一个与序列无直接依赖的项，例如常数项、函数项或外部输入项。前者更适合刻画内部规律自洽演化的过程，后者则常用于描述带有外部驱动的系统。
1.3 线性齐次递推
线性齐次递推是最常见的一类形式，其特征是各项以线性方式组合，不出现项与项之间的乘积、幂次或其他非线性运算。其一般结构可写为若干前项的线性组合等于当前项，或等价地把下一项表示成前项的加权和。这类递推在理论上较易分析，常可借助代数工具求解。
1.3.1 常系数递推
常系数递推指递推关系中的系数保持不变，不随项数变化而改变。例如，当前项由固定几个前项按固定权重线性组合而成。这类递推最容易转化为特征方程问题，因此在教材与应用中都十分常见。
1.3.2 变系数递推
变系数递推中，系数会随着项数或阶段变化而改变。由于权重不再固定，求解难度通常高于常系数情形。此类递推常出现在分层结构、非均匀环境或参数逐步变化的模型中。
1.4 初值条件与解的唯一性
递推关系本身只规定了项与项之间的联系，要得到具体序列，还必须给出若干初值条件。对于线性高阶递推，初值个数通常与递推阶数一致。只要递推式和初值都已确定，序列一般就具有唯一性，即每一项都可被逐步确定，不会出现分歧。
2 表达形式与分类
2.1 一阶齐次递推
一阶齐次递推只依赖上一项，形式最为简单。若其系数恒定，则序列通常呈现等比型变化；若系数变化，则序列的伸缩速度会随位置而调整。这类递推适合描述单步传递过程，如连续折算、逐次衰减或累积放大。
2.2 高阶齐次递推
高阶齐次递推依赖多个前项，能够表达更复杂的历史记忆效应。由于当前项受到更远历史信息的影响，这类模型在组合结构、离散动力系统和某些算法分析中较为常见。阶数越高，初值需求通常也越多。
2.2.1 二阶齐次递推
二阶齐次递推依赖前两项，是最典型的高阶情形之一。许多经典数列都可归入这一类别，例如其下一项由前两项的固定线性组合给出。二阶形式便于展示特征根、重根与通解结构等核心概念。
2.2.2 多阶齐次递推
多阶齐次递推涉及三项及以上的历史项，常用于刻画更复杂的局部依赖关系。随着阶数增加，分析过程通常更依赖系统化方法，如矩阵表示或生成函数。其解的结构往往由若干基本解叠加而成。
2.3 线性齐次递推与非线性齐次递推
线性齐次递推中的各项只以一次幂出现，并按线性方式相加；非线性齐次递推则允许出现乘积、平方、取最大值等非线性操作。线性情形通常可获得较完整的解析结果，而非线性情形更常依赖定性分析、数值计算或特殊技巧。两者都属于齐次范畴，因为其右侧不含独立外加项。
2.4 常系数与非常系数
常系数递推的结构稳定，便于分类与求解；非常系数递推则更具灵活性，能够反映环境变化或阶段差异。前者往往与特征方程直接对应，后者则可能需要变换、归一化或递推变形等手段处理。二者在建模中的选择，通常取决于实际问题是否具有固定规律。
3 求解方法
3.1 迭代展开法
迭代展开法是最直接的求解方式，即将递推式不断代入前项，逐步展开到初值。它适合低阶或结构简单的递推，也有助于观察序列前几项的模式。通过这种方式，有时可以猜测通项形式，再进一步证明。
3.2 特征方程法
特征方程法是线性常系数齐次递推的经典方法。其核心思想是设解具有指数型形式，从而把递推问题转化为代数方程。特征方程的根决定了解的基本形态，也决定序列增长的主要行为。
3.2.1 特征根的求法
求特征根时，先将递推式转写为关于指数参数的多项式方程，再求该方程的全部根。若根互异，则对应独立的基本解；若存在复数根，也可通过代数形式或实数形式表述。特征根的分布直接影响通解表达与长期趋势。
3.2.2 重根情形的处理
当特征方程出现重根时，单纯的指数型解不再足以构成完整解集，需要引入附加的多项式因子来补足独立性。一般而言，重数越高，所对应的基本解中多项式的次数也越高。此时通解仍可写成若干基本解的线性组合，但形式较互异根时更复杂。
3.3 矩阵方法
矩阵方法将高阶递推改写为一阶向量递推，从而借助线性代数工具处理。通过构造状态向量，可以把原问题转换为矩阵乘法的反复作用。该方法特别适合与特征值分解、幂矩阵计算结合使用。
3.3.1 状态向量表示
状态向量表示法把若干连续项组合成一个向量，使递推关系写成向量与矩阵相乘的形式。这样，原本看似复杂的高阶依赖就被统一到一个线性变换框架中。此法便于进行整体分析，也利于程序实现。
3.3.2 矩阵对角化
若递推对应的矩阵可以对角化，则矩阵幂的计算会显著简化。对角化后，重复作用只需处理对角矩阵的幂，进而得到显式表达。该方法与特征值、特征向量紧密相关，是研究长期行为的重要工具。
3.4 生成函数法
生成函数法把序列编码为一个形式幂级数，再将递推关系转化为函数方程。通过代数运算，可将原来的序列问题转为对函数的求解与展开。此法在组合计数中尤为常用，能够统一处理多种递推结构，并帮助提取通项系数。
3.5 归纳法与猜想验证
归纳法常用于验证由经验或计算猜测出的通项公式。通常先通过前几项观察规律，再提出猜想，最后利用数学归纳法证明其对全部项成立。这一过程虽不总能直接求出答案，但在发现规律和确认结果方面十分有效。
4 解的性质
4.1 通解结构
线性齐次递推的通解通常由若干基本解构成，每个基本解对应特征方程中的一个根或一组根。通解的形式既体现了解的线性组合特征，也反映了初值对最终序列的决定作用。通过匹配初值，便可确定通解中的待定系数。
4.2 解空间与线性组合
在齐次线性递推中，解集通常构成一个线性空间。若若干序列都是解，那么它们的任意线性组合仍然是解。这个性质使得求解问题可以转化为寻找一组基解，再通过线性组合拼装出全部解。
4.3 增长性分析
增长性分析关注序列随项数增加时的速度变化，常用于判断其是缓慢增长、指数扩张还是趋于稳定。对于常系数线性递推，增长速度通常由模最大的特征根主导。分析增长性有助于理解模型的长期行为与规模趋势。
4.3.1 指数增长
当主导特征根的模大于1时，序列往往表现出指数级增长。此时较高阶项在整体中迅速占据主导地位，初值细节只影响常数因子而不改变主要增长率。指数增长是许多递推模型中最显著的行为之一。
4.3.2 多项式因子修正
若存在重根，或多个根在贡献上需要叠加，则解中可能出现乘以多项式的修正因子。这样一来，整体增长虽然仍由指数部分决定，但会被额外的幂次项放大或调节。此类修正常见于重根对应的递推解中。
4.4 稳定性与极限行为
稳定性研究序列是否会围绕某种模式保持有界或收敛。若递推的主导部分具有收缩性质，序列可能趋于极限；若主导根处于临界状态，则可能出现振荡或缓慢变化。极限行为的分析对于判断模型是否长期可控具有重要意义。
5 典型例子
5.1 等比数列
等比数列是最简单的一阶齐次递推例子，其后一项等于前一项乘以固定常数。该序列的通项直接呈现为幂函数形式，结构清晰，便于展示齐次递推的基本思想。它常被用作入门示例。
5.2 斐波那契数列
斐波那契数列满足典型的二阶线性齐次递推，即每一项由前两项相加得到。它在自然结构、组合计数与算法示例中都极为常见。该数列是研究特征方程、生成函数和矩阵方法的经典对象。
5.3 线性组合型递推
线性组合型递推指下一项由多个前项按不同权重线性相加而成。例如，三个或更多历史项共同决定当前项，能够描述更复杂的局部依赖。此类例子常用于说明高阶递推的通解构造。
5.4 组合计数中的齐次递推
在组合计数中，齐次递推常来自“按最后一步分类”或“按局部状态分类”的计数策略。通过把复杂计数对象拆分为若干互斥子类，可以建立仅依赖前项的递推关系。此类问题往往具有清晰的结构和明确的初值。
5.4.1 路径计数问题
路径计数问题常把网格、图或状态空间中的可行路径数量转化为递推关系。某一位置的路径数通常等于若干前驱位置路径数之和，因此自然形成齐次递推。此类模型在离散数学中十分常见。
5.4.2 拆分与铺砖问题
拆分与铺砖问题经常通过“最后放置了什么”来建立递推式。无论是整数拆分还是棋盘铺砖，当前规模的方案数往往由较小规模的方案数组合而来。若没有额外外加项，便可形成齐次递推。
6 应用
6.1 算法与动态规划
在算法中，齐次递推常作为动态规划的状态转移式出现。通过保存前若干状态，可以逐步计算目标值，避免重复求解。对递推结构的理解，有助于优化时间复杂度和空间复杂度。
6.2 数论中的递推结构
数论问题中，某些序列或同余关系也会呈现递推特征。比如在某些除法过程、分解过程或模运算迭代中，状态更新可归纳为齐次递推。此时，递推不仅是计算工具，也是一种描述数值规律的语言。
6.3 图论与路径计数
图论中，顶点间路径数量、状态可达性以及层次传播过程，常可表示为递推关系。若计数规则只依赖前一层或前几层的结果，就容易形成齐次结构。通过递推分析，可以得到路径总数或可达状态的增长趋势。
6.4 计算机科学中的状态转移
计算机科学里的许多状态系统都可用齐次递推刻画，例如缓存命中演化、有限自动机状态统计以及某些迭代式程序的输出模式。递推提供了一种简洁的抽象方式，使复杂过程得以通过少量状态变量描述。它也便于理论分析与程序实现。
6.5 物理与工程中的离散模型
在离散时间的物理与工程模型中，齐次递推常用于描述振动、衰减、传输和反馈过程。若系统在每个时间步的变化只依赖于前一时刻或前几时刻的状态，就可建立相应递推。此类模型常作为连续方程的离散近似，也可独立用于工程控制与信号处理。
7 相关概念
7.1 非齐次递推
非齐次递推在齐次部分之外还包含额外项，因此其解通常由齐次解与特解共同构成。它与齐次递推在结构上密切相关，但分析步骤更为复杂。许多实际问题最终都会先分解为齐次部分再处理外加项。
7.2 差分方程
差分方程是离散形式的方程，描述变量在相邻时刻之间的变化。递推关系可视为差分方程的一种表现形式，尤其在离散动力系统中经常出现。两者在方法上互有交叉，但表述侧重点略有不同。
7.3 线性代数中的特征值问题
特征值问题研究线性变换在特征向量方向上的伸缩行为，与常系数齐次递推的特征方程法本质相通。递推中的主导增长率往往可由对应矩阵的特征值决定。因而，线性代数为递推分析提供了统一框架。
7.4 生成函数与递推关系
生成函数把离散序列转化为形式幂级数，从而把递推问题变成代数或解析问题。它不仅可用于求解通项，还能揭示系数之间的整体联系。对于组合问题和高阶递推，生成函数往往是非常有力的工具。