递推算法是信息学奥赛（OI）中一种基础且重要的算法思想。它通过已知的初始条件，利用特定的递推关系，逐步推导出后续的数据或结果。递推算法的核心在于找到问题中数据之间的内在联系，将一个复杂的问题分解为一系列简单的步骤，通过不断重复这些步骤来得到最终的解。其功能在于能够高效地解决一些具有规律性和重复性的问题，避免了重复计算，提高了算法的效率。

递推算法适用场景有：

1. 数列问题：当数列中的每一项都可以由前面的若干项通过某种固定的规则计算得出时，递推算法可以轻松解决。例如斐波那契数列，每一项都是前两项之和。
2. 计数问题：在一些需要统计方案数、排列组合数等的问题中，递推算法可以通过分析问题的特点，找出递推关系，从而计算出结果。比如走楼梯问题，计算到达第 $n$ 级楼梯的不同走法数量。
3. 动态规划基础：递推是动态规划的基础，许多动态规划问题可以通过递推的方式来解决。在处理具有最优子结构和重叠子问题的问题时，递推算法可以为动态规划提供思路。

递推算法的关键在于找到合适的递推关系和初始条件。递推关系是指数据之间的数学联系，它决定了如何从已知的项推导出未知的项；初始条件则是递推的起点，没有正确的初始条件，递推过程将无法开始。

递推有两种思考方向：

1. 顺推：从已知的初始条件出发，按照一定的递推规则，逐步计算出后续的结果。
2. 逆推：从问题的目标状态出发，通过逆向的递推关系，逐步推导出初始状态。

斐波那契类

1 1 2 3 5 8 13 ...

当前项是前两项元素之和，我们可以使用数组存储中间结果，则 $f[i]=f[i-1]+f[i-2]$ 同时递推的边界条件为 $f[1]=1,f[2]=1$，目标解即为 $f[n]$

同时，为了节省空间，我们可以迭代的来求解：

a = 1;
b = 1;
for (int i = 3; i <= n; i++) {
	t = a + b;
	a = b;
	b = t;
}

cout << b << endl;

经典例题：洛谷 P1255. 数楼梯

$n$ 级台阶，每次可以走 $1$ 级或者 $2$ 级，求不同走法的方案数。

问题分析：当 $n=1、2、3、4、5...$ 时的方案数是多少？斐波那契数列。 $f[i]=f[i-1]+f[i-2]$ 也可以这样理解，当楼梯级数是 $i$ 的方案数是楼梯级数是 $i-1$ 时走 $1$ 级到达第 $i$ 级的方案数加上楼梯级数是 $i-2$ 时走 $2$ 级到达第 $i$ 级的方案数之和。

经典例题：兔子繁殖问题

雌雄兔子各一只放入养殖场中，每只雌兔在出生两个月后每月产雌雄兔子个一只。第 $n$ 个月后养殖场共有多少对兔子？

问题分析：当 $n=1、2、3、4、5...$ 时答案是多少？斐波那契数列。

汉诺塔类

经典例题：求汉诺塔问题中盘子从 A 柱移动到 C 柱最少移动了多少次？

1. 状态定义：设 $f[i]$ 表示移动 $i$ 个盘子所需要的最少移动次数。
2. 递推关系：
   1. 移动 $i$ 个盘子时，需先将前 $i-1$ 个盘子从 $A$ 柱移动到 $B$ 柱($f[i-1]$ 次)
   2. 再将第 $i$ 个盘子从 $A$ 柱移动到 $C$ 柱($1$ 次)
   3. 最后将 $B$ 柱上的 $i-1$ 个盘子从 $B$ 柱移动到 $C$ 柱($f[i-1]$ 次)
   4. 因此：$f[i]=2\ast f[i-1]+1$
3. 初始条件： $f[1]=1$
4. 递推方向：从 $2$ 到 $n$ 顺推计算出 $f[n]$
5. 数学本质： 等比数列，通项公式为 $f[n]=2^n-1$

经典例题：Jouier 2410. Strange Towers of Hanoi

