递推

引入

我们常常说的斐波那契数列大家肯定知道，一开始学 OI 时大多数人都是用循环来解决的（c = a + b, a = b, b = c）。但你有没有想过一点，斐波那契数列的公式是 \(\begin{cases}\text{if}\ 1 \le i \le 2 & f_i = 1 \\ \text{if}\ i \ge 3 & f_i = f_{i - 1} + f_{i - 2}\end{cases}\)，如果再复杂一点，那么代码会很难写。下面就介绍一种算法——递推。

概念

递推算法是一种用若干步可重复运算来描述复杂问题的方法。递推是序列计算中的一种常用算法。通常是通过计算前面的一些项来得出序列中的指定项的值。无论顺推还是逆推，其关键是要找到递推式。这种算法能使复杂运算化为若干步重复的简单运算。