递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用于数值计算的一个重要算法。这种算法特点是：一个问题的求解需一系列的计算，在已知条件和所求问题之间总存在着某种相互联系的关系，在计算时，如果可以找到前后过程之间的数量关系（即递推式），那么，从问题出发逐步推到已知条件，此种方法叫逆推。无论顺推还是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。
递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了求通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说来，可以将递推算法看成是一种特殊的迭代算法。
递推概念
给定一个数的序列H0,H1,…,Hn,…若存在整数n0，使当n>n0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hi(0<i<n)联系起来，这样的式子就叫做递推关系。
如何建立递推关系
递推关系有何性质
如何求解递推关系
解决递推问题的一般步骤
1.建立递推关系式
2.确定边界条件
3.递推求解
递推的两种形式
顺推法和倒推法
递推的应用分类
一般递推问题
组合计数类问题
一类博弈问题的求解
动态规划问题的递推关系
（一）递推的应用（一般递推问题）
例题2：输出杨辉三角的前N行（HDOJ2032）
Problem Description
还记得中学时候学过的杨辉三角吗？具体的定义这里不再描述，你可以参考以下的图形：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
Input
输入数据包含多个测试实例，每个测试实例的输入只包含一个正整数n（1<=n<=30），表示将要输出的杨辉三角的层数。
Output
对应于每一个输入，请输出相应层数的杨辉三角，每一层的整数之间用一个空格隔开，每一个杨辉三角后面加一个空行。
Sample Input
2 3
Sample Output
1
1 1
1
1 1
1 2 1
代码如下：
#include <iostream>
using namespace std;
int a[31][31];
int main( )
{
int i,j,n;
a[0][0]=a[1][0]=a[1][1]=1;
for(i=2; i<31; i++) {
for(j=0; j<=i; j++) {
if(j==0 || i==j) {
a[i][j]=1;
} else {
a[i][j]=a[i-1][j-1]+a[i-1][j];
}
}
}
while(cin>>n) {
for(i=0; i<n; i++) {
for(j=0; j<=i; j++) {
if(j!=0) cout<<"";
cout<<a[i][j];
}
cout<<endl;
}
cout<<endl;
}
return 0;
}
例题3 : Hanoi塔问题 .
Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图1所示。要求把a柱上n个圆盘按下述规则移到c柱上：
(1)一次只能移一个圆盘；
(2)圆盘只能在三个柱上存放；
(3)在移动过程中，不允许大盘压小盘。
问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？
分析
当n=1时：A->C
当n=2时：A->B,A->C,B->C
当n=3时：
设f(n)为n 个盘子从1柱移到3柱所需移动的最少盘次。
当n=1时，f(1)=1。
当n=2时，f(2)=3。
以此类推，当1柱上有n(n>2)个盘子时，我们可以利用下列步骤：
第一步：先借助3柱把1柱上面的n-1个盘子移动到2柱上，所需的移动次数为f(n-1)。
第二步：然后再把1柱最下面的一个盘子移动到3柱上，只需要1 次盘子。
第三步：再借助1柱把2柱上的n-1个盘子移动到3上，所需的移动次数为f(n-1)。
由以上3步得出总共移动盘子的次数为：f(n-1)+1+ f(n-1)。
所以：f(n)=2f(n-1)+1
hn=2hn-1+1 =2n-1 边界条件：h1=1
（二）递推的应用（组合计数）
例题4：数的计数
【问题描述】我们要求找出具有下列性质数的个数(包含输入的自然数n)，先输入一个自然数n(n≤1000)，然后对此自然数按照如下方法进行处理：
1.不作任何处理；
2.在它的左边加上一个自然数，但该自然数不能超过原数的一半；
3.加上数后，继续按此规则进行处理，直到不能再而 自然数为止；
方法1：用递推
用h[n]表示自然数n所能扩展的数据个数，则：h[1]=1,h[2]=2,h[3]=2,h[4]=4,h[5]=4,h[6]=6,h[7]=6,h[8]=10,h[9]=10。分析上数据，可得递推公式：h[i]=1+h[1]+h[2]+…+h[i/2]。时间复杂度O(n2)。
方法2：是对方法1的改进。我们定义数组s
s(x)=h(1)+h(2)+…+h(x),
h(x)=s(x)-s(x-1)
此算法的时间复杂度可降到O(n)。
方法3：还是用递推
只要做仔细分析，其实我们还可以得到以下的递推公式：
(1)当i为奇数时,h(i)=h(i-1);
(2) 当i为偶数时,h(i)=h(i-1)+h(i/2);
【例题6】传球游戏
【问题描述】上体育课的时候，小蛮的老师经常带着同学们一起做游戏。这次，老师带着同学们一起做传球游戏。
游戏规则是这样的：n（3<=n<=30）个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以把球传给自己左右的两个同学中的一个（左右任意），当老师再吹哨子时，传球停止，此时，拿着球没传出去的那个同学就是败者，要给大家表演一个节目。
聪明的小蛮提出一个有趣的问题：有多少种不同的传球方法可以使得从小蛮手里开始传的球，传了m（3<=m<=30）次后，又回到小蛮手里。两种传球被视作不同的方法，当且仅当这两种方法中，接到球的同学按照顺序组成的序列是不同的。比如3个同学1号、2号、3号，并假设小蛮为1号，球传了3次回到小蛮手里的方式有1->2->3->1和1->3->2->1，共两种。
分析：
设f[i][k]表示经过k次传到编号为i的人手中的方案数，传到i号同学的球只能来自于i的左边一个同学和右边一个同学，这两个同学的编号分别是i-1和i+1，所以可以得到以下的递推公式：
f[i][k]=f[i-1][k-1]+f[i+1][k-1]
f[1][k]=f[n][k-1]+f[2][k-1], 当i=1时
f[n][k]=f[n-1][k-1]+f[1][k-1], 当i=1时
边界条件：f[1][0]=1；结果在f[1][m]中。
核心代码：
cin>>n>>m;
memset(f,0,sizeof(f));
f[1][0]=1;
for(k=1;k<=m;k++)
{
f[1][k]=f[2][k-1]+f[n][k-1];
for(i=2;i<=n-1;i++)f[i][k]=f[i-1][k-1]+f[i+1][k-1];
f[n][k]=f[n-1][k-1]+f[1][k-1];
}
cout<<f[1][m]<<endl;
（三）递推的应用（组合计数）
Catalan数
定义：Cn=n+2条边的多边形，能被分割成三角形的方案数，例如5边型的分割方案有：
如图，有一个正n+2边形。任取一边，从这边的端点开始，依次顺时针给顶点编号为：0,1,2,3,….,n,n+1(所取的边端点编号为:0,n+1)。这样，除线段所在顶点外，还有n个顶点：1,2,3,…,n。我们以该线段为三角形的一条边，另一个顶点为i(1<=i<=n)。
我们设题意要求的三角形剖分方案数为H(n)，即除线段顶点(编号0与n+1)外，还有n个顶点时的三角形剖分方案为H(n)。则以顶点0,i为指定线段(上面还有1,2,…,i-1，共i-1个顶点)的剖分数位H(i-1)；以顶点n+1，i为指定线段的剖分数为H(n-i)。根据乘法原理，以0,i,n+1为一剖分三角形的剖分数应为：H(i-1)*H(n-i)，i=1,2,…,n，所得的剖分各不相同，根据加法原理则有：
这与Catalan数C(n)的表达式是一致的。故本题答案为H(n)=C(n)。
具体实现时，若直接用上述公式计算，对数字的精度要求较高。可将其化为递推式:
再进行递推计算，并且注意类型的定义要用long long长整型。
（四）递推的应用（博弈问题）
例题：走直线棋问题。
有如下所示的一个编号为1到n的方格：
现由计算机和人进行人机对奕，从1到n，每次可以走k个方格，其中k为集s={a1,a2, a3,....am}中的元素(m<=4)，规定谁最先走到第n格为胜，试设计一个人机对奕方案，摸拟整个游戏过程的情况并力求计算机尽量不败。
分析:
题设条件：若谁先走到第N格谁将获胜，例如，假设S={1,2}，从第N格往前倒推，则走到第N-1格或第N-2格的一方必败，而走到第N-3格者必定获胜，因此在N，S确定后，棋格中每个方格的胜、负或和态（双方都不能到达第N格）都是可以事先确定的。将目标格置为必胜态，由后往前倒推每一格的胜负状态，规定在自己所处的当前格后，若对方无论走到哪儿都必定失败，则当前格为胜态，若走后有任一格为胜格，则当前格为输态，否则为和态。
设1表示必胜态，-1表示必败态，0表示和态或表示无法到达的棋格。
例如，设N＝10，S＝{1,2}，则可确定其每个棋格的状态如下所示：
而N＝10，S＝{2,3}时，其每格的状态将会如下所示：
有了棋格的状态图后，程序应能判断让谁先走，计算机选择必胜策略或双方和（双方均不能到达目标格）的策略下棋，就能保证计算机尽可能不败。
（五）递推的应用（动态规划中的递推）
例题：方格取数
在一个n×m的方格中，m为奇数，放置有n×m个数，如图,方格中间的下方有一人，此人可按照五个方向前进但不能越出方格,见右下图。人每走过一个方格必须取此方格中的数。要求找到一条从底到顶的路径，使其数相加之和为最大。输出和的最大值。
分析:
我们用坐标(x,y)唯一确定一个点，其中(m,n)表示图的右上角，而人的出发点是，受人前进方向的限制，能直接到达点(x,y)的点只有(x+2,y-1)，(x+1,y-1)，(x,y-1)，(x-1,y-1)，(x-2,y-1)。到点(x,y)的路径中和最大的路径必然要从(m/2,0)到(x+2,y-1)，(x+1,y-1)，(x,y-1)，(x-1,y-1)，(x-2,y-1)的几条路径中产生，既然要求最优方案，当然要挑一条和最大的路径，关系式如下：
Fx,y= Max{Fx+2,y-1,Fx+1,y-1,Fx,y-1,Fx-1,y-1,Fx-2,y-1}+Numx,y，
其中Numx,y 表示(x,y) 点上的数字。
边界条件为：
动态规划与递推的关系
上题实质上是采用动态规划来求解,那么与递推动态规划之间到底是什么关系呢？
我们不妨画个图(如下图)。而通常人们理解的递推关系就是一般递推关系，故认为动态规划与递推关系是两个各自独立的个体。
1、一般递推边界条件很明显,动态规划边界条件比较隐蔽,容易被忽视
2、一般递推数学性较强,动态规划数学性相对较弱
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时，绘出走法图
（图2）共有7种不同的走法，也就是绿色线条的数量，即f(2)=7
（3）当N=3时，绘出走法图
（图3）共有17种不同的走法，也就是红色线条的数量，即f(3)=17
此，我们不难看出，对于任何一个起点，最多可以走出3种走法，但最少必须走出2种走法。那么我们要求出f(n)，实际上转换为如果我们能够得到上一步即f（n-1）有多少个终点是有3种走法的，有多少个点有2种走法的，那么问题就解决了。
a. 上一步，即f（n-1）有多少个终点是有3种走法的。
对于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种走法的
对于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>
#include <windows.h>
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;
}