遞歸算法在ＶＢ程序設計中的實現

1、遞歸算法在程序設計中的實現遞歸是一種非常有用代寫論文的程序設計技術。在VB程序設計中，遞歸在算法的描繪中被經常采用，很多問題可以用遞歸算法求解。例如，有些問題的定義形式本身就是遞歸的，如階乘函數和Fibnai數列等；有些數據構造，如二叉樹、廣義表等，由于構造本身固有的遞歸特性，所以對它們的操作可以遞歸進展；還有一類，雖然問題本身沒有明顯的遞歸構造，但用遞歸技術求解比其他方法更容易，如最經典的漢諾塔問題和八皇后問題等。另外，由于遞歸算法省略了程序設計中的許多細節(jié)操作，簡化了程序設計過程，使得在求解許多復雜問題時，采用遞歸算法比不用遞歸算法要簡單得多，并且程序構造明晰、易讀，正確性容易驗證，這給用

2、戶編制程序和調試程序帶來很大方便。因此，掌握遞歸程序設計方法很有必要。但由于遞歸的設計思想比擬巧妙，特別是對于規(guī)模較大的問題，掌握遞歸的算法的設計分析和實現過程是比擬困難的，而且相關教程對該局部內容介紹的篇幅甚少，因此，有必要對其進展深化討論，分析其概念及算法構造特點，分析其設計方法和實現過程，以此來幫助學生加深對遞歸算法思想的進一步理解，學會正確的應用遞歸解決實際問題。一、遞歸算法的概念計算機要完成人們預先定義的工作，首先應該設計完成這個工作的步驟和方法，即算法。然后再根據算法編寫程序。算法是問題的求解過程的準確描繪，求解一個問題往往有多種算法可供選擇，選擇標準首先是算法的正確性、可靠性、可

3、讀性等，其次是算法所需存儲空間和時間的消耗。算法設計是一件非常復雜的事情，在處理實際問題時，為了更好地將復雜的問題變得簡單，在設計算法時常常采用遞歸的方法。所謂遞歸，就是指用自身的構造來描繪自身，以實現層次數據構造的查詢和訪問。用遞歸概念來描繪的算法就稱為遞歸算法。遞歸算法常用于遞歸調用方面，即子過程或函數自己調用自己。VB允許一個自定義子過程或函數過程在過程體(又稱子程序體)的內部調用自己，這樣的子過程或函數就叫遞歸子過程或遞歸函數。遞歸調用必須是有限的，有限才有意義。所以在進展算法描繪時必須設置相關的控制條件，使其成為有限。這可以通過條件語句(If語句)來實現，即只有在設定的條件成立時遞歸

4、才繼續(xù)，否那么終止遞歸?？梢姡瑯嫵蛇f歸必須滿足以下條件：1)有明確的完畢遞歸的邊界條件(又稱終止條件)以及完畢時的邊界值；2)過程的描繪中包含其本身，即能用遞歸形式表示，且遞歸向終止條件開展。二、遞歸算法的設計方法遞歸算法既是一種有效的算法設計方法，也是一種有效的分析問題的方法。遞歸算法求解問題的根本思想是：對于較為復雜的問題，把原問題分解成假設干個相對簡單且類同的子問題，這樣原問題就可遞推得到求解。當一個問題存在上述構成遞歸的條件時，該問題便可以利用遞歸算法進展處理。詳細的設計方法是：當所求解問題難于直接求解時，首先，把問題分解成假設干個難度較孝較容易求解的子問題，子問題與原問題具有類同的構

5、造。假如子問題可以直接求解，那么解之；假如子問題仍不能直接求解，將每個子問題再分解成假設干個更簡單的子問題，直到分解出的子問題可以很容易地求解或解為，這是實現遞歸的模板。然后，設計遞歸出口(即完畢遞歸的邊界條件)，在滿足出口條件時，遞歸函數不能再調用自己，必須返回一個確定的值。將這兩個方面的問題分析好之后，就可以在子程序體中定義遞歸調用了。在通常情況下，遞歸調用都是要受到條件控制的，而且在被調用的過程中，會對調用條件進展有規(guī)律的修改，直到滿足邊界條件，返回邊界值，完畢遞歸；然后按照原來的途徑逐層返回，求出原問題的解。由此可知，遞歸算法設計的關鍵在于遞歸描繪和遞歸終止條件。三、遞歸算法的實現過程

6、遞歸算法的執(zhí)行過程是不斷地自調用，直到到達遞歸出口才完畢。然后，遞歸算法開場按最后調用的過程最先返回的次序逐層返回，返回到最外層的調用語句時遞歸算法執(zhí)行過程完畢?？梢姡f歸的實現過程包含了“調用和“返回兩個階段。許多問題都是可以利用遞歸算法進展求解的。VB中一個最常用例子就是計算階乘。例如，用遞歸函數實現計算N!的求解。代碼如下：PrivateSubFrlik()DiNAsInteger,FAsLngN=InputBx(“輸入一個正整數：)F=Fat(N)函數調用PrintN；“!=;FEndSubPrivateFuntinFat(ByValNAsInteger)AsLngIfN=0rN=1T

