遞歸算法在ＶＢ程序設(shè)計中的實現(xiàn)

1、遞歸算法在程序設(shè)計中的實現(xiàn)                遞歸是一種十分有用代寫論文的程序設(shè)計技術(shù)。在VB程序設(shè)計中，遞歸在算法的描述中被經(jīng)常采 用，很多問題可以用遞歸算法求解。例如，有些問題的定義形式本身就是遞歸的，如階乘函 數(shù)和Fibonacci數(shù)列等；有些數(shù)據(jù)結(jié)構(gòu)，如二叉樹、廣義表等，由于結(jié)構(gòu)本身固有的遞歸特 性，所以對它們的操作可以遞歸進(jìn)行；還有一類，雖然問題本身沒有明顯的遞歸結(jié)構(gòu)，但用 遞歸技術(shù)求解比其他方法更容易，如最經(jīng)典的漢諾塔問題和八皇后問

2、題等。另外，由于遞歸 算法省略了程序設(shè)計中的許多細(xì)節(jié)操作，簡化了程序設(shè)計過程，使得在求解許多復(fù)雜問題時 ，采用遞歸算法比不用遞歸算法要簡單得多，并且程序結(jié)構(gòu)清晰、易讀，正確性容易驗證， 這給用戶編制程序和調(diào)試程序帶來很大方便。因此，掌握遞歸程序設(shè)計方法很有必要。但由 于遞歸的設(shè)計思想比較巧妙，特別是對于規(guī)模較大的問題，掌握遞歸的算法的設(shè)計分析和實 現(xiàn)過程是比較困難的，而且相關(guān)教程對該部分內(nèi)容介紹的篇幅甚少，因此，有必要對其進(jìn)行 深入探討，分析其概念及算法結(jié)構(gòu)特點，分析其設(shè)計方法和實現(xiàn)過程，以此來幫助學(xué)生加深 對遞歸算法思想的進(jìn)一步理解，學(xué)會正確的應(yīng)用遞歸解決實際問題。 一、遞歸算法的概念 計算

3、機(jī)要完成人們預(yù)先定義的工作，首先應(yīng)該設(shè)計完成這個工作的步驟和方法，即算法 。然后再根據(jù)算法編寫程序。算法是問題的求解過程的精確描述，求解一個問題往往有多種 算法可供選擇，選擇標(biāo)準(zhǔn)首先是算法的正確性、可靠性、可讀性等，其次是算法所需存儲空 間和時間的消耗。算法設(shè)計是一件非常復(fù)雜的事情，在處理實際問題時，為了更好地將復(fù)雜 的問題變得簡單，在設(shè)計算法時常常采用遞歸的方法。 所謂遞歸，就是指用自身的結(jié)構(gòu)來描述自身，以實現(xiàn)層次數(shù)據(jù)結(jié)構(gòu)的查詢和訪問。用遞 歸概念來描述的算法就稱為遞歸算法。遞歸算法常用于遞歸調(diào)用方面，即子過程或函數(shù)自己 調(diào)用自己。VB允許一個自定義子過程或函數(shù)過程在過程體(又稱子程序體)的

4、內(nèi)部調(diào)用自己， 這樣的子過程或函數(shù)就叫遞歸子過程或遞歸函數(shù)。 遞歸調(diào)用必須是有限的，有限才有意義。所以在進(jìn)行算法描述時必須設(shè)置相關(guān)的控制條 件，使其成為有限。這可以通過條件語句(If語句)來實現(xiàn)，即只有在設(shè)定的條件成立時遞歸 才繼續(xù)，否則終止遞歸。可見，構(gòu)成遞歸必須滿足以下條件：1)有明確的結(jié)束遞歸的邊界 條件(又稱終止條件)以及結(jié)束時的邊界值；2)過程的描述中包含其本身，即能用遞歸形式 表示，且遞歸向終止條件發(fā)展。 二、遞歸算法的設(shè)計方法 遞歸算法既是一種有效的算法設(shè)計方法，也是一種有效的分析問題的方法。遞歸算法求 解問題的基本思想是：對于較為復(fù)雜的問題，把原問題分解成若干個相對簡單且類同的

