递推法

方法定义

所谓递推法，是指通过已知条件，利用特定关系得出中间推论，进而得到结果的一种推理方法。

核心思想

递推法的核心在于**“建立状态间的逻辑联系”**。在实际解题中，一般从三个关键角度进行思考：一是“列举找规律”，通过计算前几步的简单情形，发现隐藏的周期性或通项特征；二是“找相邻项之间的关系”，从第 $n$ 步与第 $n+1$ 步（或第 $n+2$ 步）的变化规则中抽象出递推方程；三是“整体考虑”，结合方程、映射或不动点理论，将递推关系转化为通项公式从而得出结果。

适用题型

该方法广泛涉及函数、数列、计数原理、概率与统计等模块。特别适用于：

1. 函数的多重迭代求值问题（如求高阶复合函数 $h^{(n)}(x)$ 的值）。
2. 已知特殊递推关系的数列求通项公式或高次项求值问题。
3. 多步骤的动态排列组合计数问题（如质点在坐标轴上的随机跳动路径数）。
4. 具有重复操作特征的概率计算问题（如多次重复摸球、多局比赛等状态转移概率的求解）。

识别信号

1. 高阶迭代或超大下标：题目要求计算极高项数的函数迭代值或数列项（如求 $h^{(8)}(1)$ 或 $a_{2022}$），这强烈暗示不能死算，需通过递推寻找周期或规律。
2. 规则重复的动态过程：题干中出现“每次向正方向或负方向跳1个单位”、“重复 $n$ 次这样的操作”等描述，暗示需要关注第 $n$ 步状态到第 $n+1$ 步状态的演变，从而建立递推式（如 $p_{n+1}$ 与 $p_n$ 的关系）。
3. 连续相邻项的线性关系：已知条件呈现 $a_{n+2} = a_{n+1} + a_n$ 或 $a_{n+1} = -f(a_n)$ 等结构，明确指向递推求解。

标准解题步骤

1. 穷举试探，投石问路：对 $n=1, 2, 3, 4$ 等初始状态进行列举计算，观察数据变化，猜测可能存在的周期性规律或等差、等比特征。
2. 梳理规则，构建递推式：若无法直接看出规律，则深入分析问题机制。利用分类加法或分步乘法原理（或全概率公式），写出相邻状态（如 $n$ 与 $n+1$）之间的数量转化等式。
3. 转化结构，求解通项：运用特征根方程、不动点法、累加累乘法或构造新数列的方法，将写出的递推关系式彻底转化为通项公式。
4. 代入求解，得出结论：利用求出的通项公式或周期性规律，代入题目要求的具体参数（如 $n=2022$）得出最终答案。

一个简短示例

题目：已知 $f(x) = \frac{1}{x+1}$，数列 $\{a_n\}$ 满足 $a_1=1$，$a_{n+1}=-f(a_n)$，求 $a_{2022}$ 的值。

解答：利用列举法寻找迭代递推的规律。 由题意知递推关系为 $a_{n+1} = -\frac{1}{a_n+1}$。 因为 $a_1=1$，代入递推式可得： $a_2 = -\frac{1}{1+1} = -\frac{1}{2}$； $a_3 = -\frac{1}{-\frac{1}{2}+1} = -2$； $a_4 = -\frac{1}{-2+1} = 1$。 由此可知，$a_4 = a_1$，数列 $\{a_n\}$ 是一个以 3 为周期的周期数列。 因为 $2022 = 3 \times 674$， 所以 $a_{2022} = a_3 = -2$。

常见误区

1. 迷信死算，忽视周期与规律：面对高阶的多重迭代求值问题，只知低效的埋头死算，缺乏主动“列举前几项找规律”的意识，未能及时发现数列或函数中隐藏的周期性循环。
2. 递推状态分类遗漏或重叠：在处理计数或概率的递推问题时，对第 $n$ 步到第 $n+1$ 步的所有可能转移路径考虑不全，导致建立的递推关系式系数发生错误。
3. 不会处理一阶分式递推式：面对类似于 $a_{n+1}=\frac{pa_n+q}{ta_n+s}$ 的递推式，缺乏使用“不动点法”构造等比（或等差）数列的化归技巧，导致递推式无法转化为通项公式。