3.3　遞推算法思想

遞推算法是很常用的算法思想，在數(shù)學計算等方面有著廣泛的應用。遞推算法適合有著明顯公式規(guī)律的場合。

3.3.1　遞推算法基本思想

遞推算法是一種理性思維模式的代表，其根據(jù)已有的數(shù)據(jù)和關系，逐步推導而得到結果。遞推算法的執(zhí)行過程如下：

（1）根據(jù)已知結果和關系，求解中間結果。

（2）判定是否達到要求，如果沒有達到，則繼續(xù)根據(jù)已知結果和關系求解中間結果；如果滿足要求，則表示尋找到一個正確的答案。

遞推算法往往需要用戶知道答案和問題之間的邏輯關系。在許多數(shù)學問題中，都有著明確的計算公式可以遵循，因此往往可以采用遞推算法來實現(xiàn)。

3.3.2　遞推算法實例

遞推算法是基本的算法思想，常用于數(shù)學相關的場合。下面通過一個簡單的數(shù)學例子來分析遞推算法的應用。

數(shù)學里面的斐波那契數(shù)列便是一個使用遞推算法的經(jīng)典例子。13世紀意大利數(shù)學家斐波那契的《算盤書》中記載了典型的兔子產仔問題，其大意如下：

如果一對兩個月大的兔子以后每一個月都可以生一對小兔子，而一對新生的兔子出生兩個月后才可以生小兔子。也就是說，1月份出生，3月份才可產仔。那么假定一年內沒有發(fā)生兔子死亡事件，那么1年后共有多少對兔子呢？

1.遞推算法

先來分析一下兔子產仔問題。逐月分析每月的兔子對數(shù)。

第1個月：1對兔子；

第2個月：1對兔子；

第3個月：2對兔子；

第4個月：3對兔子；

第5個月：5對兔子；

……

從上述內容可以看出，從第3個月開始，每個月的兔子總對數(shù)等于前兩個月兔子數(shù)的總和。相應的計算公式如下：

第n個月兔子總數(shù)Fn=Fn-2+Fn-1。

這里，初始第1個月的兔子數(shù)為F1=1，第2個月的兔子數(shù)為F2=1。

可以通過遞歸公式來求解。為了通用性的方便，可以編寫一個算法，用于計算斐波那契數(shù)列問題。并按照這個思路來編寫相應的兔子產仔問題的求解算法，代碼示例如下：

在上述代碼中，輸入?yún)?shù)為經(jīng)歷的時間，即月數(shù)。程序中通過遞歸調用來實現(xiàn)斐波那契數(shù)列的計算。

2.地推算法求解兔子產仔問題

根據(jù)上述通用的兔子產仔問題算法，可以求解任意該類問題。下面給出完整的兔子產仔問題求解程序代碼：

【程序3-2】

在該程序中，首先由用戶輸入時間，即月數(shù)。然后調用fibonacci方法求解計算兔子產仔問題。最后輸出結果。執(zhí)行該程序，用戶輸入12，執(zhí)行結果如圖3-2所示?？梢姡?jīng)過12個月的時間，共有144對兔子。