什么是递推数据

❶ 递推算法和递归算法有什么区别

1、算法的过程不同

递推算法是一种简单的算法，即通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。

递归算法在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。

❷ 递归、递推、迭代分别是什么意思，有什么区别

<可以自由转载，但请注明以下内容，谢谢合作！>
<作者：Enoch Wang 引用自：http://chinawangquan.spaces.live.com>
所谓递归，简而言之就是应用程序自身调用自身，以实现层次数据结构的查询和访问。 递归的使用可以使代码更简洁清晰，可读性更好（对于初学者到不见得），但由于递归需要系统堆栈，所以空间消耗要比非递归代码要大很多，而且，如果递归深度太大，可能系统资源会不够用。
往往有这样的观点：能不用递归就不用递归，递归都可以用迭代来代替。
诚然，在理论上，递归和迭代在时间复杂度方面是等价的（在不考虑函数调用开销和函数调用产生的堆栈开销），但实际上递归确实效率比迭代低，既然这样，递归没有任何优势，那么是不是就，没有使用递归的必要了，那递归的存在有何意义呢？
万物的存在是需要时间的检验的，递归没有被历史所埋没，即有存在的理由。从理论上说，所有的递归函数都可以转换为迭代函数，反之亦然，然而代价通常都是比较高的。但从算法结构来说，递归声明的结构并不总能够转换为迭代结构，原因在于结构的引申本身属于递归的概念，用迭代的方法在设计初期根本无法实现，这就像动多态的东西并不总是可以用静多态的方法实现一样。这也是为什么在结构设计时，通常采用递归的方式而不是采用迭代的方式的原因，一个极典型的例子类似于链表，使用递归定义及其简单，但对于内存定义(数组方式)其定义及调用处理说明就变得很晦涩，尤其是在遇到环链、图、网格等问题时，使用迭代方式从描述到实现上都变得不现实。 因而可以从实际上说，所有的迭代可以转换为递归，但递归不一定可以转换为迭代。
采用递归算法需要的前提条件是，当且仅当一个存在预期的收敛时，才可采用递归算法，否则，就不能使用递归算法。
递归其实是方便了程序员难为了机器，递归可以通过数学公式很方便的转换为程序。其优点就是易理解，容易编程。但递归是用栈机制实现的，每深入一层，都要占去一块栈数据区域，对嵌套层数深的一些算法，递归会力不从心，空间上会以内存崩溃而告终，而且递归也带来了大量的函数调用，这也有许多额外的时间开销。所以在深度大时，它的时空性就不好了。
而迭代虽然效率高，运行时间只因循环次数增加而增加，没什么额外开销，空间上也没有什么增加，但缺点就是不容易理解，编写复杂问题时困难。
因而，“能不用递归就不用递归，递归都可以用迭代来代替”这样的理解，Enoch不敢苟同，还是辩证的来看待，不可一棍子打死。

❸ 递推算法是怎么回事

递推定义
递推算法是一种简单的算法，即通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。

递推算法分为顺推和逆推两种。

顺推法
所谓顺推法是从已知条件出发，逐步推算出要解决的问题的方法叫顺推。

如斐波拉契数列，设它的函数为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)

由此可见,递推的效率要高一些,在可能的情况下应尽量使用递推.但是递归作为比较基础的算法,它的作用不能忽视.所以,在把握这两种算法的时候应该特别注意.

❹ 什么是递推法和递归法两者在思想上有何联系

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)   由此可见,递推的效率要高一些,在可能的情况下应尽量使用递推。

但是递归作为比较基础的算法,它的作用不能忽视。所以,在把握这两种算法的时候应该特别注意。

❺ 什么是递推，有没有通俗的解释

递推算法是一种用若干步可重复的简运算（规律）来描述复杂问题的方法.
递推是序列计算机中的一种常用算法。它是按照一定的规律来计算序列中的每个项，通常是通过计算机前面的一些项来得出序列中的指定象的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。

❻ 什么叫一阶线性递推数列

以下所有的n，n+1，n-1均是指下标
一阶线性递推是指x(n+1)=f(xn)，其中
f
是一个线性函数，比如
x(n+1)=axn+b
二阶线性是指x(n+1)=f(xn)+g(x(n-1))，其中f和g都是线性函数。
k阶的意思就是等式右端涉及到数列的k层数据，k是数列的层数
线性是指
所有的变量都是一次的。

❼ 数列递推算法的原理

什么是递推
所谓递推，是指从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简后确定。
从已知条件出发逐步推到问题结果，此种方法叫顺推。
从问题出发逐步推到已知条件，此种方法叫逆推。
无论顺推还是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。
递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用于数值计算的一个重要算法。
递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了求通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说来，可以将递推算法看成是一种特殊的迭代算法。

