1, 2, 4, 8, 16 …… 数列的下一项是什么？

1, 2, 3, 5, 8 …… 数列的下一项是什么？

递推就是指从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果。

可用递推算法求解的问题一般有以下两个特点：

问题可以划分成多个状态；
除初始状态外，其它各个状态都可以用固定的递推关系式来表示.

利用递推算法解决问题，需要做好以下四个方面的工作：

确定递推变量应用递推算法解决问题，要根据问题的具体实际设置递推变量。递推变量可以是简单变量，也可以是一维或多维数组。从直观角度出发，通常采用一维数组。
建立递推关系递推关系是指如何从变量的前一些值推出其下一个值，或从变量的后一些值推出其上一个值的公式（或关系）。递推关系是递推的依据，是解决递推问题的关键。有些问题，其递推关系是明确的，大多数实际问题并没有现成的明确的递推关系，需根据问题的具体实际，通过分析和推理，才能确定问题的递推关系。
确定初始（边界）条件对所确定的递推变量，要根据问题最简单情形的数据确定递推变量的初始（边界）值，这是递推的基础。
对递推过程进行控制递推过程不能无休止地重复执行下去。递推过程在什么时候结束，满足什么条件结束，这是编写递推算法必须考虑的问题。递推过程的控制通常可分为两种情形：一种是所需的递推次数是确定的值，可以计算出来；另一种是所需的递推次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对递推过程的控制；对于后一种情况，需要进一步分析出用来结束递推过程的条件。

递推通常由循环来实现，一般在循环外确定初始（边界）条件，在循环中实施递推。

递推法从递推方向可分为顺推与倒推。

顺推法

所谓顺推法是从已知条件出发，逐步推算出要解决的问题的方法叫顺推。
如斐波拉契数列，设它的函数为f(n),已知f(1)=1，f(2)=1;f(n)=f(n-2)+f(n-1)(n>=3,n∈N)。则我们通过顺推可以知道,f(3)=f(1)+f(2)=2,f(4)=f(2)+f(3)=3……直至我们要求的解。

逆推法

所谓逆推法从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件，即顺推法的逆过程，称为逆推。

一句话概括：顺推是从条件推出结果，倒推从结果推出条件。

递推算法的经典例子

【案例】从原点出发，一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点共有多少种走法？

样例输入：N=2

样例输出：result=7

样例输入：N=3

样例输出：result=17

解题思路：要解决走N步共有多少种走法，我们在拿到题目的时候最直接的想法就是先画出当N=1、N=2、N=3。。。。。N=n时对应走法的图例，由简单到复杂、由特殊到一般的推理过程，找出规律获得解题的思路。在数学上，我们称为归纳法。如果用编程的方法来求解这样的推理题，我们把这样的求解思路（算法）称之为递推法。递推的精髓在于f（n）的结果一般由f(n-1)、f(n-2)…..f(n-k)的前k次结果推导出来。我们在解决这类递推问题时，难点就是如何从简单而特殊的案例，找到问题的一般规律，写出f（n）与f(n-1)、f(n-2)…..f(n-k)之间的关系表达式，从而得出求解的结果。在历年noip的复赛当中，参赛选手对于这类题目都有这样的感受，往往花费了大量的时间来分析题目的一般规律，写出f（n）的一般表达式，而编程实现可能只需要几分钟的时间。所以我们在平时训练的时候，对于这样的递推题目，就必须掌握如何分析问题，从特殊推导出一般的规律，写出想要的关系表达式，问题就迎刃而解了。下面是这道题解题的心得，供大家参考：

（1）当N=1时，绘出走法图

（图1）共有3种不同的走法，也就是黑色线条的数量，即f(1)=3

（2）当N=2时，绘出走法图

此图像的alt属性为空；文件名为12091211271664-1024x231.png

（图2）共有7种不同的走法，也就是绿色线条的数量，即f(2)=7

（3）当N=3时，绘出走法图

此图像的alt属性为空；文件名为12091211276184-1024x271.png

（图3）共有17种不同的走法，也就是红色线条的数量，即f(3)=17

由此，我们不难看出，对于任何一个起点，最多可以走出3种走法，但最少必须走出2种走法。那么我们要求出f(n)，实际上转换为如果我们能够得到上一步即f（n-1）有多少个终点是有3种走法的，有多少个点有2种走法的，那么问题就解决了。

a. 上一步，即f（n-1）有多少个终点是有3种走法的。

此图像的alt属性为空；文件名为12091211294574-1024x259.png

对于N=3时，f(n-1)=f(2), 有3个点A、B、C可以走出3种不同走法的，这3个点是怎么得到的呢？它的存在与N值有没有必然的联系？如果我们能找到它与N之间的关系，问题也就解决了。有了这样的思路以后，我们不难找到这样的规律：如果f（n-2）存在，即上上步存在，那么从上上步出发的线路里面必然会有一条向上走的线路，而这条向上走的线路在到达f（n-1）之后，向f（n）出发时也必然有左、上、右这三种走法，那么我们就得出了这样的结论：当f（n-2）存在时，f（n-2）的值实际上就等价于f（n-1）有多少个终点是有3种走法。

b. f（n-1）有多少个终点是有2种走法的

此图像的alt属性为空；文件名为12091211303358-1024x274.png

对于N=3时，有4个点D、E、F、G可以走出2种不同走法的，这4个点又是怎么得到的呢？它与N值有什么联系呢？实际上我们在解决了上一个问题的时候，这个问题就变得相当容易了， f（n-1）减掉刚才有3种走法的点，剩下的点不就是只有2种走法了吗？即f（n-1）-f（n-2）。

c. 得出f（n）的一般关系式

f(n)=3*f(n-2)+2*(f(n-1)-f(n-2) ) (n>=3)

化简：

f(n)=2*f(n-1)+f(n-2) (n>=3)

有一点需要补充的就是，任何递推题，都会有临界条件。当N=1时，f(n)=3;,当N=2时，f(n)=7,这些都可以看成是临界条件。只有当N>=3时，即上上步存在的情况下，就可以得出f(n)的一般通式：f(n)=2*f(n-1)+f(n-2)

#include <stdio.h>
using namespace std;
int main()
{
   int n;
   int i;
   int fn_1,fn_2;
   printf("please input n=");
   scanf("%d",&n); //输入任意n值
   int fn=0;
   if(n==1)
     fn=3; //初始化当n=1和n=2时的临界条件
   else if(n==2)
     fn=7;
   else{
     fn_1=7;
     fn_2=3;
     for(i=3;i<=n;i++)
     {
        fn=2*fn_1+fn_2; //当n>=3时fn的通式
        fn_2=fn_1;//更新fn_1和fn_2的值
        fn_1=fn;
     }
   }
   printf("一共有%d种走法！\n",fn);  //输出结果
   return 0;
}

Level3题解（1-10）

顺推法

逆推法

递推算法的经典例子