5、子問 題，這樣原問題就可遞推得到求解。 當(dāng)一個問題存在上述構(gòu)成遞歸的條件時，該問題便可以利用遞歸算法進(jìn)行處理。具體的 設(shè)計方法是：當(dāng)所求解問題難于直接求解時，首先，把問題分解成若干個難度較小、較容易 求解的子問題，子問題與原問題具有類同的結(jié)構(gòu)。如果子問題能夠直接求解，則解之；如果 子問題仍不能直接求解，將每個子問題再分解成若干個更簡單的子問題，直到分解出的子問 題能夠很容易地求解或解為已知，這是實現(xiàn)遞歸的模板。然后，設(shè)計遞歸出口(即結(jié)束遞歸 的邊界條件)，在滿足出口條件時，遞歸函數(shù)不能再調(diào)用自己，必須返回一個確定的值。將 這兩個方面的問題分析好之后，就可以在子程序體中定義遞歸調(diào)用了。 在通常情

6、況下，遞歸調(diào)用都是要受到條件控制的，而且在被調(diào)用的過程中，會對調(diào)用條 件進(jìn)行有規(guī)律的修改，直到滿足邊界條件，返回邊界值，結(jié)束遞歸；然后按照原來的路徑逐 層返回，求出原問題的解。由此可知，遞歸算法設(shè)計的關(guān)鍵在于遞歸描述和遞歸終止條件。   三、遞歸算法的實現(xiàn)過程 遞歸算法的執(zhí)行過程是不斷地自調(diào)用，直到到達(dá)遞歸出口才結(jié)束。然后，遞歸算法開始 按最后調(diào)用的過程最先返回的次序逐層返回，返回到最外層的調(diào)用語句時遞歸算法執(zhí)行過程 結(jié)束。可見，遞歸的實現(xiàn)過程包含了“調(diào)用”和“返回”兩個階段。 許多問題都是可以利用遞歸算法進(jìn)行求解的。VB中一個最常用例子就是計算階乘。例如 ，用遞歸函數(shù)實現(xiàn)計算N!的

7、求解。代碼 Private Sub FormClick() Dim N As Integer,F As Long N=InputBox(“輸入一個正整數(shù)：”) F=Fact(N) 函數(shù)調(diào)用 Print N；“!=”;F End Sub Private Function Fact(ByVal N As Integer)As Long If N=0 Or N=1 Then Fact=1 Else          Fact=N*Fact Fact(N-1) 函數(shù)遞歸調(diào)用 End If End Function 運行程序

8、，單擊窗體執(zhí)行Form Click()事件過程，鍵盤輸入3賦給變量N，即求3!的值。 程序以Fact(N)形式調(diào)用函數(shù)Fact。當(dāng)函數(shù)Fact開始運行時，首先檢測傳遞過來的參數(shù) N值 是否為1，若為1，則函數(shù)返回值為1;若不為1，函數(shù)執(zhí)行賦值語句Fact=N*Fact(N-1)。函數(shù) 調(diào)用傳遞的參數(shù)N是3，函數(shù)計算表達(dá)式3*Fact(3-1)值，由于表達(dá)式中還有函數(shù)調(diào)用，于是V B第二次調(diào)用Fact函數(shù)，但傳遞的參數(shù)是2，函數(shù)計算表達(dá)式2*Fact(2-1)值。當(dāng)再一次調(diào)用 此函數(shù)時，參數(shù)值為1，因此函數(shù)返回值1到本次調(diào)用點，此調(diào)用函數(shù)又返回2的值到調(diào)用這 個調(diào)用函數(shù)的函數(shù)；最后，最初被調(diào)用的

9、函數(shù)返回6到調(diào)用它的過程，得到運行結(jié)果。遞歸 函數(shù)Fact的調(diào)用和返回過程如圖1所示。 圖1 遞歸函數(shù)Fact的調(diào)用從圖1可以看出，一個遞歸問題可以分為“調(diào)用”和“返回”兩個階段。當(dāng)進(jìn)入調(diào)用階 段后，便逐層向下調(diào)用，因此Fact函數(shù)被調(diào)用3次，即Fact（3)、Fact(2)、Fact(1)，直到 遇到終止條件(即當(dāng)N=1時Fact=1)。然后帶著終止條件所給的函數(shù)值進(jìn)入返回階段。按照原 來的路徑逐層返回，由Fact(1)推出Fact(2)，由Fact(2)推出Fact(3)為止。 一般來講，從算法描述的角度看，遞歸算法通常有兩種實現(xiàn)方法。一種是在遞歸函數(shù)中用遞 歸公式實現(xiàn)。上述的計算階乘就是

