JAVA如何使用递归与非递归实现斐波那契数列

这篇文章将为大家详细讲解有关JAVA如何使用递归与非递归实现斐波那契数列，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。

创新互联是一家以网站建设、网页设计、品牌设计、软件运维、成都网站推广、小程序App开发等移动开发为一体互联网公司。已累计为纸箱等众行业中小客户提供优质的互联网建站和软件开发服务。

斐波那契数列（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语言递归与非递归方式不同实现：

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描述斐波那契数列，更适合使用非递归方法的形式计算。

关于“JAVA如何使用递归与非递归实现斐波那契数列”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。