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

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

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

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

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

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

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

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

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

9、種是在遞歸函數(shù)中用遞歸公式實現(xiàn)。上述的計算階乘就是一個使用遞歸公式的常用例子，其中Fat=N*FatN-1)就是遞歸公式。再如，求Fibnai數(shù)列的問題，也是通過遞歸公式來實現(xiàn)遞歸調(diào)用的。其遞歸函數(shù)代碼段如下：圖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座挪動到座。根據(jù)以上分析，(1)和(3)步屬于同類問題，只是參數(shù)值不同而已。由此可寫出遞歸算法，并用VB程序描繪的遞歸過程代碼段如下：PrivateSubveDisk(NAsInteger,AAsString，BAsString,AsString)IfN=1ThenPrint“將第1個圓盤從第A“座移到第“座ElseallveDisk(N-1，A，B

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

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