搜索

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

gecimao 发表于 2019-08-14 01:10 | 查看: | 回复:

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

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

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

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

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

  以下是比较全面的解释,可以看看。 递归算法是一种直接或者间接地调用自身的算法。在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解。 递归算法解决问题的特点: (1) 递归就是在过程或函数里调用自身。 (2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。 (3) 递归算法解题通常显得很简洁,但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。 (4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。

本文链接:http://windsorflowers.net/diguilicheng/439.html
随机为您推荐歌词

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部