递归与循环的优缺点.docVIP

递归与循环的优缺点（转载）?? 2011-08-24 17:49:40|??分类：  HYPERLINK /blog/ \l m=0t=1c=fks_084064080081082066082084094095085084081064086095080074083 \o 算法数据结构 算法数据结构 |??标签： |字号大中小?订阅 递归的话函数调用是有开销的，而且递归的次数受堆栈大小的限制。?以二叉树有哪些信誉好的足球投注网站为例：?bool search(btree* p, int v)?{?if (null == p)?return false;?if (v == p-v)?return true?else?{?if (v p-v)?return search(p-left, v);?else?return search(p-right, v);?}?}?如果这个二叉树很庞大，反复递归函数调用开销就很大，万一堆栈溢出怎么办？?现在我们用循环改写：?bool search(btree* p, int v)?{?while (p)?{?if (v == p-v)?return true;?else?{?if (v p-v)?p = p-left;?else?p = p-right;?}?}?return false;?} --------------------------------------------------------------------------------------------------------- 递归好处：代码更简洁清晰，可读性更好?递归可读性好这一点，对于初学者可能会反对。实际上递归的代码更清晰，但是从学习的角度要理解递归真正发生的什么，是如何调用的，调用层次和路线，调用堆栈中保存了什么，可能是不容易。但是不可否认递归的代码更简洁。一般来说，一个人可能很容易的写出前中后序的二叉树遍历的递归算法，要写出相应的非递归算法就比较考验水平了，恐怕至少一半的人搞不定。所以说递归代码更简洁明了。?递归坏处：由于递归需要系统堆栈，所以空间消耗要比非递归代码要大很多。而且，如果递归深度太大，可能系统撑不住。?楼上的有人说：?小的简单的用循环,太复杂了就递归吧,,免得循环看不懂?话虽然简单，其实非常有道理：对于小东西，能用循环干嘛要折腾？如果比较复杂，在系统撑的住的情况下，写递归有利于代码的维护（可读性好）?另：一般尾递归（即最后一句话进行递归）和单向递归（函数中只有一个递??调用地方）都可以用循环来避免递归，更复杂的情况则要引入栈来进行压栈出栈来改造成非递归，这个栈不一定要严格引入栈数据结构，只需要有这样的思路，用数组什么的就可以。?至于教科书上喜欢n!的示例，我想只是便于递归思路的引进和建立。真正做代码不可能的。 -------------------------------------------------------------------------------------------------------------------- 循环方法比递归方法快, 因为循环避免了一系列函数调用和返回中所涉及到的参数传递和返回值的额外开销。?递归和循环之间的选择。一般情况下, 当循环方法比较容易找到时, 你应该避免使用递归。这在问题可以按照一个递推关系式来描述时, 是时常遇到的, 比如阶乘问题就是这种情况。 反过来, 当很难建立一个循环方法时, 递归就是很好的方法。实际上, 在某些情形下, 递归方法总是显而易见的, 而循环方法却相当难找到。当某些问题的底层数据结构本身就是递归时, 则递归也就是最好的方法了。 --------------------------------------------------------------------------------------------------------------------------- 递归其实是方便了程序员难为了机器。它只要得到数学公式就能很方便的写出程序。优点就是易理解，容易编程。但递归是用栈机制实现的（c++），每深入一层，都要占去一块栈数据区域，对嵌套层数深的一些算法，递归会力不从心，空间上会以内存崩溃而告终，而且递归也带来了大量的函数调用，这也有许多额外的时间开销。所以在深度大时，它的时空性就不好了。?循环其缺点就是不容易理解，编写复杂问题时困难。优点是效率高。运行时间只因循环次数增加而增加，没什么额外开销。空间上没有什么增加。 ------------------------------------------------------