Java递归发实现Fibonacci数列,尾递归实现Fibonacci数列,并获取计算所需时间

发布于:2021-11-29 01:13:49

递归法计算Fibonacci数列:


它可以递归地定义为:



第n个Fibonacci数列可递归地计算如下:


int fibonacci(int n)


???{


???????if (n <= 1) return 1;


???????return fibonacci(n-1)+fibonacci(n-2);


???}


以下这个源代码可以计算出递归法实现Fibonacci数列时,n为45、46、47、48时所需的时间。


import?java.text.DateFormat;


import?java.util.Date;


import?java.util.Scanner;


public?class?time {


public?static?void?main(String[] args) {


?


Date date=new?Date();


DateFormat df=DateFormat.getDateTimeInstance();


?


System.out.println(df.format(date));


Scanner in=new?Scanner(System.in);


int?n=in.nextInt();


?


time a=new?time();


a.Fib(n);


System.out.println("相加的结果为:"+Fib(n));


?


Date date1=new?Date();


System.out.println(df.format(date1));


long?time=(date1.getTime()-date.getTime())/1000;


System.out.println("当n为"+n+"时,计算所需要的时间差为:"+time+"秒");


}


public?static?int?Fib(int?n){


if(n<=1) return?1;


return?Fib(n-1)+Fib(n-2);


}


}



可以看到,递归法所需要的时间还是很久的,因为计算F(n)时,需首先计算F(n-1)和F(n-2)


,而在计算F(n-1)时已经算过F(n-2)了,但是递归算法看不到这点,所以产生这么多假发,所需时间也就多了,效率就下降了。


尾递归:


尾递归比递归函数效率高太多了,尾递归就是把当前的运算结果(或路径)放在参数里传给下层函数。而不是把下层函数的运算结果用来本次的计算。尾递归是极其重要的,不用尾递归,函数的堆栈耗用难以估量,需要保存很多中间函数的堆栈,而递归每一次计算出来的部分结果,在下一次循环时还需要再计算一遍。


import?java.text.DateFormat;


import?java.util.Date;


import?java.util.Scanner;


public?class?time {


public?static?void?main(String[] args) {


?


Date date=new?Date();


DateFormat df=DateFormat.getDateTimeInstance();


Scanner in=new?Scanner(System.in);


int?n=in.nextInt();


?


time a=new?time();


a.Fib(n);


System.out.println("相加的结果为:"+Fib(n));


Date date1=new?Date();


long?time=(date1.getTime()-date.getTime())/1000;


System.out.println("当n为"+n+"时,计算所需要的时间差为:"+time+"秒");


}


public?static?int?Fib(int?n){


if(n<2) return?n;


return?Fibo(n,1,1,3);


}


public?static?int?Fibo(int?n,int?r1,int?r2,int?begin){


if(n==begin) return?r1+r2;


return?Fibo(n,r2,r1+r2,++begin);


}


}



?


?

相关推荐

最新更新

猜你喜欢