遞歸編程與數學應用

① 08《演算法入門教程》遞歸演算法之斐波那契數列

本節內容是遞歸演算法系列之一：斐波那契數列遞歸求解，主要介紹了斐波那契數列的定義，然後用遞歸的實現思想分析了一下斐波那契數列，最後給出了基於 Java 代碼應用遞歸思想實現斐波那契數列的代碼實現及簡單講解。

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

斐波那契數列是數學上面一個經典的例子，並且在日常生活中有很多應用，他還與黃金分割有著密不可分的聯系，而且當 n 趨向於無窮大時，前一項與後一項的比值越來越逼近黃金分割值 0.618。

在這一節中，我們就需要利用遞歸的思想去求解斐波那契數列，當給出一個斐波那契中第幾項的數字，然後求解出對應的斐波那契數值。在之前，我們已經定義了遞歸演算法的相關概念，並且明確了需要應用遞歸時候的三要素：

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

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

在說明斐波那契數列的遞歸描述之後，我們看看如何用 Java 代碼來實現對斐波那契數列的計算。

運行結果如下：

代碼中的第 4 行至第 8 行分別調用斐波那契數列計算函數，計算出斐波那契數列中對應 n=1,2,3,4,5 時斐波那契數列的取值，進行結果比較，判斷斐波那契數列程序實現是否正確。代碼中的第 12 行至第 20 行是斐波那契數列應用遞歸方法進行斐波那契數列的計算，按照遞歸的三要素進行計算處理。

本節主要介紹了用遞歸思想求解斐波那契數列，在學完本節課程之後，我們了解到了什麼是斐波那契數列，並且將遞歸演算法在斐波那契數列中進行了實際應用，需要掌握斐波那契數列的遞歸求解方法，並自己可以實現相關的代碼實現，並清楚裡面的每一步邏輯。

② 計算機裡面什麼是遞歸

在數學和計算機科學中，當一類對象或方法可以由兩個屬性定義時，它們表現出遞歸行為:

簡單的基線條件---不使用遞歸產生答案的終止情況

一組規則將所有其他情形縮減到基線條件

例如，以下是某人祖先的遞歸定義:

某人的父母是他的祖先(基線條件)

某人祖先的祖先也是他的祖先(遞歸步驟)

斐波那契數列是遞歸的經典例子:

Fib(0) = 1 基線條件1；

Fib(1) = 1 基線條件2；

對所有整數n,n > 1時：Fib(n) = (Fib(n-1) + Fib(n-2))。

許多數學公理基於遞歸規則。例如，皮亞諾公理對自然數的形式定義可以描述為:0是自然數，每個自然數都有一個後繼數，它也是自然數。通過這種基線條件和遞歸規則，可以生成所有自然數的集合。

遞歸定義的數學對象包括函數、集合，尤其是分形。

遞歸還有多種開玩笑的「定義」。

非正式定義

俄羅斯娃娃或俄羅斯套娃是遞歸概念的一個物理藝術例子。

自1320年喬托的Stefaneschi三聯畫問世以來，遞歸就一直用於繪畫。它的中央面板包含紅衣主教Stefaneschi的跪像，舉著三聯畫本身作為祭品。

M.C. Eschers 印刷畫廊 (1956)描繪了一個扭曲的城市，其中包含一個遞歸包含圖片的畫廊，因此無限。

③ 遞歸演算法是什麼

遞歸演算法（英語：recursion algorithm）在計算機科學中是指一種通過重復將問題分解為同類的子問題而解決問題的方法。

遞歸式方法可以被用於解決很多的計算機科學問題，因此它是計算機科學中十分重要的一個概念。絕大多數編程語言支持函數的自調用，在這些語言中函數可以通過調用自身來進行遞歸。

計算理論可以證明遞歸的作用可以完全取代循環，因此在很多函數編程語言（如Scheme）中謹段習慣用遞歸來實現循環。