1. 前言
本節(jié)內容是遞歸算法系列之一：斐波那契數列遞歸求解吹截，主要介紹了斐波那契數列的定義蚣旱，然后用遞歸的實現思想分析了一下斐波那契數列崇决，最后給出了基于 Java 代碼應用遞歸思想實現斐波那契數列的代碼實現及簡單講解丝蹭。
2. 什么是斐波那契數列秤掌？
斐波那契數列（Fibonacci sequence），也稱之為黃金分割數列再来，由意大利數學家列昂納多?斐波那契（Leonardo Fibonacci）提出蒙兰。斐波那契數列指的是這樣的一個數列：1、1芒篷、2搜变、3、5梭伐、8痹雅、13、21糊识、34、……摔蓝，這個數列從第 3 項開始赂苗，每一項都等于前面兩項之和。在數學上贮尉，斐波那契數列可以被遞推的方法定義如下：
F(1)=1拌滋，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）
斐波那契數列是數學上面一個經典的例子猜谚，并且在日常生活中有很多應用败砂，他還與黃金分割有著密不可分的聯系，而且當 n 趨向于無窮大時魏铅，前一項與后一項的比值越來越逼近黃金分割值 0.618昌犹。
3. 用遞歸方法求解斐波那契數列
在這一節(jié)中，我們就需要利用遞歸的思想去求解斐波那契數列览芳，當給出一個斐波那契中第幾項的數字斜姥，然后求解出對應的斐波那契數值。在之前沧竟，我們已經定義了遞歸算法的相關概念铸敏，并且明確了需要應用遞歸時候的三要素：
- 遞歸終止條件；
- 遞歸終止時候的處理方法悟泵；
- 遞歸中重復的邏輯提取杈笔，縮小問題規(guī)模。
接下來糕非，我們將利用遞歸的知識來解決斐波那契數列問題蒙具，明確在斐波那契數列求解問題中的遞歸三要素分別是什么敦第。
斐波那契數列的遞歸終止條件
顯然易見，通過觀察斐波那契數列的定義店量，我們很容易發(fā)現當 n=1 或者 n=2 時芜果，是斐波那契數列的遞歸終止條件，這個時候可以給出斐波那契數列的具體值融师。
斐波那契數列遞歸終止時候的處理方法
同樣的右钾，基于斐波那契數列的遞推定義，當斐波那契數列達到終止條件 n=1 或者 n=2 時旱爆，我們也很容易發(fā)現對應 F(1)=1舀射，F(2)=1，這就是斐波那契數列在遞歸終止時對應的取值怀伦。
斐波那契數列的遞歸重復邏輯提取
按照斐波那契數列的數學定義脆烟，F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）房待，即當 n ≥ 3 時邢羔，斐波那契數列中這一項的值等于前面兩項的值之和，這樣便可以將求解一個比較大的斐波那契數列轉化為求解較小數值的斐波那契數列值桑孩，這里面有重復邏輯可以遞歸復用拜鹤。
例如，當我們求解斐波那契數列中的 F(5) 時流椒，按照定義敏簿，我們有：
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 代碼示例及實現講解
在說明斐波那契數列的遞歸描述之后宣虾，我們看看如何用 Java 代碼來實現對斐波那契數列的計算惯裕。
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));
}
//斐波那契數列數列的計算
private static int fibonacci(int n){
//如果是終止條件，按照要求返回終止條件對應結果
if( n==1 || n==2 ){
return 1;
}else {
//非終止條件绣硝，按照要求把大的問題拆分成小問題蜻势，調用自身函數遞歸處理
return fibonacci(n-1)+fibonacci(n-2);
}
}
}
運行結果如下：
1
1
2
3
5
代碼中的第 4 行至第 8 行分別調用斐波那契數列計算函數，計算出斐波那契數列中對應 n=1,2,3,4,5 時斐波那契數列的取值域那，進行結果比較咙边，判斷斐波那契數列程序實現是否正確。代碼中的第 12 行至第 20 行是斐波那契數列應用遞歸方法進行斐波那契數列的計算次员，按照遞歸的三要素進行計算處理败许。
5. 小結
本節(jié)主要介紹了用遞歸思想求解斐波那契數列，在學完本節(jié)課程之后淑蔚，我們了解到了什么是斐波那契數列市殷，并且將遞歸算法在斐波那契數列中進行了實際應用，需要掌握斐波那契數列的遞歸求解方法刹衫，并自己可以實現相關的代碼實現醋寝，并清楚里面的每一步邏輯搞挣。
