遞歸算法之斐波那契數(shù)列

1. 前言

本節(jié)內(nèi)容是遞歸算法系列之一：斐波那契數(shù)列遞歸求解，主要介紹了斐波那契數(shù)列的定義，然后用遞歸的實(shí)現(xiàn)思想分析了一下斐波那契數(shù)列，最后給出了基于 Java 代碼應(yīng)用遞歸思想實(shí)現(xiàn)斐波那契數(shù)列的代碼實(shí)現(xiàn)及簡單講解。

2. 什么是斐波那契數(shù)列？

斐波那契數(shù)列（Fibonacci sequence），也稱之為黃金分割數(shù)列，由意大利數(shù)學(xué)家列昂納多?斐波那契（Leonardo Fibonacci）提出。斐波那契數(shù)列指的是這樣的一個(gè)數(shù)列：1、1、2、3、5、8、13、21、34、……，這個(gè)數(shù)列從第 3 項(xiàng)開始，每一項(xiàng)都等于前面兩項(xiàng)之和。在數(shù)學(xué)上，斐波那契數(shù)列可以被遞推的方法定義如下：

F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）

斐波那契數(shù)列是數(shù)學(xué)上面一個(gè)經(jīng)典的例子，并且在日常生活中有很多應(yīng)用，他還與黃金分割有著密不可分的聯(lián)系，而且當(dāng) n 趨向于無窮大時(shí)，前一項(xiàng)與后一項(xiàng)的比值越來越逼近黃金分割值 0.618。

3. 用遞歸方法求解斐波那契數(shù)列

在這一節(jié)中，我們就需要利用遞歸的思想去求解斐波那契數(shù)列，當(dāng)給出一個(gè)斐波那契中第幾項(xiàng)的數(shù)字，然后求解出對應(yīng)的斐波那契數(shù)值。在之前，我們已經(jīng)定義了遞歸算法的相關(guān)概念，并且明確了需要應(yīng)用遞歸時(shí)候的三要素：

1. 遞歸終止條件；
2. 遞歸終止時(shí)候的處理方法；
3. 遞歸中重復(fù)的邏輯提取，縮小問題規(guī)模。

接下來，我們將利用遞歸的知識(shí)來解決斐波那契數(shù)列問題，明確在斐波那契數(shù)列求解問題中的遞歸三要素分別是什么。

斐波那契數(shù)列的遞歸終止條件
顯然易見，通過觀察斐波那契數(shù)列的定義，我們很容易發(fā)現(xiàn)當(dāng) n=1 或者 n=2 時(shí)，是斐波那契數(shù)列的遞歸終止條件，這個(gè)時(shí)候可以給出斐波那契數(shù)列的具體值。

斐波那契數(shù)列遞歸終止時(shí)候的處理方法
同樣的，基于斐波那契數(shù)列的遞推定義，當(dāng)斐波那契數(shù)列達(dá)到終止條件 n=1 或者 n=2 時(shí)，我們也很容易發(fā)現(xiàn)對應(yīng) F(1)=1，F(2)=1，這就是斐波那契數(shù)列在遞歸終止時(shí)對應(yīng)的取值。

斐波那契數(shù)列的遞歸重復(fù)邏輯提取
按照斐波那契數(shù)列的數(shù)學(xué)定義，F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*），即當(dāng) n ≥ 3 時(shí)，斐波那契數(shù)列中這一項(xiàng)的值等于前面兩項(xiàng)的值之和，這樣便可以將求解一個(gè)比較大的斐波那契數(shù)列轉(zhuǎn)化為求解較小數(shù)值的斐波那契數(shù)列值，這里面有重復(fù)邏輯可以遞歸復(fù)用。

例如，當(dāng)我們求解斐波那契數(shù)列中的 F(5) 時(shí)，按照定義，我們有：

F(5) = F(4) + F(3) // 遞歸分解
? = ( F(3) + F(2) ) + ( F(2）+F(1) ) // 遞歸求解
? = [ ( F(2)+F(1) ) + 1 ] + ( 1+1 ) // 遞歸求解，遇到終止條件就求解
? = [(1+1) +1 ]+(1+1) // 歸并
? = 3 + 2 // 歸并
? = 5 // 歸并

4. 基于 Java 代碼示例及實(shí)現(xiàn)講解

在說明斐波那契數(shù)列的遞歸描述之后，我們看看如何用 Java 代碼來實(shí)現(xiàn)對斐波那契數(shù)列的計(jì)算。

public class Fibonacci {

    public static void main(String[] args){
        System.out.println(fibonacci(1));
        System.out.println(fibonacci(2));
        System.out.println(fibonacci(3));
        System.out.println(fibonacci(4));
        System.out.println(fibonacci(5));
    }

    //斐波那契數(shù)列數(shù)列的計(jì)算
    private static int fibonacci(int n){
        //如果是終止條件，按照要求返回終止條件對應(yīng)結(jié)果
        if( n==1 || n==2 ){
            return 1;
        }else {
            //非終止條件，按照要求把大的問題拆分成小問題，調(diào)用自身函數(shù)遞歸處理
            return fibonacci(n-1)+fibonacci(n-2);
        }
    }

}

運(yùn)行結(jié)果如下：

1
1
2
3
5

代碼中的第 4 行至第 8 行分別調(diào)用斐波那契數(shù)列計(jì)算函數(shù)，計(jì)算出斐波那契數(shù)列中對應(yīng) n=1,2,3,4,5 時(shí)斐波那契數(shù)列的取值，進(jìn)行結(jié)果比較，判斷斐波那契數(shù)列程序?qū)崿F(xiàn)是否正確。代碼中的第 12 行至第 20 行是斐波那契數(shù)列應(yīng)用遞歸方法進(jìn)行斐波那契數(shù)列的計(jì)算，按照遞歸的三要素進(jìn)行計(jì)算處理。

5. 小結(jié)

本節(jié)主要介紹了用遞歸思想求解斐波那契數(shù)列，在學(xué)完本節(jié)課程之后，我們了解到了什么是斐波那契數(shù)列，并且將遞歸算法在斐波那契數(shù)列中進(jìn)行了實(shí)際應(yīng)用，需要掌握斐波那契數(shù)列的遞歸求解方法，并自己可以實(shí)現(xiàn)相關(guān)的代碼實(shí)現(xiàn)，并清楚里面的每一步邏輯。