1、遞歸算法與遞歸程序,德羅斯特效應(yīng) （Droste effect） 是遞歸的一種視覺形式， 是指一張圖片的某個部分與整張圖片相同， 如此產(chǎn)生無限循環(huán)。,遞歸算法：是一種直接或者間接地調(diào)用自身的算法。 在定義一個過程或函數(shù)時出現(xiàn)調(diào)用本過程或本函數(shù)的成分，稱之為遞歸。,什么時候調(diào)用遞歸？,問題4-16：著名的意大利數(shù)學(xué)家斐波那契(Fibonacci)在他的著作算盤書中提出了一個“兔子問題”：假定小兔子一個月就可以長成大兔子，而大兔子每個月都會生出一對小兔子。如果年初養(yǎng)了一對小兔子，問到年底時將有多少對兔子? (當(dāng)然得假設(shè)兔子沒有死亡而且嚴格按照上述規(guī)律長大與繁殖),(1)分析問題。,這個表格雖然解決

2、了斐波那契的兔子問題(年底時兔子的總數(shù)是144只)，但仔細觀察一下這個表格，你會發(fā)現(xiàn)兔子的數(shù)目增長得越來越快，如果時間再長，只用列表的方法就會有困難。(例如，你愿意用列表的方法求出5年后兔子的數(shù)目嗎？)我們需要研究表中的規(guī)律，找出一般的方法，去解決這個問題。,仔細研究表4-8，你有些什么發(fā)現(xiàn)？每一個月份的大兔數(shù)、小兔數(shù)與上一個月的數(shù)字有什么聯(lián)系？,每個月的小兔子數(shù)等于上個月的大兔子數(shù)； 每個月的大兔子數(shù)等于上個月的兔子總數(shù)； 從第三個月起： 每個月的兔子總數(shù)等于前兩個月的兔子數(shù)之和。,(2)設(shè)計算法。,“兔子問題”很容易列出一條遞推式而得到解決。假設(shè)第N個月的兔子數(shù)目是F(N)，我們有：,前面

3、學(xué)過：,自定義函數(shù)的定義格式: Function 函數(shù)名(參數(shù)表 ) As type 過程中的代碼 End Function 調(diào)用函數(shù)的格式： 函數(shù)名(參數(shù)表),(3)編寫程序。,Function Fib(ByVal N As Integer) As Long If N 3 Then Fib = 1 Else Fib = Fib(N - 1) + Fib(N - 2) End Function Private Sub Command1_Click() N = Val(Text1.Text) Text2.Text = 第 當(dāng)n=2時， f(2)=3; 當(dāng)n=3時， f(3)=7; 當(dāng)n=4時，

4、f(4)=15;. 不難可以推出f(n)=2n-1。 當(dāng)n=64時， f(64)= 264-1=18446744073709551615 假如每秒鐘一次，共需多長時間呢？一年大約有 31536926 秒，計算表明移完這些金片需要多億年，比地球壽命還要長，事實上，世界、梵塔、廟宇和眾生都已經(jīng)灰飛煙滅。,(1)分析問題。,我們把3根寶石柱分別命名為A、B、C。最初有N個金盤放在A，需要把它們?nèi)堪匆?guī)則移動到B。當(dāng)N=1時，直接把金盤從A搬到B就可以了，1次成功。當(dāng)N2，那么需要利用C柱來過渡。我們假設(shè)已經(jīng)找到一種把N1個金盤從一根柱搬到另外一根柱的方法，那么，我們只要把N1個金盤從A搬到C，然后把

5、最大的金盤從A搬到B，最后把C上的N一1個金盤搬到B就可以了。靠遞歸的思想，我們輕而易舉地完成了整個搬動。,(2)設(shè)計算法。,我們定義一個過程Hanoi(N，A，B，C)，表示有N個金盤需要從A柱搬到B柱(以C柱為過渡)。那么完成它只需3步： Hanoi(N一1，A，C，B)它的意思是把A柱上的N一1個金盤搬到C柱； AB它的意思是把一個(最大的)金盤從A柱搬到B柱； Hanoi(N1，C，B，A)它的意思是把c柱上的N一1個金盤搬到B柱。,前面已經(jīng)學(xué)過：,過程定義的格式： Private Sub 過程名 (參數(shù)表) 代碼 End Sub 調(diào)用過程的格式： Call過程名(參數(shù)表),(3)編寫

6、程序,Private Sub Hanoi(n As Integer, ByVal A As String, ByVal B As String, ByVal C As String, t As Long) If n = 1 Then Text3.Text = Text3.Text + A + + B + vbCrLf t = t + 1 增加變量t用來統(tǒng)計移動次數(shù)。 Else Call Hanoi(n - 1, A, C, B, t) Text3.Text = Text3.Text + A + + B + vbCrLf t = t + 1 Call Hanoi(n - 1, C, B, A,

7、t) End If End Sub Private Sub Command1_Click() Dim t As Long, n As Integer t = 0 n = Val(Text1.Text) A = A B = B C = C Call Hanoi(n, A, B, C, t) Text2.Text = t End Sub,效率分析總結(jié),小結(jié)：,遞歸算法的特點,遞歸過程一般通過函數(shù)或子過程來實現(xiàn)。 遞歸算法：在函數(shù)或子過程的內(nèi)部，直接或者間接地調(diào)用自己的算法。,遞歸算法的實質(zhì),是把問題轉(zhuǎn)化為規(guī)模縮小了的同類問題的子問題。然后遞歸調(diào)用函數(shù)(或過程)來表示問題的解。,遞歸算法解決問題的特點：,(1)遞歸就是在過程或函數(shù)里調(diào)用自身。 (2)在使用遞歸策略時，必須有一個明確的遞歸結(jié)束條件，稱為遞歸出口。 (3)遞歸算法解題通常顯得很簡潔，但遞歸算法解題的運行效率較低。所以一般不提倡用遞歸算法設(shè)計程序。,遞歸算法所體現(xiàn)的“重復(fù)”一般有三個要求：,一是每次調(diào)用在規(guī)模上都有所縮小(通常是減半)； 二是相鄰兩次重復(fù)之間有緊密的聯(lián)系