欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

JAVA递归与非递归实现斐波那契数列

程序员文章站 2023-11-21 13:38:58
斐波那契数列(fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(leonardoda fibonacci[1] )以兔子繁殖为例子而引入...

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

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。