深究递归和迭代

深究递归和迭代

使用场景：

        需要重复地多次地计算相同的问题，一般会用到递归和循环。

递归：

        概念：内部调用函数本身。

        使用前提：在使用递归的时候，必须有一个明确的递归结束条件，称之为递归出口。

使用递归，必须预期收敛。

循环：

        通过设置初始条件和结束条件，在一个范围内重复计算。

        代码的可读性不如递归，但是效率更高。

递归的优点：

        1. 代码简洁；

        2. 在树的前序，中序，后序的遍历算法中，递归的实现比循环简单很多。

递归的缺点：

        1. 时间和空间的消耗比较大。

        每一个线程都会有一个私有的栈mixed stack，存储java方法的桢栈和native方法的桢栈。每一次方法的调用都涉及到一个桢栈的入栈到出栈。同时，会涉及到分配内存空间，保存参数，返回地址和临时变量，而且往栈里压入数据和弹出都需要时间。

        2. 递归会出现重复计算。

        递归的本质是把一个问题分解为多个问题，如果多个问题存在重复计算，有时候这个情况会随着n成指数增长。比如斐波那契的递归就是一个例子。

        3. 递归还有栈溢出的问题，每个线程的栈容量多少有限的。

        如果栈内存没有可用空间存储方法桢栈（包括局部变量表，操作数栈，返回地址，动态链接），jvm会抛出java.lang.StackOverFlowError.

        栈的内存远远小于堆内存，-Xss选项设置栈内存大小，-Xms设置堆开始的大小，-Xmx堆最大值。

        (ps：如果是堆内存没有可用空间存储生成对象，jvm会抛出java.lang.OutOfMemoryError.)

迭代的速度快，那么递归存在的意义呢？

       理论上来说，所有的递归函数都可以转换为迭代函数，反之亦然。但是一般来说，代价比较高。

       实际上来说，迭代都可以转换为递归，但是递归不一定能转换为迭代。 

---------------------

搬家

原来地址

https://blog.csdn.net/YY_worhol/article/details/83617109