递推

考什么 · What it tests

需要先会 · Prerequisites

• 数列与规律 / Sequences and patterns
• 基本计数原理（加法/乘法） / Basic counting (addition/multiplication)
• 代入求值 / Substitution and evaluation

常见套路 · Common moves

1. 先建递推关系再逐项算：想清「第 $n$ 项怎么由第 n-1（和 n-2）项得来」，写出 $a_n = \cdots$，再从小情形一路推上去——递推题的通用主线。

   Build the recurrence, then compute term by term: figure out how term $n$ comes from term n-1 (and n-2), write $a_n = \cdots$, and climb up from small cases — the main line of every recursion problem.
2. 斐波那契型抓「上一步的落点」：能到第 $n$ 级的方式 = 到第 n-1 级加到第 n-2 级（爬楼梯、铺砖），$a_n=a_{n-1}+a_{n-2}$。

   For Fibonacci-type problems, track the last footing: ways to reach step $n$ = ways to step n-1 plus ways to step n-2 (climbing stairs, tiling), so $a_n=a_{n-1}+a_{n-2}$.
3. 从最小情形起步验证：先手算 $a_1,a_2,a_3$ 对不对，再放心用递推公式往上算。

   Start by checking the smallest cases: compute $a_1,a_2,a_3$ by hand to confirm, then trust the recurrence upward.

易错点 · Common pitfalls

• 初始项（$a_1$、$a_2$）设错或漏设：递推靠地基，头一两项错了后面全错。

  Setting or omitting the initial terms ($a_1$, $a_2$) wrongly: recursion rests on its base, so a wrong first term or two derails everything after.
• 递推关系少数了一种来路：数「能从哪些上一步过来」时漏掉一类，$a_n$ 就少一块。

  Leaving a path out of the recurrence: if you miss one way to arrive from a previous step, $a_n$ comes up short.