7、henFat=1Else轉貼于論文聯盟.ll.Fat=N*FatFat(N-1)函數遞歸調用EndIfEndFuntin運行程序，單擊窗體執(zhí)行Frlik()事件過程，鍵盤輸入3賦給變量N，即求3!的值。程序以Fat(N)形式調用函數Fat。當函數Fat開場運行時，首先檢測傳遞過來的參數N值是否為1，假設為1，那么函數返回值為1;假設不為1，函數執(zhí)行賦值語句Fat=N*Fat(N-1)。函數調用傳遞的參數N是3，函數計算表達式3*Fat(3-1)值，由于表達式中還有函數調用，于是VB第二次調用Fat函數，但傳遞的參數是2，函數計算表達式2*Fat(2-1)值。當再一次調用此函數時，參數值為1，因

8、此函數返回值1到本次調用點，此調用函數又返回2的值到調用這個調用函數的函數；最后，最初被調用的函數返回6到調用它的過程，得到運行結果。遞歸函數Fat的調用和返回過程如圖1所示。圖1遞歸函數Fat的調用從圖1可以看出，一個遞歸問題可以分為“調用和“返回兩個階段。當進入調用階段后，便逐層向下調用，因此Fat函數被調用3次，即Fat3)、Fat(2)、Fat(1)，直到遇到終止條件(即當N=1時Fat=1)。然后帶著終止條件所給的函數值進入返回階段。按照原來的途徑逐層返回，由Fat(1)推出Fat(2)，由Fat(2)推出Fat(3)為止。一般來講，從算法描繪的角度看，遞歸算法通常有兩種實現方法。一

9、種是在遞歸函數中用遞歸公式實現。上述的計算階乘就是一個使用遞歸公式的常用例子，其中Fat=N*FatN-1)就是遞歸公式。再如，求Fibnai數列的問題，也是通過遞歸公式來實現遞歸調用的。其遞歸函數代碼段如下：圖2漢諾塔(hani)問題PrivateFuntinFab(ByValNAsInteger)AsLngIfN=1rN=2ThenFab=1遞歸出口ElseFab=Fab(N-2)+Fab(N-1)遞歸公式EndIfEndFuntin有些問題無法直接使用遞歸公式，而要通過一個遞歸過程來描繪。例如，大家所熟知的漢諾塔問題：有A、B、三個塔座，A塔上有直徑從小到大的N個盤子(如圖2所示)，要求

10、借助塔B將N個盤子由A移到，且保證：每次只挪動一個盤子，任何時刻不能把大盤子置于小盤子之上。此問題可以用一個遞歸過程描繪：(1)借助，將N-1個盤子從A座挪動到B座：(2)將最后一個盤子(最下端的)從A座挪動到座：(3滯助A，將(N-1)個盤子從B座挪動到座。根據以上分析，(1)和(3)步屬于同類問題，只是參數值不同而已。由此可寫出遞歸算法，并用VB程序描繪的遞歸過程代碼段如下：PrivateSubveDisk(NAsInteger,AAsString，BAsString,AsString)IfN=1ThenPrint“將第1個圓盤從第A“座移到第“座ElseallveDisk(N-1，A，B

11、)過程遞歸調用Print“將第N“個圓盤從第A“座移到第n“座allveDisk(N-1，B，A，)過程遞歸調用EndIfEndSub此程序根據對問題的遞歸描繪寫出，構造清楚，易理解。因涉及遞歸，所以其調用的執(zhí)行過程可能很復雜。但假如不用遞歸方法，問題又可能很難處理。因此，在算法描繪過程中，只需把以上算法的三步過程設計好，再考慮一個盤子時的情況(遞歸出口)怎樣處理就可以了。從上述分析中，可以認為，看問題能否用遞歸算法，先不要考慮詳細的執(zhí)行過程，只要滿足上述構成遞歸的條件即可。在VB程序設計中使用遞歸時還應注意，在定義遞歸函數或遞歸過程時，一般先使用If語句進展遞歸測試，找到遞歸完畢的條件，然后

12、再進展遞歸調用。以上例如是遞歸應用的典型。很多人認為遞歸不易理解，這是把遞歸狹隘化了，但是對遞歸的理解不能因此受到限制，遞歸程序的復雜程度比一般程序要高很多。遞歸算法使程序明晰直觀，是程序設計中很重要的方面，但遞歸在計算機中的執(zhí)行過程卻很復雜，需要占用較大的內存空間和較多的系統(tǒng)時間來進展頻繁進出和轉移操作，執(zhí)行效率很低。所以，在VB程序設計過程中，并不一味追求遞歸。假如一個問題的求解過程明顯是遞推規(guī)律或通過循環(huán)處理方法即可方便解決的，那么不必要使用遞歸。反之，在對問題進展分解、求解的過程中得到的是和原問題性質一樣的子問題，由此自然得到一個遞歸算法，且它比實現非遞歸算法更符合人們的思維邏輯，那么應該使用遞歸。因此，使用