漫谈递归:递归与循环

大部分递归可以转化为循环
服务器君一共花费了440.568 ms进行了7次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

所谓的递归慢到底是什么原因呢?

前面一篇讲到了递归的效率问题,但是没具体深入到数据结构层面的解释,这里补充一下。

大家都知道递归的实现是通过调用函数本身,函数调用的时候,每次调用时要做地址保存,参数传递等,这是通过一个递归工作栈实现的。具体是每次调用函数本身要保存的内容包括:局部变量、形参、调用函数地址、返回值。那么,如果递归调用N次,就要分配N*局部变量、N*形参、N*调用函数地址、N*返回值。这势必是影响效率的。

递归是利用系统的堆栈保存函数当中的局部变量来解决问题的。递归说白了就是在栈处理栈上一堆的指针指向内存中的对象,这些对象一直不被释放,直到递归执行到最后一次跳出条件的时候,才一个个出栈。所以开销很大。

用循环效率会比递归效率高吗?

递归与循环是两种不同的解决问题的典型思路。当然也并不是说循环效率就一定比递归高,递归和循环是两码事,递归带有栈操作,循环则不一定,两个概念不是一个层次,不同场景做不同的尝试。

1. 递归算法:

  • 优点:代码简洁、清晰,并且容易验证正确性。(如果你真的理解了算法的话,否则你更晕)
  • 缺点:它的运行需要较多次数的函数调用,如果调用层数比较深,需要增加额外的堆栈处理(还有可能出现堆栈溢出的情况),比如参数传递需要压栈等操作,会对执行效率有一定影响。但是,对于某些问题,如果不使用递归,那将是极端难看的代码。

2. 循环算法:

  • 优点:速度快,结构简单。
  • 缺点:并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用循环并不困难的话,最好使用循环。

3. 递归算法和循环算法总结:

递归通常很直白地描述了一个求解过程,因此也是最容易被想到和实现的算法。循环其实和递归具有相同的特性(即:做重复任务),但有时,使用循环的算法并不会那么清晰地描述解决问题步骤。单从算法设计上看,递归和循环并无优劣之别。然而,在实际开发中,因为函数调用的开销,递归常常会带来性能问题,特别是在求解规模不确定的情况下。而循环因为没有函数调用开销,所以效率会比递归高。除少数编程语言对递归进行了优化外,大部分语言在实现递归算法时还是十分笨拙,由此带来了如何将递归算法转换为循环算法的问题。算法转换应当建立在对求解过程充分理解的基础上,有时甚至需要另辟蹊径。

  • 一般递归调用可以处理的算法,也通过循环去解决需要额外的低效处理。
  • 现在的编译器在优化后,对于多次调用的函数处理会有非常好的效率优化,效率未必低于循环。
  • 递归和循环两者完全可以互换。如果用到递归的地方可以很方便使用循环替换,而不影响程序的阅读,那么替换成递归往往是好的。(例如:求阶乘的递归实现与循环实现。)

要转换成为非递归,两步工作:

  1. 第一步,可以自己建立一个堆栈保存这些局部变量,替换系统栈;
  2. 第二步把对递归的调用转变为循环处理就可以了。

那么递归使用的栈是什么样的一个栈呢?

首先,看一下系统栈和用户栈的用途。

  1. 系统栈(也叫核心栈、内核栈)是内存中属于操作系统空间的一块区域,其主要用途为:
    • 保存中断现场,对于嵌套中断,被中断程序的现场信息依次压入系统栈,中断返回时逆序弹出;
    • 保存操作系统子程序间相互调用的参数、返回值、返回点以及子程序(函数)的局部变量。
  2. 用户栈是用户进程空间中的一块区域,用于保存用户进程的子程序间相互调用的参数、返回值、返回点以及子程序(函数)的局部变量。

我们编写的递归程序属于用户程序,因此使用的是用户栈。

延伸阅读

此文章所在专题列表如下:

  1. 漫谈递归:递归的思想
  2. 漫谈递归:递归需要满足的两个条件
  3. 漫谈递归:字符串回文现象的递归判断
  4. 漫谈递归:二分查找算法的递归实现
  5. 漫谈递归:递归的效率问题
  6. 漫谈递归:递归与循环
  7. 漫谈递归:循环与迭代是一回事吗?
  8. 递归计算过程与迭代计算过程
  9. 漫谈递归:从斐波那契开始了解尾递归
  10. 漫谈递归:尾递归与CPS
  11. 漫谈递归:补充一些Continuation的知识
  12. 漫谈递归:PHP里的尾递归及其优化
  13. 漫谈递归:从汇编看尾递归的优化

本文地址:http://www.nowamagic.net/librarys/veda/detail/2322,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/2322

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《链接器和加载器》 莱文(John R.Levine) (作者), 李勇 (译者)

《链接器和加载器》讲述构建程序的关键工具——链接器和加载器,内容包括链接和加载、体系结构、目标文件、存储分配、符号管理、库、重定位、加载和覆盖、共享库、动态链接和加载、动态链接的共享库,以及着眼于成熟的现代链接器所做的一些变化;并介绍一个持续的实践项目,即使用Perl语言开发一个可用的小链接器。《链接器和加载器》适合高校计算机相关专业的学生、实习程序员、语言设计者和开发人员阅读参考。

更多计算机宝库...