递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用于数值计算的一个重要算法。这种算法特点是：一个问题的求解需一系列的计算，在已知条件和所求问题之间总存在着某种相互联系的关系，在计算时，如果可以找到前后过程之间的数量关系（即递推式），那么，从问题出发逐步推到已知条件，此种方法叫逆推。无论顺推还是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了求通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说来，可以将递推算法看成是一种特殊的迭代算法。【例1】数字三角形。如下所示为一个数字三角形。请编一个程序计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。只要求输出总和。1、一步可沿左斜线向下或右斜线向下走；2、三角形行数小于等于100；3、三角形中的数字为0，1，…，99；测试数据通过键盘逐行输入，如上例数据应以如下所示格式输入：5738810274445265【算法分析】此题解法有多种，从递推的思想出发，设想，当从顶层沿某条路径走到第i层向第i+1层前进时，我们的选择一定是沿其下两条可行路径中最大数字的方向前进，为此，我们可以采用倒推的手法，设a[i][j]存放从i,j出发到达n层的最大值，则a[i][j]=max{a[i][j]+a[i+1][j]，a[i][j]+a[i+1][j+1]}，a[1][1]即为所求的数字总和的最大值。【参考程序】#include<iostream>usingnamespacestd;intmain(){intn,i,j,a[101][101];cin>>n;for(i=1;i<=n;i++)for(j=1;j<=i;j++)cin>>a[i][j];//输入数字三角形的值for(i=n-1;i>=1;i--)for(j=1;j<=i;j++){if(a[i+1][j]>=a[i+1][j+1])a[i][j]+=a[i+1][j];//路径选择elsea[i][j]+=a[i+1][j+1];}cout<<a[1][1]<<endl;}【例2】满足F1=F2=1，Fn=Fn-1+Fn-2的数列称为斐波那契数列（Fibonacci），它的前若干项是1，1，2，3，5，8，13，21，34……求此数列第n项（n>=3）。即：f1=1（n=1）f2=1（n=2）fn=fn-1+fn-2（n>=3）有关Fibonacci数列，我们先来考虑一个简单的问题：楼梯有n个台阶，上楼可以一步上一阶，也可以一步上两阶。一共有多少种上楼的方法？这是一道计数问题。在没有思路时，不妨试着找规律。n=5时，一共有8种方法：5=1+1+1+1+15=2+1+1+15=1+2+1+15=1+1+2+15=1+1+1+25=2+2+15=2+1+25=1+2+2其中有5种方法第1步走了1阶(背景灰色)，3种方法第1步走了2阶，没有其他可能。假设f(n)为n个台阶的走法总数，把n个台阶的走法分成两类。第1类：第1步走1阶，剩下还有n-1阶要走，有f(n-1)种方法。第2类：第1步走2阶，剩下还有n-2阶要走，有f(n-2)种方法。这样，就得到了递推式：f(n)=f(n-1)+f(n-2),不要忘记边界情况：f(1)=1,f(2)=2。把f(n)的前几项列出：1，2，3，5，8，……。再例如，把雌雄各一的一对新兔子放入养殖场中。每只雌兔在出生两个月以后，每月产雌雄各一的一对新兔子。试问第n个月后养殖场中共有多少对兔子。还是先找找规律。第1个月：一对新兔子r1。用小写字母表示新兔子。第2个月：还是一对新兔子，不过已经长大，具备生育能力了，用大写字母R1表示。第3个月：R1生了一对新兔子r2，一共2对。第4个月：R1又生一对新兔子r3，一共3对。另外，r2长大了，变成R2第5个月：R1和R2各生一对，记为r4和r5，共5对。此外，r3长成R3。第6个月：R1、R2和R3各生一对，记为r6～r8，共8对。此外，r4和r5长大。……把这些数排列起来：1，1，2，3，5，8，……，事实上，可以直接推导出来递推关系f(n)=f(n-1)+f(n-2):第n个月的兔子由两部分组成，一部分是上个月就有的老兔子f(n-1)，一部分是上个月出生的新兔子f(n-2)(第n-1个月时具有生育能力的兔子数就等于第n-2个月兔子总数)。根据加法原理，f(n)=f(n-1)+f(n-2)。【例3】有2χn的一个长方形方格，用一个1*2的骨牌铺满方格。（4）当n=3时：骨牌可以全部竖排，也可以认为在方格中已经有