JAVA如何使用遞歸與非遞歸實現(xiàn)斐波那契數列

這篇文章將為大家詳細講解有關JAVA如何使用遞歸與非遞歸實現(xiàn)斐波那契數列，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

斐波那契數列（Fibonacci sequence），又稱黃金分割數列、因數學家列昂納多·斐波那契（Leonardoda Fibonacci[1] ）以兔子繁殖為例子而引入，故又稱為“兔子數列”，指的是這樣一個數列：0、1、1、2、3、5、8、13、21、34、……在數學上，斐波納契數列以如下被以遞歸的方法定義：F（0）=0，F(xiàn)（1）=1，F(xiàn)（n）=F(n-1)+F(n-2)（n≥2，n∈N*）在現(xiàn)代物理、準晶體結構、化學等領域，斐波納契數列都有直接的應用，為此，美國數學會從1963起出版了以《斐波納契數列季刊》為名的一份數學雜志，用于專門刊載這方面的研究成果。

下面我用JAVA語言遞歸與非遞歸方式不同實現(xiàn)：

public class Feibonacii {
  //使用遞歸方法實現(xiàn)斐波那契數列
  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)斐波那契數列
  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)斐波那契數列，feibonaci1（45）執(zhí)行一次，Java執(zhí)行方法feibonaci1有2^44+2^43+……+2^1+1次，而feibonaci2(45)，只執(zhí)行了一次方法，但計算次數與feibonaci1一樣。

結論：JAVA描述斐波那契數列，更適合使用非遞歸方法的形式計算。

關于“JAVA如何使用遞歸與非遞歸實現(xiàn)斐波那契數列”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。