斐波那契数列算是一个非常古老的数学题目了，它的通项公式是：F(n) = F(n-1)+F(n-2)。   在编程中，利用递归的思想去求斐波那契数列也算的上是一个很经典的算法。众所周知，这也基本是所有的关于斐波那契效率最低的算法。
   但是通过这个分析这个方案为啥效率这么低，还是发现了递归一些很本质的东西：
   1：要调用的递归的方法的必须在某个时刻的返回值是确定的，也就是在满足一定的条件时，能不再调用它本身，否则就成了无穷递归，会导致桟内存溢出。在菲波那切数列的计算中，所有的计算都是基于最后方法中传入的值是否是1和2来决定是否结束递归调用（1和2返回的值都是1），例如：如果要计算第44个数列值701408733，底层就要进行701408733次循环，最后把这么多次返回值的1一个个的加起来。基本耗时在13s左右才能完成计算。
   2：递归类似于一种隐式的循环，这种重复执行不需要循环的控制。
   3：递归方法不一定有返回值。例如利用递归遍历计算机某个路径下的所有文件，但是深度未知，就可以利用方法来查找文件。可以在方法参数中传入一个文件路径，遍历该路径下的所有文件，如果是文件就输出文件名，如果是文件夹就递归调用，直到找到所有所有文件，结束递归调用。

递归的关键是   确定结束值

效率低为什么还要用呢

看着好难。

6666666666

cyongcar 发表于 2016-11-20 12:28
效率低为什么还要用呢

虽然效率低，可这东西确实可以用递归做。另一方面想通过这个例子分析一些递归的特点。