10、一個使用遞歸公式的常用例子，其中Fact=N*Fact（N-1) 就是遞歸公式。再如，求Fibonacci數(shù)列的問題，也是通過遞歸公式來實現(xiàn)遞歸調(diào)用的。其 遞歸函數(shù)代碼段 圖2 漢諾塔(hanoi)問題Private Function Fab(ByVal N As Integer)As Long If N=1 Or N=2 Then Fab=1 遞歸出口 Else Fab=Fab(N-2)+Fab(N-1) 遞歸公式 End If End Function 有些問題無法直接使用遞歸公式，而要通過一個遞歸過程來描述。例如，大家所熟知的 漢諾塔問題：有A、B、C三個塔座，A塔上有直徑從小到大的N個

11、盤子(如圖2所示)，要求借助 塔B將N個盤子由A移到C，且保證：每次只移動一個盤子，任何時刻不能把大盤子置于小盤子 之上。 此問題可以用一個遞歸過程描述：(1)借助C，將（N-1）個盤子從A座移動到B座：(2)將 最后一個盤子(最下端的)從A座移動到C座：(3）滯助A，將(N-1)個盤子從B座移動到 C座。 依據(jù)以上分析，(1)和(3)步屬于同類問題，只是參數(shù)值不同而已。由此可寫出遞歸算法 ，并用VB程序描述的遞歸過程代碼段 Private Sub MoveDisk(N As Integer,A As String，B As String,C As String) If N=1 Then Pr

12、int “將第1個圓盤從第”&A&“座移到第”&C&“座” Else Call MoveDisk(N-1，A，C，B) 過程遞歸調(diào)用 Print“將第”&N&“個圓盤從第”&A&“座移到第”n&C&“座” Call MoveDisk(N-1，B，A，C) 過程遞歸調(diào)用 End If End Sub 此程序根據(jù)對問題的遞歸描述寫出，結(jié)構(gòu)清楚，易理解。因涉及遞歸，所以其調(diào)用的執(zhí)行過 程可能很復(fù)雜。但如果不用遞歸方法，問題又可能很難處理。因此，在算法描述過程中，只 需把以上算法的三步過程設(shè)計好，再考慮一個盤子時的情況(遞

13、歸出口)怎樣處理就可以了。 從上述分析中，可以認(rèn)為，看問題能否用遞歸算法，先不要考慮具體的執(zhí)行過程，只要滿足 上述 構(gòu)成遞歸的條件即可。在VB程序設(shè)計中使用遞歸時還應(yīng)注意，在定義遞歸函數(shù) 或遞歸過程時，一般先使用If語句進(jìn)行遞歸測試，找到遞歸結(jié)束的條件，然后再進(jìn)行遞歸調(diào) 用。 以上示例是遞歸應(yīng)用的典型。很多人認(rèn)為遞歸不易理解，這是把遞歸狹隘化了，但是對 遞歸的理解不能因此受到限制，遞歸程序的復(fù)雜程度比一般程序要高很多。遞歸算法使程序 清晰直觀，是程序設(shè)計中很重要的方面，但遞歸在計算機(jī)中的執(zhí)行過程卻很復(fù)雜，需要占用 較大的內(nèi)存空間和較多的系統(tǒng)時間來進(jìn)行頻繁進(jìn)出和轉(zhuǎn)移操作，執(zhí)行效率很低。所以，在VB 程序設(shè)計過程中，并不一味追求遞歸。如果一個問題的求解過程明顯是遞推規(guī)律或通過循 環(huán)處理方法即可方便解決的，則不必要使用遞歸。反之，在對問題進(jìn)行分解、求解的過程中 得到的是和原問題性質(zhì)相同的子問題，由此自然得到一個遞歸算法，且它比實現(xiàn)非遞歸算法 更符合