斐波那契數(shù)列（Fibonacci sequence），又稱黃金分割數(shù)列、因數(shù)學家列昂納多·斐波那契（Leonardoda Fibonacci[1] ）以兔子繁殖為例子而引入，故又稱為“兔子數(shù)列”，指的是這樣一個數(shù)列：0、1、1、2、3、5、8、13、21、34、……在數(shù)學上，斐波納契數(shù)列以如下被以遞歸的方法定義：F（0）=0，F(xiàn)（1）=1，F(xiàn)（n）=F(n-1)+F(n-2)（n≥2，n∈N*）在現(xiàn)代物理、準晶體結構、化學等領域，斐波納契數(shù)列都有直接的應用，為此，美國數(shù)學會從1963起出版了以《斐波納契數(shù)列季刊》為名的一份數(shù)學雜志，用于專門刊載這方面的研究成果。
下面我用JAVA語言遞歸與非遞歸方式不同實現(xiàn)：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
public class Feibonacii { //使用遞歸方法實現(xiàn)斐波那契數(shù)列 public static int feibonaci1(int n){ if(n==0){return 0;} if(n==1){return 1;} return feibonaci1(n-1)+feibonaci1(n-2); } //使用非遞歸方法實現(xiàn)斐波那契數(shù)列 public static int feibonaci2(int n){ int arr[] = new int[n+1]; arr[0]=0; arr[1]=1; for(int i=2;i<=n;i++){ arr[i] = arr[i-1]+arr[i-2]; } return arr[n]; } public static void main(String[] args) { for(int i=40;i<=45;i++){ System.out.println("feibonaci1 i="+i+",vaule="+feibonaci1(i)); } for(int i=40;i<=45;i++){ System.out.println("feibonaci2 i="+i+",vaule="+feibonaci2(i)); } }} |
執(zhí)行時明顯發(fā)現(xiàn)遞歸方法43之后執(zhí)行相對緩慢，非遞歸方法執(zhí)行都相當快速。
分析：
（1）Java使用方法遞歸實現(xiàn)斐波那契數(shù)列，feibonaci1（45）執(zhí)行一次，Java執(zhí)行方法feibonaci1有2^44+2^43+……+2^1+1次，而feibonaci2(45)，只執(zhí)行了一次方法，但計算次數(shù)與feibonaci1一樣。
結論：JAVA描述斐波那契數(shù)列，更適合使用非遞歸方法的形式計算。
以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：http://blog.csdn.net/u012712901/article/details/50979904
