递推关系是将数列中的项与同一数列的其他项联系起来的方程，所涉及的其他项通常具有较小的下标。配合适当的初始条件，递推关系可以通过逐项计算来定义一个数列。递推关系是递归的数学表达形式，可用于描述数值规律和分析算法。求解递推关系通常是指求出显式公式，或确定其解的增长规律。(discrete.openmathbooks.org)
定义与初始条件
一种常见的有限阶形式为
[ a_n=F(n,a_{n-1},a_{n-2},\ldots,a_{n-k}), \qquad n\ge k, ]
其中，(F) 是给定的函数，(k) 是固定的正整数。当 (F) 确实依赖于前 (k) 项处的那一项时，该递推关系的阶数为 (k)。对于这种显式形式，只要 (F) 的每次求值都有定义，指定 (a_0,\ldots,a_{k-1}) 就能唯一确定后续各项。没有初始条件的递推关系通常描述的是一族数列，而不是某一个数列。(ocw.mit.edu)
例如，
[ a_n=a_{n-1}+d,\qquad a_0=A ]
可得 (a_n=A+nd)。类似地，(a_n=ra_{n-1}) 可得 (a_n=Ar^n)。这些例子说明了递归定义与闭式表达式之间的区别：前者引用先前的值，后者则直接根据下标计算某一项。可以用数学归纳法验证一个待证公式：先检查初始值，再证明该公式满足递推关系。(discrete.openmathbooks.org)
分类
如果递推关系中的数列项都以一次幂出现，且各项之间没有相乘，则称其为线性递推关系。一个 (k) 阶线性递推关系可写为
[ a_n=c_1(n)a_{n-1}+\cdots+c_k(n)a_{n-k}+g(n). ]
当各个 (c_j(n)) 都与 (n) 无关时，称其为常系数递推关系。当 (g(n)=0) 时，称其为齐次递推关系，否则称为非齐次递推关系。对于齐次线性递推关系，解的任意线性组合仍然是解。对于非齐次递推关系，其通解等于一个特解加上相应齐次递推关系的通解。(ocw.mit.edu)
变系数并不一定使递推关系成为非线性的。例如，阶乘满足 (a_n=na_{n-1})，初始条件为 (a_0=1)。这一递推关系是线性的，但其系数依赖于 (n)。相比之下，含有 (a_{n-1}^2) 的表达式是非线性的。因此，线性与否、系数是否变化以及齐次与否，是彼此独立的分类标准。(ocw.mit.edu)
特征根法
对于常系数齐次线性递推关系
[ a_n=c_1a_{n-1}+\cdots+c_ka_{n-k}, ]
代入指数形式的试探解 (a_n=r^n)，可得到特征多项式
[ p(r)=r^k-c_1r^{k-1}-\cdots-c_k. ]
假设 (c_k\ne0)，如果其根 (r_1,\ldots,r_k) 两两不同，则通解为
[ a_n=C_1r_1^n+\cdots+C_kr_k^n. ]
这些常数由初始条件确定，具体做法是求解一个线性方程组。如果根 (r) 的重数为 (m)，则它对应的解的部分为
[ (C_0+C_1n+\cdots+C_{m-1}n^{m-1})r^n. ]
这一方法同样适用于复数根。(math.libretexts.org)
斐波那契数列是一个典型的二阶例子：
[ F_0=0,\qquad F_1=1,\qquad F_n=F_{n-1}+F_{n-2}. ]
其特征方程为 (r^2-r-1=0)。记 (\phi=(1+\sqrt5)/2)、(\psi=(1-\sqrt5)/2)，由初始条件可得
[ F_n=\frac{\phi^n-\psi^n}{\sqrt5}. ]
虽然这个公式含有无理数，但当下标为非负整数时，它给出的值都是整数，因为它满足定义该数列的递推关系和初始条件。(math.libretexts.org)
生成函数
普通生成函数将数列表示为一个幂级数：
[ A(x)=\sum_{n=0}^{\infty}a_nx^n. ]
将递推关系乘以 (x^n)，再对其成立的所有下标求和，就能把数列中的下标移位转化为对 (A(x)) 的代数运算。初始项必须单独处理。这个级数可以作为形式级数来使用，因此这些运算不必依赖于解析意义上的收敛性。(math.libretexts.org)
对于斐波那契数列，由递推关系可得
[ A(x)-xA(x)-x^2A(x)=x, ]
因此
[ A(x)=\frac{x}{1-x-x^2}. ]
将分母因式分解，并利用等比级数展开所得的各个分式，即可重新得到显式公式。更一般地，生成函数将关于带下标项的问题转化为关于代数表达式的问题，随后通过提取系数还原数列。(math.libretexts.org)
算法分析
在计算机科学中，递推关系往往用于描述时间复杂度，而不是单独的数值序列。一个采用分治法的算法，如果产生 (a) 个规模约为 (n/b) 的子问题，并且需要额外完成工作量为 (f(n)) 的操作，通常会得到
[ T(n)=aT(n/b)+f(n). ]
还需指定基本情形和整数取整方式，才能完整定义这一递推关系。对于归并排序，通常采用的递推关系为 (T(n)=2T(n/2)+\Theta(n))，由此得到 (\Theta(n\log n)) 的时间复杂度。二分查找对应的递推关系则为 (T(n)=T(n/2)+\Theta(1))，由此得到 (\Theta(\log n))。(ocw.mit.edu)
求解方法包括反复展开、猜测一个界并用归纳法证明，以及对递归树上的工作量求和。主定理通过比较 (f(n)) 与 (n^{\log_b a})，可以处理许多具有上述分治形式的递推关系。它的各个情形都有特定的增长条件和正则性条件，因此并不是适用于任意递推关系的通用方法。在算法分析中，这类计算复杂性界往往比精确公式更有用，因为它们既能刻画增长规律，又能略去依赖于具体实现的常数。(live.ocw.mit.edu)