JAVA遞歸與非遞歸實現(xiàn)斐波那契數(shù)列
斐波那契數(shù)列（Fibonacci sequence），又稱黃金分割數(shù)列、因數(shù)學(xué)家列昂納多·斐波那契（Leonardoda Fibonacci[1] ）以兔子繁殖為例子而引入，故又稱為“兔子數(shù)列”，指的是這樣一個數(shù)列：0、1、1、2、3、5、8、13、21、34、……在數(shù)學(xué)上，斐波納契數(shù)列以如下被以遞歸的方法定義：F（0）=0，F(xiàn)（1）=1，F(xiàn)（n）=F(n-1)+F(n-2)（n≥2，n∈N*）在現(xiàn)代物理、準(zhǔn)晶體結(jié)構(gòu)、化學(xué)等領(lǐng)域，斐波納契數(shù)列都有直接的應(yīng)用，為此，美國數(shù)學(xué)會從1963起出版了以《斐波納契數(shù)列季刊》為名的一份數(shù)學(xué)雜志，用于專門刊載這方面的研究成果。
下面我用JAVA語言遞歸與非遞歸方式不同實現(xiàn)：
public class Feibonacii {
//使用遞歸方法實現(xiàn)斐波那契數(shù)列
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)斐波那契數(shù)列
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í)行都相當(dāng)快速。
分析：
（1）Java使用方法遞歸實現(xiàn)斐波那契數(shù)列，feibonaci1（45）執(zhí)行一次，Java執(zhí)行方法feibonaci1有2^44+2^43+……+2^1+1次，而feibonaci2(45)，只執(zhí)行了一次方法，但計算次數(shù)與feibonaci1一樣。
結(jié)論：JAVA描述斐波那契數(shù)列，更適合使用非遞歸方法的形式計算。
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
Ubuntu16.04安裝部署solr7的圖文詳細(xì)教程
這篇文章主要為大家詳細(xì)介紹了Ubuntu16.04安裝部署solr7的圖文詳細(xì)教程，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-07-07
eclipse+myeclipse 環(huán)境配置方法
eclipse+myeclipse配置環(huán)境2009-07-07
這篇文章主要介紹了Maven導(dǎo)入依賴時報錯如何解決,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-12-12
Java LinkedList的實現(xiàn)原理圖文詳解
今天小編就為大家分享一篇關(guān)于Java LinkedList的實現(xiàn)原理圖文詳解，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-01-01
Java實現(xiàn)Map遍歷key-value的四種方法
本文主要介紹了Java實現(xiàn)Map遍歷key-value的四種方法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-07-07
這篇文章主要介紹了java 多線程饑餓現(xiàn)象的問題解決方法的相關(guān)資料,需要的朋友可以參考下2017-06-06
Spring Boot 2.X整合Spring-cache(讓你的網(wǎng)站速度飛起來)
這篇文章主要介紹了Spring Boot 2.X整合Spring-cache(讓你的網(wǎng)站速度飛起來)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-09-09
Springboot整合多數(shù)據(jù)源配置流程詳細(xì)講解
這篇文章主要介紹了Springboot整合多數(shù)據(jù)源配置流程，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)吧2023-03-03
最近經(jīng)常在機房看同學(xué)在玩一個走迷宮的游戲,比較有趣，自己也用java寫一個實現(xiàn)隨機生成迷宮的算法,其實就是一個圖的深度優(yōu)先遍歷算法.2016-05-05
SpringBoot2.X Devtools熱部署實現(xiàn)解析
這篇文章主要介紹了SpringBoot2.X Devtools熱部署實現(xiàn)解析,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-08-08