1. 递推算法概述

“递推”是计算机解题的一种常用法。利用“递推法”解题首先要分析归纳出“递推关系”。如经典的斐波那契数列问题，用 f(i) 表示第 i 项的值，则 f(1) = 0 ，f(2) = 1，在 n>2 时，存在递推关系：f(n) = f(n-1) + f(n-2) 。

在递推问题模型中，每个数据项都与它前面的若干个数据项（或后⾯的若⼲个数据项）存在⼀定的关联，这种关联一般是通过一个“递推关系式”来描述的。

求解问题时，需要从初始的⼀个或若⼲数据项出发，通过递推关系式逐步推进，从而推导计算出最终结果。这种求解问题的⽅法叫“递推法”。其中，初始的若⼲数据项称为“递推边界”。

1.1 解决递推问题有三个重点：

1. 建立正确的递推关系式；

2. 分析递推关系式的性质；

3. 根据递推关系式编程求解。

1.2 顺推和倒推

递推法分为 “顺推” 和 “倒推” 两类模型：

1. 顺推，就是从问题的边界条件(初始状态)出发，通过递推关系式依次从前往后递推出问题的解；

2. 倒推，就是在不知道问题的边界条件(初始状态)下，从问题的最终解(目标状态或某个中间状态)出发，反过来推导问题的初始状态。