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

roych

       在談遞歸算法之前，不得不提的是斐波納契（Fibonacci）數(shù)列。生于十二世紀(jì)的斐波納契（Leonardo Fibonacci）曾提到這樣一個(gè)問(wèn)題：有一對(duì)兔子，如果每個(gè)月生一對(duì)小兔子，而剛生下來(lái)的兔子兩個(gè)月后同樣每個(gè)月生一對(duì)小兔子，那么，一對(duì)兔子一年內(nèi)總共能生下幾對(duì)兔子？
      1……第一個(gè)月
      1……第二個(gè)月
      2……第三個(gè)月，產(chǎn)下第一只兔子（仔兔的第一個(gè)月）。
      3……第四個(gè)月，產(chǎn)下第二只兔子（仔兔的第二個(gè)月）。
      5……第五個(gè)月，產(chǎn)下第三只兔子，仔兔產(chǎn)下第一只兔子（仔兔的第三個(gè)月）。
      ……………………………………………………………………
     于是得到這樣一個(gè)數(shù)列：1,1,2,3,5,8,13,21……這在數(shù)學(xué)上解法很多，通項(xiàng)公式是：an=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}，并由此引出了黃金比例等等。當(dāng)我們把通項(xià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）時(shí)，就可以直接調(diào)用了：

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

復(fù)制代碼

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

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

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

【新手入門】之一：If分支語(yǔ)句
【新手入門】之二：分支語(yǔ)句總結(jié)
【新手入門】之三：循環(huán)語(yǔ)句For
【新手入門】之四：循環(huán)語(yǔ)句Do和死循環(huán)
【新手入門】之五：公共變量與傳址過(guò)程、傳值過(guò)程
【新手入門】之六：“悲歡離合總無(wú)情”——淺談Split和Join
【新手入門】之七：嵌套與并列——再談If流程問(wèn)題
【新手入門】之八：“連就連”——淺談“&”和“+”連接符的區(qū)別
【新手入門】之九：從百錢百雞談起——淺談“規(guī)劃求解”兼答lingjiang問(wèn)
【新手入門】之十：書到用時(shí)方恨少——自定義菜單（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ì)算
【新手進(jìn)階】之十一：“庖丁解�！焙汀凹o(jì)昌學(xué)射”——淺談表格式文本數(shù)據(jù)的導(dǎo)入
【新手進(jìn)階】之十二：從四腳騰空的奔馬談起——原來(lái)界面可以這樣設(shè)計(jì)
【新手進(jìn)階】之十三：Outlook風(fēng)格導(dǎo)航界面
【新手進(jìn)階】之十四：倉(cāng)庫(kù)管理系統(tǒng)

ycxchen

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

陽(yáng)春面

學(xué)習(xí)

JosephTan

有興趣，看看。

xie62

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

風(fēng)中漫步

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

fnsmydyang

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

yanghua1900363

學(xué)習(xí)！

風(fēng)中漫步

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

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

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

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

imono

厲害，旁征博引，說(shuō)的很清楚，謝謝！