问答文章1 问答文章501 问答文章1001 问答文章1501 问答文章2001 问答文章2501 问答文章3001 问答文章3501 问答文章4001 问答文章4501 问答文章5001 问答文章5501 问答文章6001 问答文章6501 问答文章7001 问答文章7501 问答文章8001 问答文章8501 问答文章9001 问答文章9501
你好,欢迎来到懂视!登录注册
当前位置: 首页 - 正文

程序的递归算法与非递归的区别

发布网友 发布时间:2022-05-04 21:24

我来回答

3个回答

热心网友 时间:2022-06-26 00:29

1、递归和非递归(用栈) 非递归(用栈),也用到栈函数了,和递归就没多大区别了! 每次递归进栈出栈,非递归(用栈)的每次调用栈函数也是进栈出栈。主要是在非递归(用栈)中,它的栈函数里比递归多了些赋值语句。。。所以效率上,非递归(用栈)比递归差。 只不过,递归越深,占用栈空间越多。非递归(用栈),占用的栈空间少。如果,递归的深度还没达到超出栈空间的程度,那么递归比非递归(用栈)好。 如果是非递归(不用栈),当然是非递归最好。 在下面的这个例子(解决“整数划分问题”)中,说明了如果只是用栈机械的模拟,得到的结果只是: 空间不变(事实上,非递归应该多一些),而非递归的时间数倍的增加。。 感兴趣的朋友运行就知道了 #include<iostream> #include<stack> #include<ctime> using namespace std; //---------------------------递归算法 int q(int n,int m) { if((n<1) || (m<0)) return 0; if((n==1) ||(m==1)) return 1; if(n<m) return q(n,n); if(n==m) return q(n,m-1)+1; return q(n,m-1)+q(n-m,m); } int q(int num) { return q(num,num); } struct Point { int n,m; Point(int _n,int _m){ n=_n; m=_m;} }; //-------------------------非递归算法 int _q(int n,int m) { int sum=0; Point tmp(n,m); stack<Point> s; s.push (tmp); while(!s.empty()) { tmp=s.top(); n=tmp.n; m=tmp.m; s.pop(); if((n<1) || (m<0)) ++sum; else if((n==1) ||(m==1)) ++sum; else if(n<m) s.push(Point(n,n)); else if(n==m) { ++sum; s.push(Point(n,m-1)); } else { s.push(Point(n,m-1)); s.push(Point(n-m,m)); } } return sum; } int _q(int num) { return _q(num,num); } int main() { int num; unsigned int p; do{ cout<<"Input a num:"; cin>>num; p=clock(); cout<<" 递归: "<<q(num)<<endl; cout<<"\t\t用时:"<<clock()-p<<endl; p=clock(); cout<<"非递归: "<<_q(num)<<endl; cout<<"\t\t用时:"<<clock()-p<<endl<<endl; }while(num); return 0; } 2. 如果非递归不是用栈做的 这里有一个网友做的汉诺塔问题的非递归解法 看了真让人汗颜 这样的规律都有人发现 下载地址是: http://wenku.baidu.com/view/cfd56b3610661ed9ad51f3f9.html 此算法不是用大家以前熟悉的递归算法 虽然没运行 可以猜想 这个程序的空间和时间效率毫无疑问会大幅度提高。 3. 总结: 直接引用《算法设计与分析(第二版)》里的一段话: 结构清晰,可读性强,而且容易用数学归纳法来证明算法的正确性,而且它为设计算法,调试程序带来很大方便。 然而递归算法的运行效率较低,无论是耗费的计算时间还是占用的存储空间都比非递归算法要多 仅仅是机械地模拟还不能达到减少计算时间和存储空间的目的。因此,还需要根据具体程序和特点对递归调用的工作栈进行简化,尽量减少栈的操作,压缩栈存储以达到节省计算时间和存储空间的目的。

热心网友 时间:2022-06-26 00:29

递归算法是一种直接或者间接地调用自身的算法。

在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解。

递归就是在过程或函数里调用自身。  

在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。

递归算法解题通常显得很简洁,但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。

在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出。

热心网友 时间:2022-06-26 00:30

以下是比较全面的解释,可以看看。 递归算法是一种直接或者间接地调用自身的算法。在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解。   递归算法解决问题的特点:   (1) 递归就是在过程或函数里调用自身。   (2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。   (3) 递归算法解题通常显得很简洁,但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。   (4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。
声明:本网页内容为用户发布,旨在传播知识,不代表本网认同其观点,若有侵权等问题请及时与本网联系,我们将在第一时间删除处理。
E-MAIL:11247931@qq.com
貔貅请多少只 生活的滋味 写写你的生活实际 这个短文收到什么启发 阳光城并州府施工进度 狙击手幽灵战士契约2伪装所在地点位置分享介绍_狙击手幽灵战士契约2伪 ... 狙击手幽灵战士契约2弹药怎么搜集_狙击手幽灵战士契约2弹药怎么获得 《狙击手幽灵战士2》攻略图文详解(精准射击) 生产经营能力主要形式 每到节假日新华书店坐满了看书的人把坐满了看书的人写具体 三星4300提示墨粉用尽 如何将递归函数转化为非递归函数 递归与非递归 C语言中递归函数是,非递归函数是?能否举例子? Barclays Stockbrokers CFD&FST Trader怎么样 200分 帮忙人式翻译一段计算机英文文档 这个轴承可以满足你提出的条件 用英语怎么翻译 翻译句子 人工翻译谢谢 我想系统的学习证券投资知识 电影&lt;华尔街&gt;的观后感? (高分求助)排列组合 之 篮球红球问题 为什么jsp代码onsubmit=“return check()”报错 技术分析实战工具的作者简介 急,Strangle在金融里是什么意思? 怎样识别手机数据线的型号,在哪儿可以买到适合自己手机的数据线? 怎么知道自己的USB数据线型号 求梁永琪的一首歌的歌名?;歌词有句是&#92;&#39;好想快点张大,不用看童话&#92;&quot;整首个有点童谣的感觉 我不不怕不怕我要快快长大是那首歌的歌词 小松树歌词 我想找一首歌,词里是这样唱的&quot;嗡嗡嗡蜜蜂在采蜜,爱爸爸,爱妈妈,我要快快长大 歌曲快快长大,是一首电视片插曲,歌词是:儿时的摇篮摇着那闪闪的煤油灯花,那灯下的妈妈为我逢着那布娃娃 如何实现递归函数改写成非递归函数 将c++递归函数改为非递归函数 将递归函数化为非递归函数~ 递归与非递归两种函数程序设计好难做 请将下列递归函数变为非递归函数! 每一个递归版的函数都能写成一个非递归版的函数吗? 用非递归的函数调用形式求斐波那契数列第n项 画红线区域内为什么说递归函数象非递归函数那样保存信息会出错 求教,C语言非递归函数求斐波那契数列 读下列程序 说出程序的功能;将其改写为传递引用参数,将findmax()函数改写成非递归函数 C++ 先序中序后序层序 非递归函数 谁能帮我解释一下 编写非递归函数int Fibonacci(int n),返回斐波那契数列的第n项.C++!今早出答案给20分!!! 中国到底有没有修真者? 中国真的有修真者吗 现在中国到底有没有修真的人?还存不存在门派?一般怎么才有机会加入? 中国的修真者、古武者真的存在吗? 中国真的有修真者吗? 龙江健康码有过红码恢复后对以后会有影响吗 古时候的中国人修真是否确有其事?有没有历史记载? 古武修炼者存在吗
  • 焦点

最新推荐

猜你喜欢

热门推荐