什么是菲波那契数列。例子：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;
}
}
为什么递归在效率上会如此糟糕呢？递归由于是函数的自身调用，而函数的调用时需要消耗时间和空间的，每一次调用都需要内存分配，需要内存栈的出栈，入栈操作。所以自身的效率肯定是低于循环的。
