【新手進(jìn)階】之七：遞歸算法

roych

       在談遞歸算法之前，不得不提的是斐波納契（Fibonacci）數(shù)列。生于十二世紀(jì)的斐波納契（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ù)學(xué)上解法很多，通項公式是：an=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}，并由此引出了黃金比例等等。當(dāng)我們把通項公式寫成程序則得到以下函數(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

復(fù)制代碼

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

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

復(fù)制代碼

顯然，數(shù)學(xué)不太好的盆友們，一時間未必能推導(dǎo)出通項公式，可如果恰好需要去完成這項任務(wù)，該怎么辦呢？我們只能使用反推法：從數(shù)列中可以看得出來，后一項是前面兩項之和。先得到最后一項，再得到倒數(shù)第二和倒數(shù)第三項，然后再繼續(xù)往前推，直至得到第一項和第二項。于是整個結(jié)果就出來了。
這就是程序上最常用的遞歸思想�，F(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

復(fù)制代碼

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

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

【新手入門】之一：If分支語句
【新手入門】之二：分支語句總結(jié)
【新手入門】之三：循環(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屬性答疑
【新手入門】之二十一：記錄集的“凌遲”——逐條導(dǎo)出記錄集

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

ycxchen

第一個學(xué)習(xí)！

陽春面

學(xué)習(xí)

JosephTan

有興趣，看看。

xie62

學(xué)習(xí)學(xué)習(xí)學(xué)習(xí)

風(fēng)中漫步

那個數(shù)列還真沒聽說過.挺復(fù)雜的.其實在生活中類遞歸的例子真有,如常說的:從前有座山,山上有做廟,廟里有個老和尚在給小和尚講故事,講的什么故事呢?從前有座山,山上有做廟,廟里有個老和尚在給小和尚講故事,......
記得偶上小學(xué)時,班里有個同學(xué)特有才,那時偶根本不知道這叫有才.他寫了篇作文,講述的是他與父親搬磚,"搬了一塊又一塊,搬了一塊又一塊,搬了一塊又一塊,.......",直到達(dá)到老師要求的字?jǐn)?shù)后才停止了調(diào)用.當(dāng)時這篇作文被老師當(dāng)眾批評了.我學(xué)編程后才知道那同學(xué)使用的是遞歸

fnsmydyang

學(xué)習(xí)了，謝謝。

yanghua1900363

學(xué)習(xí)！

風(fēng)中漫步

roych  為什么不是簡單的循環(huán)語句呢？

遞歸的特點是自己調(diào)用自己.

斑竹講到這我也就跟進(jìn)了,這用循環(huán)也可解決的.可能我理解的會有偏差,還請斑竹批評指正了.
這個我對低歸的理解,請大家批評:

Function by(zs As String) As Long
  If Len(zs) > 100 Then   Exit Function
  Text1 = zs
  zs = zs + "搬了一塊又一塊,"
  Call by(zs)
End Function

imono

厲害，旁征博引，說的很清楚，謝謝！