当前位置 博文首页 > 一个好孩子啊的博客：java递归的效率问题及递归与循环比较
1.所谓的递归慢到底是什么原因呢？
大家都知道递归的实现是通过调用函数本身，函数调用的时候，每次调用时
要做地址保存，参数传递等，这是通过一个递归工作栈实现的。具体是每次
调用函数本身要保存的内容包括：局部变量、形参、调用函数地址、返回值。
那么，如果递归调用N次，就要分配N*局部变量、N*形参、N*调用函数地址、
N*返回值。这势必是影响效率的。
2.用循环效率会比递归效率高吗？
递归与循环是两种不同的解决问题的典型思路。当然也并不是说循环效率就
一定比递归高，递归和循环是两码事，递归带有栈操作，循环则不一定，两
个概念不是一个层次，不同场景做不同的尝试。
2.1递归算法：
优点：代码简洁、清晰，并且容易验证正确性。（如果你真的理解了算法的
话，否则你更晕）
缺点：它的运行需要较多次数的函数调用，如果调用层数比较深，需要增加
额外的堆栈处理（还有可能出现堆栈溢出的情况），比如参数传递需要压栈
等操作，会对执行效率有一定影响。但是，对于某些问题，如果不使用递归，
那将是极端难看的代码。
2.2循环算法：
优点：速度快，结构简单。
缺点：并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用
循环并不困难的话，最好使用循环。
2.3递归算法和循环算法总结：
1. 一般递归调用可以处理的算法，也通过循环去解决常需要额外的低效处理。
2. 现在的编译器在优化后，对于多次调用的函数处理会有非常好的效率优化
，效率未必低于循环。
3.递归和循环两者完全可以互换。如果用到递归的地方可以很方便使用循环
替换，而不影响程序的阅读，那么替换成递归往往是好的。（例如：求阶乘
的递归实现与循环实现。）
3.那么递归使用的栈是什么样的一个栈呢？首先，看一下系统栈和用户栈的用途。
3.1系统栈（也叫核心栈、内核栈）是内存中属于操作系统空间的一块区域，
其主要用途为： (1)保存中断现场，对于嵌套中断，被中断程序的现场信息
依次压入系统栈，中断返回时逆序弹出； (2)保存操作系统子程序间相互调
用的参数、返回值、返回点以及子程序(函数)的局部变量。
3.2用户栈是用户进程空间中的一块区域，用于保存用户进程的子程序间相互
调用的参数、返回值、返回点以及子程序(函数)的局部变量。
我们编写的递归程序属于用户程序，因此使用的是用户栈。