问题分析：设 $d[n]$ 表示求解 $n$ 盘 $3$ 塔问题的最少步数，$f[n]$ 表示求解 $n$ 盘 $4$ 塔问题的最少步数。$f[n]=mi{n}_{1\le i<n}\{2\ast f[i]+d[n-i]\}$，边界条件：$f[1]=1$。上式的含义是：先把 $i$ 个盘子在 $4$ 塔模式下移动到 $B$ 柱，然后把 $n-i$ 个盘子在 $3$ 塔模式下移动到 $D$ 柱，最后把 $i$ 个盘子在 $4$ 塔模式下移动到 $D$ 柱。考虑所有可能的 $i$，取最小值即可。

平面分割类

经典例题：设有 $n$ 条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。

问题分析：当平面上已经有 $n-1$ 条曲线将平面分割成 $f[n-1]$ 个区域后，画第 $n$ 条曲线时，第 $n$ 条曲线与之前 $n-1$ 条曲线每个曲线都会相交，与每个曲线相交会多产生 $2$ 个区域，共多出来 $2\ast (n-1)$ 个区域。$f[n]=f[n-1]+2\ast (n-1)$，边界条件：$f[1]=2$

例题 2：$n$ 条直线最多将平面分成多少个区域？$n=3$ 时，答案为 $7$。

1. 状态定义： 设 $f[i]$ 表示 $i$ 条直线最多将平面分割成的区域个数。
2. 递推关系：
   1. 第 $i$ 条直线与前 $i-1$ 条直线最多有 $i-1$ 个交点，这些交点将第 $i$ 条直线分成 $i$ 段。
   2. 每段对应一个新增区域，因此新增区域数为 $i$。
   3. 因此：$f[i]=f[i-1]+i$
3. 初始条件：$f[0]=1$（没有直线时，只有一个区域）
4. 递推方向：从 $1$ 到 $n$ 顺推计算出 $f[n]$。
5. 数学本质：通过求和可得：$f[n]=n\ast (n+1)/2+1$。

双递推类

经典例题：位数问题

在所有的 $N$ 位数中，有多少个数中有偶数个数字 $3$？请输出答案对 $12345$ 取余之后的值。

问题分析：设 $f[i][0]$ 表示前 $i$ 位取偶数个 $3$ 有几种情况，$f[i][1]$ 表示前 $i$ 位取奇数个 $3$ 有几种情况。

1. $f[i][0]=f[i-1][0]\ast 9+f[i-1][1]$
2. $f[i][1]=f[i-1][0]+f[i-1][1]\ast 9$
3. 边界条件：$f[1][1]=1,f[1][0]=8$

矩阵递推

经典例题：YBT 1258：数字金字塔

问题分析：设 $f(i,j)$ 表示从 $(1,1)$ 到 $(i,j)$ 的最大路径之和，$f(i,j)=max(f(i-1,j-1),f(i-1,j))+a[i][j]$

边界：$f(1,1)=a[1][1]$

目标解：$max(f(n,j)),1\le j\le n$

错排问题

经典例题：$n$ 个元素排成一列，每个元素都不在原来位置上的排列数，称为错位排列数。求 $n$ 的错位排列数。（$n=3$ 时，答案为 $2$）

1. 状态定义：设 $f[i]$ 表示 $i$ 个元素排成一列的错位排列数。
2. 递推关系：
   1. 考虑第 $i$ 个元素放在第 $k$ 个位置上（$1\le k<i$），分两种情况：
      1. 第 $k$ 个元素放在第 $i$ 个位置上，此时剩下 $i-2$ 个元素需要错位排列，有 $f[i-2]$ 种情况。
      2. 第 $k$ 个元素不放在第 $i$ 个位置上，此时等价于将前 $i-1$ 个元素错位排列（第 $k$ 个元素不放在第 $i$ 个位置上，相当于新的错位问题），有 $f[i-1]$ 种情况。
   2. 因此：$f[i]=(i-1)\ast (f[i-1]+f[i-2])$
3. 初始条件：$f[1]=0$（无法错位），$f[2]=1$（交换两个元素）
4. 递推方向： 从 $3$ 到 $n$ 顺推计算出 $f[n]$。

以上递推方式为顺推，如何进行逆推呢？请同学们思考！