递推的特点
可用递推算法求解的题目一般有以下两个特点：
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排列方法数的和

❽ 一阶、二阶线性递推数列是什么内容

一阶线性递推是指x(n+1)=f(xn)，其中 f 是一个线性函数，比如 x(n+1)=axn+b
二阶线性是指x(n+1)=f(xn)+g(x(n-1))，其中f和g都是线性函数。

k阶的意思就是等式右端涉及到数列的k层数据，k是数列的层数
线性是指 所有的变量都是一次的。

如果本题有什么不明白的可以追问，如果满意请点击右上角的好评并“采纳为最佳答案”
如果有其他问题，可以点击我的头像向我求助，答题不易，请谅解。您的支持是我前进的动力，祝学习进步。

❾ c语言递推求解释

如题，输入的参数是7，调用fun（7），进入fun函数，if判断，此时x=7，if语句的condition为真，继续调用fun函数fun（3）（7/2取整为3），进入fun函数，if判断，此时x=3，if语句的condition为假，执行if语句后的输出语句，输出3（此时x=3），返回上一层的fun函数调用（即是fun（7），因为第一次调用时，还留这一句输出语句没有执行），输出7（此次fun函数调用x=7），主函数结束。函数执行的解析：程序的执行从主函数开始，一条一条语句执行，语句存放在一定的数据空间里，这段空间就是代码段，一般情况下程序是按代码的地址顺序执行的，但是在函数调用，程序会暂停当前的代码的执行，把下一条应该执行的代码的地址放在另一个存储空间里（其实是压进栈了），而转去执行调用的函数代码，执行完所有函数应该被执行代码（是所有哦，当然分支语句里的一些语句可以不执行的），程序会把压进栈的指令地址取出来，继续执行下去，直到住程序结束。递归函数是一般函数用分支或者循环控制多次重复调用函数的情况。

❿ Pascal算法之回溯及递推详细介绍、

