【新手進階】之七：遞歸算法

roych

       在談遞歸算法之前，不得不提的是斐波納契（Fibonacci）數(shù)列。生于十二世紀的斐波納契（Leonardo Fibonacci）曾提到這樣一個問題：有一對兔子，如果每個月生一對小兔子，而剛生下來的兔子兩個月后同樣每個月生一對小兔子，那么，一對兔子一年內(nèi)總共能生下幾對兔子？
      1……第一個月
      1……第二個月
      2……第三個月，產(chǎn)下第一只兔子（仔兔的第一個月）。
      3……第四個月，產(chǎn)下第二只兔子（仔兔的第二個月）。
      5……第五個月，產(chǎn)下第三只兔子，仔兔產(chǎn)下第一只兔子（仔兔的第三個月）。
      ……………………………………………………………………
     于是得到這樣一個數(shù)列：1,1,2,3,5,8,13,21……這在數(shù)學上解法很多，通項公式是：an=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}，并由此引出了黃金比例等等。當我們把通項公式寫成程序則得到以下函數(shù)：

1. Function GetF(N As Long)
   
2. GetF = (Sqr(5) / 5) * (((1 + Sqr(5)) / 2) ^ N - ((1 - Sqr(5)) / 2) ^ N)
   
3. End Function

復制代碼

我們需要獲取具體值（例如a5）時，就可以直接調(diào)用了：

1. Sub Test()
   
2. Debug.Print GetF(5)
   
3. End Sub

復制代碼

顯然，數(shù)學不太好的盆友們，一時間未必能推導出通項公式，可如果恰好需要去完成這項任務，該怎么辦呢？我們只能使用反推法：從數(shù)列中可以看得出來，后一項是前面兩項之和。先得到最后一項，再得到倒數(shù)第二和倒數(shù)第三項，然后再繼續(xù)往前推，直至得到第一項和第二項。于是整個結果就出來了。
這就是程序上最常用的遞歸思想。現(xiàn)在我們開始寫函數(shù)：

1. Function Fibonacci(N As Long)
   
2. If N = 1 Or N = 2 Then Fibonacci = 1
   
3. If N >= 3 Then Fibonacci = Fibonacci(N - 1) + Fibonacci(N - 2)
   
4. End Function

復制代碼

這顯然比用通項公式解答起來簡單多了。以N=4時為例，運行過程大體如下：
      Fibonacci（4）→Fibonacci（3）+Fibonacci（2）→Fibonacci（2）+Fibonacci（1）+Fibonacci（2）→1+1+1=3
      記得前些日子ycxchen提及，在Access中這些是如何應用的。其實這個算法在Access里也是可以用得上的，常見于樹控件中。Kangking同志曾在《程序界面兼工具欄、樹、狀態(tài)欄、頁標簽及進度條等控件的應用》里就用過它來展開子節(jié)點，有興趣的版友可以去看看。
       這里給一個比較簡單的作業(yè)，用遞歸思想寫一個階乘的函數(shù)。

游客，如果您要查看本帖隱藏內(nèi)容請回復

【新手入門】之一：If分支語句
【新手入門】之二：分支語句總結
【新手入門】之三：循環(huán)語句For
【新手入門】之四：循環(huán)語句Do和死循環(huán)
【新手入門】之五：公共變量與傳址過程、傳值過程
【新手入門】之六：“悲歡離合總無情”——淺談Split和Join
【新手入門】之七：嵌套與并列——再談If流程問題
【新手入門】之八：“連就連”——淺談“&”和“+”連接符的區(qū)別
【新手入門】之九：從百錢百雞談起——淺談“規(guī)劃求解”兼答lingjiang問
【新手入門】之十：書到用時方恨少——自定義菜單（Access 2003）的制作
【新手入門】之十一：淺談ADO之序言
【新手入門】之十二：淺談ADO之Connection
【新手入門】之十三：淺談ADO之Conmmand（上）
【新手入門】之十四：淺談ADO之Command（下）
【新手入門】之十五：淺談ADO之Recordset（上）
【新手入門】之十六：淺談ADO之Recordset（下）
【新手入門】之十七：淺談列表框的使用
【新手入門】之十八：雙擊列表框修改數(shù)據(jù)
【新手入門】之十九：從“書與女友恕不外借”談起——淺談“Bookmark”的使用
【新手入門】之二十：“書與書簽”——bookmark屬性答疑
【新手入門】之二十一：記錄集的“凌遲”——逐條導出記錄集

【新手進階】之一：基礎算法（一）
【新手進階】之二：基礎算法（二）
【新手進階】之三：基礎算法（三）
【新手進階】之四：基礎算法（四）
【新手進階】之五：排序搜索（一）
【新手進階】之六：排序搜索（二）
【新手進階】之七：遞歸算法
【新手進階】之八：冒泡排序
【新手進階】之九：淺談不綁定數(shù)據(jù)源操作記錄
【新手進階】之十：工作日的計算
【新手進階】之十一：“庖丁解�！焙汀凹o昌學射”——淺談表格式文本數(shù)據(jù)的導入
【新手進階】之十二：從四腳騰空的奔馬談起——原來界面可以這樣設計
【新手進階】之十三：Outlook風格導航界面
【新手進階】之十四：倉庫管理系統(tǒng)

cclxf

學習學習！

heqing3000

:):):):):):):):):)

XH8608208

學習學習

hxx3970

學習一下

ej1213

學習

miaoiyangzhi

66666學習

72310

新手回復

anttsy

111111111

wenbin_zheng

學習