java实现斐波那契数列的几种方法时间效率问

这道兔子题的实质就是斐波那契数列： 有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少? 
1 1 2 3 5 8 13 …… 

方案一：递归算法实现

public static long fib(int n){

if(n <= 1){

return 1;

}else{

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

}

}

初看起来，使用递归算法是最简洁的。可是，如果将程序编码病在n值为40左右时运行那么这个程序让人感到效率低的吓人。n>4时，其时间效率为fib(N)>=(3/2)的n次方，这个程序运行的时间以指数的速度增长。这大概是最坏的情况。

方案二：数组方式

public static int fib2(int n) {

int[] array = new int[n];

array[0] = array[1] =1;

for (int i = 0; i < array.length; i++) {

if (i == 0 || i == 1) {

return array[i];

}else {

array[i] = array[i-1] +array[i-2];

}

} return array[i];

}

数组方式的好处是只是用了一个for循环，运行时间可以显著降低。