递归 递归是计算机科学的一个重要概念,递归的方法是程序设计中有效的方法,采用递归编写程序能是程序变得简洁和清晰.2.1 递归的概念
1.概念一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数).如:procere a; begin . . . a; . . .end;这种方式是直接调用.又如: procere b; procere c; begin begin . . . . . . c; b; . . . . . .end; end;这种方式是间接调用.例1计算n!可用递归公式如下: 1 当 n=0 时 fac(n)={n*fac(n-1) 当n>0时可编写程序如下:program fac2;varn:integer;function fac(n:integer):real;beginif n=0 then fac:=1 else fac:=n*fac(n-1)end;beginwrite('n=');readln(n);writeln('fac(',n,')=',fac(n):6:0);end.例2 楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法.设n阶台阶的走法数为f(n)显然有 1 n=1 f(n)={2 n=2 f(n-1)+f(n-2) n>2可编程序如下：program louti;var n:integer;function f(x:integer):integer;beginif x=1 then f:=1 elseif x=2 then f:=2 else f:=f(x-1)+f(x-2);end;beginwrite('n=');read(n);writeln('f(',n,')=',f(n))end.2.2 如何设计递归算法
1.确定递归公式2.确定边界(终了)条件练习:用递归的方法完成下列问题1.求数组中的最大数2.1+2+3+...+n3.求n个整数的积4.求n个整数的平均值5.求n个自然数的最大公约数与最小公倍数6.有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问n个月后共有多少对兔子?7.已知:数列1,1,2,4,7,13,24,44,...求数列的第 n项. 2.3典型例题例3 梵塔问题 如图:已知有三根针分别用1,2,3表示,在一号针中从小放n个盘子,现要求把所有的盘子 从1针全部移到3针,移动规则是:使用2针作为过度针,每次只移动一块盘子,且每根针上不能出现大盘压小盘.找出移动次数最小的方案. 程序如下:program fanta;varn:integer;procere move(n,a,b,c:integer);beginif n=1 then writeln(a,'--->',c)else beginmove(n-1,a,c,b);writeln(a,'--->',c);move(n-1,b,a,c);end;end;beginwrite('Enter n=');read(n);move(n,1,2,3);end.例4 快速排序快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束.程序如下:program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
a:arr;
i:integer;
procere quicksort(var b:arr; s,t:integer);
var i,j,x,t1:integer;
begin
i:=s;j:=t;x:=b[i];
repeat
while (b[j]>=x) and (j>i) do j:=j-1;
if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end;
while (b[i]<=x) and (i<j) do i:=i+1;
if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end
until i=j;
b[i]:=x;
i:=i+1;j:=j-1;
if s<j then quicksort(b,s,j);
if i<t then quicksort(b,i,t);
end;
begin
write('input data:');
for i:=1 to n do read(a[i]);
writeln;
quicksort(a,1,n);
write('output data:');
for i:=1 to n do write(a[i]:6);
writeln;
end.练习:1.计算ackerman函数值: n+1 m=0 ack(m,n)={ ack(m-1,1) m<>0 ,n=0 ack(m-1,ack(m,n-1)) m<>0,n<>0 求ack(5,4)
回溯 回溯是按照某种条件往前试探搜索,若前进中遭到失败,则回过头来另择通路继续搜索.3.1 回溯的设计 1.用栈保存好前进中的某些状态.2.制定好约束条件例1由键盘上输入任意n个符号;输出它的全排列.program hh;
const n=4;
var i,k:integer;
x:array[1..n] of integer;
st:string[n];
t:string[n];
procere input;
var i:integer;
begin
write('Enter string=');readln(st);
t:=st;
end;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if x[i]=x[k] then
begin place:=false; break end ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(t[x[i]]);
writeln;
end;
begin
input;
k:=1;x[k]:=0;
while k>0 do
begin
x[k]:=x[k]+1;
while (x[k]<=n) and (not place(k)) do x[k]:=x[k]+1;
if x[k]>n then k:=k-1
else if k=n then print
else begin k:=k+1;x[k]:=0 end
end ;
end.例2.n个皇后问题:program hh;
const n=8;
var i,j,k:integer;
x:array[1..n] of integer;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then
place:=false ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(x[i]:4);
writeln;
end;
begin
k:=1;x[k]:=0;
while k>0 do
begin
x[k]:=x[k]+1;
while (x[k]<=n) and (not place(k)) do x[k]:=x[k]+1;
if x[k]>n then k:=k-1
else if k=n then print
else begin k:=k+1;x[k]:=0 end
end ;end.回溯算法的公式如下:3.2 回溯算法的递归实现由于回溯算法用一栈数组实现的,用到栈一般可用递归实现。上述例1的递归方法实现如下：program hh;
const n=4;
var i,k:integer;
x:array[1..n] of integer;
st:string[n];
t:string[n];
procere input;
var i:integer;
begin
write('Enter string=');readln(st);
t:=st;
end;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if x[i]=x[k] then
begin place:=false; break end ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(t[x[i]]);
writeln;readln;
end;
procere try(k:integer);
var i :integer;
begin
if k=n+1 then begin print;exit end;
for i:=1 to n do
begin
x[k]:=i;
if place(k) then try(k+1)
end
end;
begin
input;
try(1);
end.例2：n皇后问题的递归算法如下：程序1：program hh;
const n=8;
var i,j,k:integer;
x:array[1..n] of integer;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then
place:=false ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(x[i]:4);
writeln;
end;
procere try(k:integer);
var i:integer;
begin
if k=n+1 then begin print; exit end;
for i:= 1 to n do
begin
x[k]:=i;
if place(k) then try(k+1);
end;
end ;
begin
try(1);
end.程序2：说明:当n=8 时有30条对角线分别用了l和r数组控制，用c数组控制列.当(i,j)点放好皇后后相应的对角线和列都为false.递归程序如下:program nhh;
const n=8;
var s,i:integer;
a:array[1..n] of byte;
c:array[1..n] of boolean;
l:array[1-n..n-1] of boolean;
r:array[2..2*n] of boolean;
procere output;
var i:integer;
begin
for i:=1 to n do write(a[i]:4);
inc(s);writeln(' total=',s);
end;
procere try(i:integer);
var j:integer;
begin
for j:=1 to n do
begin
if c[j] and l[i-j] and r[i+j] then
begin
a[i]:=j;c[j]:=false;l[i-j]:=false; r[i+j]:=false;
if i<n then try(i+1) else output;
c[j]:=true;l[i-j]:=true;r[i+j]:=true;
end;
end;
end;
begin
for i:=1 to n do c[i]:=true;
for i:=1-n to n-1 do l[i]:=true;
for i:=2 to 2*n do r[i]:=true;
s:=0;try(1);
writeln;
end.练习：1.找出所有从m个元素中选取n(n<=m)元素的组合。2.设有A,B,C,D,E 5人从事j1,j2,j3,j4,j5 5项工作每人只能从事一项,它们的效益表如下:求最佳安排,使效益最高.3.N个数中找出M个数(从键盘上输入正整数N,M后再输入N个正数),要求从N个数中找出若干个数,使它们的和为M,把满足条件的数组找出来,并统计组数.4.地图着色。如下图12个区域用4种颜色着色要求相邻的区域着不同的颜色5.将任意一正整数(1<n<100)分解成若干正整数的和. 如:4=1+1+1+1 =2+1+1 =2+2 =3+1.