菲波那契数列。

什么是菲波那契数列。例子：0，1，1，2，3，5，8，11…这样的数列称为菲波那契数列。直接上代码比较靠谱

/**

* 题目：写一个函数，输入n，求菲波那契数列的第n项

* if 0;=0

* if 1;=1;

* else f(n-1)+f(n-2)

* 菲波那契数列

* 递归和非递归的实现 顺便比较一下两者的效率

* 当n 大于50 是,递归的计算很慢，一直没有算出结果，然后非递归很快就计算出来。

* 在n 逐渐这大n，递归还是不适合。

* Created by Darker on 15/7/17.

*/

public class Fibonacci{

public static void main(String[]args){

System.out.println("递归开始时间："+System.currentTimeMillis());

System.out.println(findValueUseRecursive());

System.out.println("递归结束时间："+System.currentTimeMillis());

System.out.println("非递归开始时间："+System.currentTimeMillis());

System.out.println(findValueUseInterative(50));

System.out.println("非递归结束时间："+System.currentTimeMillis());

}

//递归实现

public static long findValueUseRecursive(int n){

if(n<=1)return n;

return findValueUseRecursive(n-1)+findValueUseRecursive(n-2);

}

//非递归实现

public static long findValueUseInterative(int n){

if(n<=1)return n;

long firstValue=0;

long secondValue=1; 

long lastValue=0;

for(int i=2;i<=n;i++){

lastValue=firstValue+secondValue;

firstValue=secondValue;

secondValue=lastValue;

}

return lastValue;

}

}

为什么递归在效率上会如此糟糕呢？递归由于是函数的自身调用，而函数的调用时需要消耗时间和空间的，每一次调用都需要内存分配，需要内存栈的出栈，入栈操作。所以自身的效率肯定是低于循环的。