漫谈递归：递归与循环

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

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

大家都知道递归的实现是通过调用函数本身，函数调用的时候，每次调用时要做地址保存，参数传递等，这是通过一个递归工作栈实现的。具体是每次调用函数本身要保存的内容包括：局部变量、形参、调用函数地址、返回值。那么，如果递归调用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，欢迎访问原出处。