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