递推算法
‘壹’ 递推算法是什么
递推算法是一种用若干步可重复运算来描述复杂问题的方法。递推是序列计算中的一种常用算法。通常是通过计算机前面的一些项来得出序列中的指定项的值。
递推是按照一定的规律来计算序列中的每个项，通常是通过计算前面的一些项来得出序列中的指定项的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。
‘贰’ 递推和递归算法有什么区别
举个例子,数列:1,1,2,3,5,8,13,21,……
要求第100项,就得从前两项开始推,直到第100项,是一个递推的过程
f[0]=f[1]=1;
for(i=2;i<101;i++)
{
f[i]=f[i-1]+f[i-2];
}
如果已知:f(n)=f(n-1)+f(n-2),f(0)=f(1)=1;
求f(n)就可以写一个函数:
int f(int n)
{
if(n==0||n==1)
return 1;
else
return f[n-1]+f[n-2];
}
这个就是回溯,因为比较简单,所以其实也可以用递推来实现
‘叁’ 数列递推算法的原理
什么是递推
所谓递推，是指从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简后确定。
从已知条件出发逐步推到问题结果，此种方法叫顺推。
从问题出发逐步推到已知条件，此种方法叫逆推。
无论顺推还是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。
递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用于数值计算的一个重要算法。
递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了求通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说来，可以将递推算法看成是一种特殊的迭代算法。
递推的特点
可用递推算法求解的题目一般有以下两个特点：
1、问题可以划分成多个状态；
2、除初始状态外，其它各个状态都可以用固定的递推关系式来表示。
在我们实际解题中，题目不会直接给出递推关系式，而是需要通过分析各种状态，找出递推关系式。
【例1】数字三角形。
如下所示为一个数字三角形。请编一个程序计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。只要求输出总和。
1、 一步可沿左斜线向下或右斜线向下走；
2、 三角形行数小于等于100；
3、 三角形中的数字为0，1，…，99；
测试数据通过键盘逐行输入，如上例数据应以如下所示格式输入：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
【算法分析】
此题解法有多种，从递推的思想出发，设想，当从顶层沿某条路径走到第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>
using namespace std;
int main(){
int n,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]; //路径选择
else a[i][j]+=a[i+1][j+1];
}
cout<<a[1][1]<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
思考
如果要输出最大和的路径该怎么处理呢？
【例2】 骨牌问题
有2 × n的一个长方形方格，用一个1 × 2的骨牌铺满方格。
编写一个程序，试对给出的任意一个n(n>0), 输出铺法总数。
【算法分析】
（1）面对上述问题，如果思考方法不恰当，要想获得问题的解答是相当困难的。可以用递推方法归纳出问题解的一般规律。
（2）当n=1时，只能是一种铺法，铺法总数有示为x1=1。
（3）当n=2时：骨牌可以两个并列竖排，也可以并列横排，再无其他方法，如下左图所示，因此，铺法总数表示为x2=2；
（4）当n=3时：骨牌可以全部竖排，也可以认为在方格中已经有一个竖排骨牌，则需要在方格中排列两个横排骨牌（无重复方法），若已经在方格中排列两个横排骨牌，则必须在方格中排列一个竖排骨牌。如上右图，再无其他排列方法，因此铺法总数表示为x3=3。
由此可以看出，当n=3时的排列骨牌的方法数是n=1和n=2排列方法数的和
‘肆’ 什么是递推法和递归法两者在思想上有何联系
1、递推法：递推算法是一种根据递推关系进行问题求解的方法。通过已知条件，利用特定的递推关系可以得出中间推论，直至得到问题的最终结果。递推算法分为顺推法和逆推法两种。
2、递归法：在计算机编程中，一个函数在定义或说明中直接或间接调用自身的编程技巧称为递归。通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归做为一种算法在程序设计语言中广泛应用。
3、两者的联系：在问题求解思想上，递推是从已知条件出发，一步步的递推出未知项，直到问题的解。从思想上讲，递归也是递推的一种，只不过它是对待解问题的递推，直到把一个复杂的问题递推为简单的易解问题。然后再一步步的返回去，从而得到原问题的解。
(4)递推算法扩展阅读
相对于递归算法,递推算法免除了数据进出栈的过程，也就是说,不需要函数不断的向边界值靠拢,而直接从边界出发,直到求出函数值。
比如阶乘函数：f(n)=n*f(n-1)
在f(3)的运算过程中,递归的数据流动过程如下: f(3){f(i)=f(i-1)*i}-->f(2)-->f(1)-->f(0){f(0)=1}-->f(1)-->f(2)--f(3){f(3)=6}
而递推如下: f(0)-->f(1)-->f(2)-->f(3) 由此可见,递推的效率要高一些,在可能的情况下应尽量使用递推。
但是递归作为比较基础的算法,它的作用不能忽视。所以,在把握这两种算法的时候应该特别注意。
‘伍’ 递推算法是怎么回事
递推定义
递推算法是一种简单的算法，即通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。
递推算法分为顺推和逆推两种。
顺推法
所谓顺推法是从已知条件出发，逐步推算出要解决的问题的方法叫顺推。
如斐波拉契数列，设它的函数为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……直至我们要求的解。
逆推法
所谓逆推法从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件，即顺推法的逆过程，称为逆推。
递推与递归的比较
相对于递归算法,递推算法免除了数据进出栈的过程，也就是说,不需要函数不断的向边界值靠拢,而直接从边界出发,直到求出函数值.
比如阶乘函数：f(n)=n*f(n-1)
在f(3)的运算过程中,递归的数据流动过程如下:
f(3){f(i)=f(i-1)*i}-->f(2)-->f(1)-->f(0){f(0)=1}-->f(1)-->f(2)--f(3){f(3)=6}
而递推如下:
f(0)-->f(1)-->f(2)-->f(3)
由此可见,递推的效率要高一些,在可能的情况下应尽量使用递推.但是递归作为比较基础的算法,它的作用不能忽视.所以,在把握这两种算法的时候应该特别注意.
‘陆’ 用递推算法求10！
Python版递归算法
def factorial（n）
if n<=0：
return error
else if n==1：
return 1
else ：
return n*factorial（n-1）
‘柒’ 递推估计算法的概述
递推估计算法recursive estimation algorithm
利用时刻t上的参数估计、存储向量与时刻 t+1上测量的输入和输出值u(t+1)和y(t+1)计算新参数值(t+1),再根据(t+1)计算出新参数值(t+2)，直到获得满意的参数值为止。这种算法的每一步计算量都比较小，能够使用小型计算机进行离线或在线参数估计，可以估计时变参数，也可以实时估计适应控制器的参数（见适应控制系统）。20世纪60年代，递推估计算法得到迅速发展，到了70年代产生了许多不同的方法，例如，有离线方法的各种变形、卡尔曼滤波法、随机逼近方法和模型参考适应参数递推估计法等。
递推估计算法的各种方法可以用一个统一的公式来描述：
‘捌’ 如何用递推算法写出计算N!的函数
N>1时：N!=N*(N-1)!
N=1时：N!=1
‘玖’ 想问什么是递推法
递推算法是一种用若干步可重复运算来描述复杂问题的方法。
递推是序列计算中的一种常用算法。通常是通过计算前面的一些项来得出序列中的指定项的值。
递推是按照一定的规律来计算序列中的每个项，通常是通过计算前面的一些项来得出序列中的指定项的值。
其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。
分类：递推算法分为顺推和逆推两种。
递推与递归的比较：
相对于递归算法,递推算法免除了数据进出栈的过程，也就是说,不需要函数不断的向边界值靠拢,而直接从边界出发,直到求出函数值。
所谓顺推法是从已知条件出发，逐步推算出要解决的问题的方法叫顺推。
以上内容参考网络-递推算法
‘拾’ 递推的递推算法
【例1】
植树节那天，有五位同学参加了植树活动，他们完成植树的棵树都不相同。问第一位同学植了多少棵时，他指着旁边的第二位同学说比他多植了两棵；追问第二位同学，他又说比第三位同学多植了两棵；... 如此，都说比另一位同学多植两棵。最后问到第五位同学时，他说自己植了10棵。到底第一位同学植了多少棵树？
分析：设第一位同学植树的棵树为a1,欲求a1，需从第五位同学植树的棵数a5入手，根据“多两棵”这个规律，按照一定顺序逐步进行推算：
(1) a5=10;
(2) a4=a5+2=12;
(3) a3=a4+2=14;
(4) a2=a3+2=16;
(5) a1=a2+2=18;
Pascal程序：
Program Examl;
Var i,a:byte;
begin
a:=10;
for i:= 1 to 4 do
a:=a+2;
writeln('The Num is' ,a);
readln;
end.
本程序的递推运算可用下图示表示：
初始值a:=10 ----- i=1,a=a+2(12) ----- i=2,a=a+2(14) ------ i=3,a=a+2(16) ----- i=4,a=a+2(18) ---- 输出a值
例2：
十本不同的书放在书架上。现重新摆放，使每本书都不在原来放的位置。有几种摆法？
当n个编号元素放在n个编号位置,元素编号与位置编号各不对应的方法数用M(n)表示,那么M(n-1)就表示n-1个编号元素放在n-1个编号位置,各不对应的方法数,其它类推.
第一步,把第n个元素放在一个位置,比如位置k,一共有n-1种方法;
第二步,放编号为k的元素,这时有两种情况.1,把它放到位置n,那么,对于剩下的n-2个元素,就有M(n-2)种方法;2,不把它放到位置n,这时,对于这n-1个元素,有M(n-1)种方法;
综上得到
M(n)=(n-1)[M(n-2)+M(n-1)]
递推算法以初始（起点）值为基础，用相同的运算规律，逐次重复运算，直至运算结束。这种从“起点”重复相同的方法直至到达一定“边界”，犹如单向运动，用循环可以实现。递推的本质是按规律逐次推出（计算）先一步的结果。