1、3.5 用遞歸法解決問題什么是遞歸法從前有座山，山里有座廟，廟里有個老和尚給小和尚講故事，講什么呢？從前有座山，山里有座廟，很久以前，有一則古老而有趣的故事，流傳至今：蘊含了遞歸思想遞歸法包括2種情況：v函數自己調用自己v兩個函數之間相互調用 如果一個函數在定義時，直接或間接地調用了自己，這種算法在程序設計中統稱為遞歸法。函數是為了實現某種功能而編寫的一段相對獨立的程序。自定義函數是指我們自己編寫的函數。 標準函數 自定義函數Abs( ) 、len( )、mid( )、chr( )、asc( )自定義函數自定義函數: : 在在VB中，自定中，自定義義函數函數形式形式如下：如下： Public|

2、Private Function (參數參數列列表表) As 類類型型 局部常量局部常量、變量變量定定義義 語語句句組組 函函數數名名稱稱=返返回值回值 End Function 自定自定義義函數函數的的調調用，可以有用，可以有三種三種格式格式： 變量變量=函函數數名名稱（參數）稱（參數） Call 函函數數名名稱（參數）稱（參數） 函函數數名名稱稱 參數參數子過程的定義Public|private function (參數列表) as 類型 局部常量、變量定義 語句組 函數名稱=返回值End functionpublic|private sub (參數列表) 局部常量、變量定義 過程語句組E

3、nd sub自定義函數：自定義函數：子過程的定義：子過程的定義：private sub s(n As Integer) As Long If n = 1 Then s =1 Else s =s(n-1)*n End IfEnd subPublic Function s(n As Integer) As Long If n = 1 Then s =1 Else s =s(n-1)*n End IfEnd Function比較兩個數的大小比較兩個數的大小 Public Function max(n As Integer) As Integer If ab Then max=a Else max=b

4、 End If End Function Private Sub command_Click() 調用遞歸函數，顯示結果 Print max(3,5) End Sub基本思想: 把規模大的、較難解決的問題變成規模較小的、易解決的同一問題。規模較小的問題又變成規模更小的問題，并且小到一定的程度直到可以直接得出它的解，從而得到原來問題的解。 注意：必須要有一個結束遞歸的條件，不得無限遞歸。分析步驟： 1.決定問題規模的參數。 2.問題的邊界條件及邊界值。 3.解決問題的通式。例:計算一個數的階乘 1!=1 f(1)=1 2!=1*2 f(2)=f(1)*2 3!=1*2*3 f(3)=f(2)*3

5、 4!=1*2*3*4 f(4)=f(3)*4 5!=1*2*3*4*5 f(5)=f(4)*5 . . n!=1*2*3*4*5*.*n f(n)=f(n-1)*n遞歸函數求5！ Public Function s(n As Integer) As Long If n = 1 Then s =1 Else s =s(n-1)*n End If End Function Private Sub form_Click() 調用遞歸函數，顯示結果 Print s(5)=; s(5) End Sub遞歸法的實現遞歸法的實現 有有人人養養了一對了一對兔兔子子，這對，這對兔兔子子以后以后每每月月生生一一

6、對對兔兔子子，新生新生兔兔子子從從第三個第三個月月開始，也是開始，也是每每月月生生一對一對兔兔子子，問，問12個個月月后這后這人人有多少對有多少對新新生生兔兔子子？問題分析問題分析這個問題是公元前13世紀意大利數學家斐波那契的名著算盤書里的問題。圖中每個色塊表示一對兔子，其中白色色塊表示新生兔子。從圖中可以發現，每月新生兔子的對數為：1,1,2,3,5從第三個月起，當月新生兔子數為前兩月新生兔子數之和。這個數列在數學上被稱做“斐波那契數列”。程序實現程序實現這這個個問題如問題如果果不用不用遞歸遞歸法解決，法解決，其其參參考代碼考代碼如下：如下：Private Function Hares(By

7、Val intMonth As Integer) As IntegerDim i As IntegerDim intCurMon As Integer 當當前月新前月新生生兔兔子子對數對數Dim intPreMon1 As Integer 前前一個一個月新月新生生兔兔子子對數對數Dim intPreMon2 As Integer 前前兩個兩個月新月新生生兔兔子子對數對數 前前兩個兩個月月分分別別為為1對對intPreMon1 = 1intPreMon2 = 1 從第從第3月起月起,新新生生兔兔子子為為前前兩兩月月之之和和For i = 3 To intMonthintCurMon = intP

8、reMon2 + intPreMon1intPreMon1 = intPreMon2intPreMon2 = intCurMonNextHares = intCurMonEnd Function用用遞歸遞歸法法實現實現。參參考代碼考代碼如下：如下： Public Function S(N As Integer) As Integer If N = 1 Or N= 2 Then S = 1 Else S = S(N1) + S(N2) End If End Function年齡問題 有5個人做在一起，問第5個人多大了。他說比第四個人大2歲，問第四個人多大了，他說比第三個人大2歲，問第三個人多大了，他說比第二個人大2歲，問第二個人多大了，他說比第一個人大2歲，最后問第一個人，他說他10歲了。請問第5個人多大了？遞歸法的歸納1： 遞歸算法的實質：是把問題轉化為規模縮小了的同類問題的子問題。然后遞歸調用函數(或過程)來表示問題的解。遞歸算法解決問題的特點：(1) 遞歸就是在過程或函數里調用自身。(2) 在使用遞增歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。(3) 遞歸算法解題通常顯得很簡潔，但遞歸算法解題的運行效率較低。所以一般不提倡用遞歸算法設計程序遞歸法的歸納2：遞歸算法所體現的“重復”一般有三個要求：一是每次調用在規模上都有所縮小(