Insert time: 1355.69 Node number: 200000

Non-Stack time: 207.086

LevlOrder time: 766.023

PreOrder time: 183.287

InOrder time: 179.835

PostOrder time: 190.674

更多内容请看C/C++技术专题数据结构数据结构教程专题，或 递归遍历的速度是最快的

　　这恐怕是上面结果得出的最直接的结论。

不知从哪听来的观点“递归的速度慢，为了提高速度，应该用栈消解递归”，证据就是斐波那契数列的计算，遗憾的是斐波那契数列的非递归算法是循环迭代，不是栈消解；如果他真的拿栈来模拟，他就会发现，其实用栈的更慢。

　　我们来看看为什么。递归的实现是将参数压栈，然后call自身，最后按层返回，一系列的动作是在堆栈上操作的，用的是push、pop、call、ret之类的指令。而用ADT栈来模拟递归调用，实现的还是上述指令的功能，不同的是那些指令对照的ADT实现可就不只是一条指令了。谁都明白模拟的执行效率肯定比真实的差，怎么会在这个问题上就犯糊涂了呢？

　　当然，你非要在visit函数中加入类似这样的istream file1(“input.txt”)，然后在用栈模拟的把这个放在循环的外面，最后你说，栈模拟的比递归的快，我也无话可说——曾经就见过一个人，http://www.csdn.net/Develop/Read_Article.asp?Id=18342将数据库连接放在visit函数里面，然后说递归的速度慢。

　　如果一个递归过程用非递归的方法实现后，速度提高了，那只是因为递归做了一些无用功。比如用循环消解的尾递归，是多了无用的压栈和出栈才使速度受损的；斐波那契数列计算的递归改循环迭代所带来的速度大幅提升，是因为改掉了重复计算的毛病。假使一个递归过程必须要用栈才能消解，那么，完全模拟后的结果根本就不会对速度有任何提升，只会减慢；如果你改完后速度提升了，那只证明你的递归函数写的有问题，例如多了许多重复操作——打开关闭文件、连接断开数据库，而这些完全可以放到递归外面。递归方法本身是简洁高效的，只是使用的人不注意使用方法。

　　这么看来，研究递归的栈消解好像是无用的，其实不然，用栈模拟递归还是有点意义的，只是并不大，下面将给出示例来说明。

　　栈模拟递归的好处是节省了堆栈

　　将上面的程序//node number那行的数值改为15000——不改没反应了别找我，将//random swap那行注释掉，运行debug版，耐心的等30秒，就会抛异常了，最后的输出结果是这样的：

Insert time: 27555.5 Node number: 15000

Non-Stack time: 16.858

LevlOrder time: 251.036

　　这只能说明堆栈溢出了。你可以看到层次遍历还能工作（由此类推，栈模拟的也能工作），但是递归的不能工作了。这是因为和总的内存空间比起来，堆栈空间是很少的，如果递归的层次过深，堆栈就溢出了。所以，如果你预先感到递归的层次可能过深，你就要考虑用栈来消解了。

　　然而，如果你必须用递归，而递归的层次深到连堆栈都溢出了，那肯定是你的算法有问题，或者是那个程序根本不适合在PC上运行——运行起来就象死机了，这样的程序谁敢用？所以说用栈模拟递归是有意义的，但是不大，因为很少用到。

　　对于树结构来说，如果没有双亲指针，那么遍历时的递归是必须的，与其搞什么栈消解不如添加一个双亲指针，这实际上也是用堆空间换取堆栈空间的一个方法，只是比ADT栈来得直接、高效罢了。

　　综上，递归的栈消解，实际上只能节省堆栈空间，不仅不会提高速度，相反却会降低——天下哪有白吃的午餐，既省了堆栈空间还能提高速度。那些“栈消解递归能提高速度”的谣传只是对“消除尾递归能提高速度”的不负责任的引申，然而一群人以讹传讹，真就像是那么回事了，这就叫三人成虎。等我这时候再回过头看教科书，竟然没看见一本书上写着“栈消解递归能提高速度”。真的，以前一直被误导了，还不知道是被谁误导的——书上根本就没有写。

　　另外的结论

　　对比上面两组结果，可以看到插入15000个节点比200000个节点消耗的时间还多，其原因就是插入数据的顺序不同，从而导致了find的效率不同。

上一页 [1] [2] [3] [4] [5] [6] 下一页

上一篇:用游戏串起程序员的基本功之四

下一篇:Bjarne：必须在类声明处赋予数据吗？

数据结构学习（C++）之二叉树相关文章：

·教你学习如何破解XP登陆密码

·EasyRecovery 604硬盘数据恢复软件技巧

·AIX 5L 学习大纲/简易教程（2）（未经许可，请勿COPY）

·学习SQL语句之SQL语句大全

·asp.net(C#)海量数据表高效率分页算法（易懂，不使用存储过程）

·C#源码读取excel数据到程序中-SQL SERVER-到dataset中

·SQL2000 数据库安装说明

·SQL数据库完全使用手册

·大学生毕业实习报告范文之二

·Visual C++ ADO数据库编程入门

数据结构学习（C++）之二叉树相关软件：

·洪恩轻松教你学电脑_internet学习

·鸟哥的linux私房菜：基础学习篇

·新东方演讲录俞敏洪老师学习英语与人生奋斗

·玄异怪谭系列丛书之二

·ACCESS数据库教程北京大学的ACCESS教程

·zemax教学视频和学习笔记

·爆出网站数据库路径

·混凝土结构设计规范GB50010-2002

·双向式英语学习法mp3+文档

·钢结构工程施工质量验收规范GB50205-2001

特别声明：本站除部分特别声明禁止转载的专稿外的其他文章可以自由转载，但请务必注明出处和原始作者。文章版权归文章原始作者所有。对于被本站转载文章的个人和网站，我们表示深深的谢意。如果本站转载的文章有版权问题请联系编辑人员，我们尽快予以更正。
[打印本页] [关闭窗口] 转载请注明来源：http://www.vipcn.net

	\| 帮助(？) \| 版权声明 \| 友情连接 \| 关于我们 \| 信息发布
Copyright 2007 www.vipcn.net All Rights Reserved.	鄂ICP备05000083号Powered by:viphot