JAVA再帰と非再帰実現フィボナッチ数列


フィボナッチの数列は、黄金分割数列とも呼ばれ、数学者レオナルド・フィボナッチがウサギの繁殖例として導入したもので、ウサギの数列とも言われています。0、1、1、2、3、8、13、21、34、数学…フィボナッチ数列は、F(0)=0、F(1)=1、F(n)=F(n−1)+F(n−2)(n≧2、n∈N*)を再帰的に定義し、現代物理、準結晶数学、化学などの分野でフィボナッチ数列が直接的に適用されているため、米国の数学会は1963年から雑誌「フィボナッチ」を出版しました。この方面の研究成果を専門に掲載するのに使います。
次はJAVA言語で再帰と非再帰の方式と違います。

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の使用方法はフィボナッチ数列を再帰的に実現し、feibonaci 1(45)は一回実行し、Javaの実行方法はfeibonaci 1は2^44+2^43++2^1+1回、feibonaci 2(45)は一回だけ実行したが、計算回数はfeibonaci 1と同じです。
結論:JAVAはフィボナッチの数列を記述し、非再帰的方法の形式計算により適している。
以上が本文の全部です。皆さんの勉強に役に立つように、私たちを応援してください。