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

1、递推法：递推算法是一种根据递推关系进行问题求解的方法。通过已知条件，利用特定的递推关系可以得出中间推论，直至得到问题的最终结果。递推算法分为顺推法和逆推法两种。 

2、递归法：在计算机编程中，一个函数在定义或说明中直接或间接调用自身的编程技巧称为递归。通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归做为一种算法在程序设计语言中广泛应用。 

3、两者的联系：在问题求解思想上，递推是从已知条件出发，一步步的递推出未知项，直到问题的解。从思想上讲，递归也是递推的一种，只不过它是对待解问题的递推，直到把一个复杂的问题递推为简单的易解问题。然后再一步步的返回去，从而得到原问题的解。 

扩展资料

相对于递归算法,递推算法免除了数据进出栈的过程，也就是说,不需要函数不断的向边界值靠拢,而直接从边界出发,直到求出函数值。

比如阶乘函数：f(n)=nf(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）递归模式：大问题是如何分解为小问题的，也称为递归体。递归函数只有具备了这两个要素，才能在有限次计算后得出结果 

在递归函数中，调用函数和被调用函数是同一个函数，需要注意的是递归函数的调用层次，如果把调用递归函数的主函数称为第0层，进入函数后，首次递归调用自身称为第1层调用；从第i层递归调用自身称为第i+1层。反之，退出第i+1层调用应该返回第i层。

一个递归函数的调用过程类似于多个函数的嵌套的调用，只不过调用函数和被调用函数是同一个函数。为了保证递归函数的正确执行，系统需设立一个工作栈。具体地说，递归调用的内部执行过程如下：

（1）运动开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址；

（2）每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈；

（3）每次递归调用结束后，将栈顶元

扩展资料：

递归就是某个函数直接或间接地调用了自身，这种调用方式叫做递归调用。说白了，还是函数调用。既然是函数调用，那么就有一个雷打不动的原则：所有被调用的函数都将创建一个副本，各自为调用者服务，而不受其他函数的影响。

你的ff函数，递归多少次，就有多少个副本，再利用内存的栈式管理，反向退出。这个最好找一下“栈”这方面的东西看看，挺容易的，就像子弹匣一样，先进后出。

从某种意义上说，这是不对的，因为就像刚才说的，一旦被调用，他将在内存中复制出一份代码，再被调用就再复制一份，换句话说，你可以吧同一个函数的多次调用理解称谓多个不同函数的一次调用，这样也会会简单些。

再说=1和=0是为什么退出。递归，很需要注意的就是死递归，也就是说，某一个函数进入了无限调用自身的情况，永无止境地消耗内存等资源，这在编程方面是一大忌。

但凡是递归的函数，一定会在某一个地方存在能够返回上一层函数的代码，否则必定死递归。ff函数中，那个else就是返回的出口，你可以这样想，如果没有那个if来进行判断，你递归到什么时候算完？ff是不是会一直调用自己。

因为一旦某个函数A中调用了函数B（或者自己），那么A中的代码会停在调用的位置，而转向B中去执行，同理，如果B又调用函数C，那么B又停在调用的位置，去执行C，如果无限调用，那么程序是永远不会结束的。

当然，也有这种情况，A调用B，然后继续自己的代码，不管B的死活，这种不在我们的讨论范围内，因为那牵扯到另一种编程方式：多线程。

参考资料：

——递归函数

问题一：什么是递推法和递归法两者在思想有何联系 程序调用自身的编程技巧称为递归。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

递推算法是一种用若干步可重复的简运算（规律）来描述复杂问题的方法。递推是序列计算机中的一种常用算法。它是按照一定的规律来计算序列中的每个项，通常是通过计算机前面的一些项来得出序列中的指定象的值。

迭代是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会作为下一次迭代的初始值。

问题二：递推和递归算法有什么区别 递归指自我调用的函数，自己调用自己；递推指重复进行的过程，重复进行一个过程，

问题三：的递推和递归方法的区别是什么 递归就是自己调用自己吧！

递推是从头向后推吧！

问题四：递推和递归算法有什么区别 递归就是自己调用自己吧！

递推是从头向后推吧！

问题五：递推和递归的区别是什么 1递归：将问题规模为n的问题，降解成若干个规模为n-1的问题，依次降解，直到问题规模可求，求出低阶规模的解，代入高阶问题中，直至求出规模为n的问题的解。

2递推：构造低阶的规模(如规模为i，一般i=0)的问题，并求出解，推导出问题规模为i+1的问题以及解，依次推到规模为n的问题。

3递归包括回溯和递推两个过程。

最好的例子是斐波那契数列: 1 1 2 3 5 8 13 21

总结成公式就是F(n+1)=F(n)+F(n-1), F(0)=F(1)=1;

你可以用递归的方法写这个函数:

int F(int n) {

if (n 问题六：递推算法和递归算法有什么区别 递推就是从前往后推,递归还有个回溯的过程

举个例子,数列:1,1,2,3,5,8,13,21,……

要求第100项,就得从前两项开始推,直到第100项,是一个递推的过程

f[0]=f[1]=1;

for(i=2;i 问题七：递推法和递归法两者在思想有何联系 两者是一样的，没有本质区别。

问题八：递推算法的递推与递归的比较 相对于递归算法,递推算法免除了数据进出栈的过程，也就是说,不需要函数不断的向边界值靠拢,而直接从边界出发,直到求出函数值比如阶乘函数：f(n)=nf(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……直至我们要求的解。 所谓逆推法从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件，即顺推法的逆过程，称为逆推。

问题九：什么是递归算法 递归算法就是一个函数通过不断对自己的调用而求得最终结果的一种思维巧妙但是开销很大的算法。

比如：

汉诺塔的递归算法：

void move(char x,char y){

printf(%c-->%c\n,x,y);

}

void hanoi(int n,char one,char two,char three){

/将n个盘从one座借助two座，移到three座/

if(n==1) move(one,three);

else{

hanoi(n-1,one,three,two);

move(one,three);

hanoi(n-1,two,one,three);

}

}

main(){

int n;

printf(input the number of diskes:);

scanf(%d,&n);

printf(The step to moving %3d diskes:\n,n);

hanoi(n,'A','B','C');

}

我说下递归的理解方法

首先：对于递归这一类函数，你不要纠结于他是干什么的，只要知道他的一个模糊功能是什么就行，等于把他想象成一个能实现某项功能的黑盒子，而不去管它的内部操作先，好，我们来看下汉诺塔是怎么样解决的

首先按我上面说的把递归函数想象成某个功能的黑盒子，void hanoi(int n,char one,char two,char three); 这个递归函数的功能是：能将n个由小到大放置的小长方形从one 位置，经过two位置 移动到three位置。那么你的主程序要解决的问题是要将m个的汉诺块由A借助B移动到C，根据我们上面说的汉诺塔的功能，我相信傻子也知道在主函数中写道：hanoi(m,A,B,C)就能实现将m个块由A借助B码放到C，对吧？所以，mian函数里面有hanoi(m,'A','C','B');这个调用。

接下来我们看看要实现hannoi的这个功能，hannoi函数应该干些什么？

在hannoi函数里有这么三行

hanoi(n-1,one,three,two);

move(one,three);

hanoi(n-1,two,one,three);

同样以黑盒子的思想看待他，要想把n个块由A经过B搬到C去，是不是可以分为上面三步呢？

这三部是：第一步将除了最后最长的那一块以外的n-1块由one位置经由three搬到two 也就是从A由C搬到B 然后把最下面最长那一块用move函数把他从A直接搬到C 完事后 第三步再次将刚刚的n-1块借助hanno处函数的功能从B由A搬回到C 这样的三步实习了n块由A经过B到C这样一个功能，同样你不用纠结于hanoi函数到底如何实现这个功能的，只要知道他有这么一个神奇的功能就行

最后：递归都有收尾的时候对吧，收尾就是当只有一块的时候汉诺塔怎么个玩法呢？很简单吧，直接把那一块有Amove到C我们就完成了，所以hanoni这个函数最后还要加上 if(n==1)move(one,three);（当只有一块时，直接有Amove到C位置就行）这么一个条件就能实现hanoin函数n>=1时>>

问题十：递归和递推有什么不一样。用起来哪个快一些？？ 递推就是递推循环，递推或者说循环比递归更容易理解和运用，但递归算法在运行速度上更快，代码也比较简洁。递归算法也有缺点，主要是空间消耗比较大。从数学上说，所有的递归算法都可以用递推（循环）算法代替，但不是所有的循环算法都可以被递归代替。

1、贪心算法主要是把问题分成很多局部问题，用局部最优解合成整体最优解。因此使用这种算法需要此问题满足两个条件，一个是能够分成多个能够求解的局部问题，第二个就是局部问题的解能够合成最优解。和动态规划、回溯等相比差别就是再不回溯的前提下找出整体最优解或者接近最优解，速度快但应用有比较大的限制。

2、迭代也叫递推，通过重复执行某一步骤或者函数来求得计算结果

递归是指函数中直接或者间接调用自身

举例：

求a乘以2的10次方等于几

迭代：

for (i=0;i<10;i++)

a = 2;

递归：

int db(int a,int num)

{

if (num<10)

return 2 db(a,num+1);

else

return 1;

}

db(a,0);

3、回溯的含义就是在搜索问题的状态过程中，如果不能继续前进，再向后回到岔口，换一条路继续搜索，直到搜索完所有状态或者查找到需要的状态。

举例：（最典型的就是树的深度搜索，下面举一个简单的例子）

int a[10]={5,3,7,9,3,2,5,6,9,1};//从3开始查找1

int read[10]=(0);//是否查找过

int readNum = 0;//查找过的个数

int forward = 1;//1为左，2为右

int tmp = 0,index = 5;

tmp = a[index];

read[index] = 1;

readNum++;

while (tmp != 1 || readNum != 10)

{

if (forward == 1)

index --;

else

index++;

if (!read[index])

{

tmp = a[index];

read[index] = 1;

readNum++;

}

if (index <=0 || index>=9)

forward = 3 - forward;

}

所谓递推关系，通常是指一个数列 》的第 项a与前面k个项a ,a … a n n n =n2 n k

(k为正整数，kn)之间的关系：

an =f(an 1, an_2;",an_k) (n>k)

这里，f是关于a，an 2 ank的k元函数，通常称为递归函数；递推关系，也常称为k阶递归方程

关键字：递推法，组合数，列举累乘法，列举累加法，列举归纳猜想法，不动点法和换元法

递推法的应用及证明步骤

递推法也常用以处理正整数为状态函数的数学问题，诸如递归数列的通项问题，与数列有关的计算问题，证明问题，等等，应用递推法解答数学问题，一般包括两个步骤：

第一步：建立递推关系，根据问题的特点，通过观察，试验，归纳，猜想等思维活动，寻求递推关系

第二步：求递推关系初始值和相应的递推关系，求得所需的结论

例1：计算两类带组合数 C和Ck的器和Shd=ZCAkm，Un(n)=Z Cnkm

我想你要说的是递归和循环（从程序执行角度，递推比较侧重逻辑推理）。递归可以看作一个逆向求解的过程，循环则可以看作一个正向求解的过程。

unsigned long

fac0(int n)

{

return (n == 0 1 : n fac0(n-1));

}

unsigned long

fac1(int n)

{

int i;

unsigned long r;

for (r = 1, i = 1; i <= n; ++i)

r = i;

return r;

}

fac0是用递归定义的，fac1是用循环定义的。两者字面上的区别就是，递归定义的函数体里面必然要自调用（在fac0的定义里面我们调用了fac0(n-1)），相反以循环定义的函数fac1里面却没有自调用。

递归与循环更深层次的区别则在执行的过程上。在一个没有提供尾调优化的编译器上，递归的执行效率比循环低很多，也就是说当输入很大时，循环实现将比递归实现更快地给出结果。为什么会这样呢？我们看一个计算fac0(3)和fac1(3)的比较：

fac0(3) = 3 调用fac0(3-1)，等待fac0(2)的返回值

fac0(2) = 2 调用fac0(2-1)，等待fac0(1)的返回值

fac0(1) = 1 调用fac0(1-1)，等待fac0(0)的返回值

fac0(0) = 1 fac0(0)直接返回1

fac0(1) = 1 拿到fac(0)的返回值1，算出11返回1

fac0(2) = 2 拿到fac0(1)的返回值1，算出21返回2

fac0(3) = 6 拿到fac0(2)的返回值2，算出32返回6

所以你看到递归实现会有一串调用返回的过程，正是这一频繁调用返回的过程将耗去很多的时间，而且伴有等待，这一等待也是有开销的，因为一般函数的调用和返回在底层是通过调用栈（call stack）实现的，当一个函数调用另一个函数时，调用函数要先把自己的当前状态保存到调用栈，然后跳到被调用函数体里面执行，等到那里执行完后，被调用函数返回，之前的调用函数才又从调用栈恢复。所以一条函数调用链越长，意味着将有越多的中间状态被保存到调用栈，如果输入很大，比如fac0(100)，就会生成一条很长的调用链fac0(100) --> fac0(99) --> --> fac0(0)，而调用栈的大小一般都有一个上限，这条调用链很可能还没有到达fac0(0)开始返回，中间需要保存的状态就已经超出这个上限了，于是就产生栈溢出（stack overflow）的错误。所以递归实现在空间效率上往往也表现糟糕。

相反，循环实现则没有上面提到的调用返回链的问题。所以在时间和空间效率上都略胜一筹。但是递归比循环适用范围广，也就是说有的算法用递归能实现，用循环却做不到（比如二叉树的遍历）。实际上，所有的循环都可以转化为一类特殊的递归，尾递归。而且，如果编译器能做尾调优化，那么用尾递归实现的算法在空间利用上则跟用循环实现持平。下面是阶乘用尾递归的实现：

unsigned long

fac2(int n, unsigned long r)

{

return (n == 0 r : fac2(n-1, nr));

}

计算的时候要写fac2(3, 1);。

递归一开始是比较抽象的，要慢慢理解。如果我上面有些概念你不太明白也没太大关系，往后你会明白的。