遞歸算法與棧

1、遞歸算法及在計(jì)算機(jī)中的實(shí)現(xiàn)1、 遞歸算法例1、用遞歸算法把任一給定的十進(jìn)制正整數(shù)（<=32000）轉(zhuǎn)換成八進(jìn)制數(shù)輸出，程序如下：var m:integer;procedure tran(n:integer); 遞歸過(guò)程var k:integer;begink:=n mod 8;n:=n div 8;if n<>0 then tran(n);write(k:1)end;begin 主程序write('input m:');readln(m);write(m,'=(');tran(m);writeln(')8');readln;en

2、d.輸入：m=765 下劃線表示輸入輸出：765=（1375）8例2、用遞歸算法求N階乘（N！=1*2*3*N,N<20）；var n:integer;function f(n:integer):longint; 遞歸函數(shù)，N=20時(shí)，超過(guò)maxlongintbeginif n=0 then f:=1else f:=n*f(n-1)end;begin 主程序write('input n:');readln(n);write(n,'!=',f(n);end.2、 遞歸在計(jì)算機(jī)中的實(shí)現(xiàn)計(jì)算機(jī)執(zhí)行遞歸算法時(shí)，是通過(guò)棧來(lái)實(shí)現(xiàn)的。具體說(shuō)來(lái)，就是在（遞歸過(guò)程或遞歸函數(shù)

3、）開(kāi)始運(yùn)行時(shí)，系統(tǒng)首先為遞歸建立一個(gè)棧，該棧的元素類型（數(shù)據(jù)域）包括值參、局部變量和返回地址；在每次執(zhí)行遞歸調(diào)用語(yǔ)句時(shí)之前，自動(dòng)把本算法中所使用的值參和局部變量的當(dāng)前值以及調(diào)用后的返回地址壓棧（一般形象地稱為“保存現(xiàn)場(chǎng)”，以便需要時(shí)“恢復(fù)現(xiàn)場(chǎng)”返回到某一狀態(tài)），在每次遞歸調(diào)用結(jié)束后，又自動(dòng)把棧頂元素（各個(gè)域）的值分別賦給相應(yīng)的值參和局部變量（出棧），以便使它們恢復(fù)到調(diào)用前的值，接著無(wú)條件轉(zhuǎn)向（返回）由返回地址所指定的位置繼續(xù)執(zhí)行算法。具體到上面的例1中，當(dāng)遇到遞歸調(diào)用tran(n)時(shí)，系統(tǒng)首先為后面的遞歸調(diào)用建立一個(gè)含有3個(gè)域（值參n，局部變量k和一個(gè)返回地址）的棧；在每次執(zhí)行遞歸調(diào)用tran

4、(n)前，系統(tǒng)自動(dòng)把n和k的當(dāng)前值以及write(k:1)語(yǔ)句的開(kāi)始位置（即調(diào)用結(jié)束后的返回地址）壓棧；在每次執(zhí)行到最后的end語(yǔ)句（即一次遞歸調(diào)用結(jié)束）后，又自動(dòng)把棧頂?shù)呐cn和k對(duì)應(yīng)的值分別賦給n和k（出棧），接著無(wú)條件轉(zhuǎn)向write(k:1)語(yǔ)句的開(kāi)始位置繼續(xù)向下執(zhí)行程序。3、 遞歸的缺點(diǎn)早期操作系統(tǒng)DOS的內(nèi)核是限制只能使用640K內(nèi)存（當(dāng)時(shí)的機(jī)器內(nèi)存也很?。?，在此之上的BP運(yùn)行時(shí)，可用的所有內(nèi)存空間最大也只能為640K，其中程序代碼、常量、變量和堆棧（局部變量、子程序參數(shù)、返回地址；即遞歸中的棧）各占64K，在BP中的OPTIONS菜單的MEMORY SIZE子菜單中可以修改STACK

5、 SIZE至多到64K（一般設(shè)置為65520），可以解決很多遞歸程序遇到的棧溢出錯(cuò)誤。但有時(shí)還是不夠，這時(shí)就想用640K以內(nèi)（64K以上）的多余空間，方法是手工開(kāi)辟一個(gè)?？臻g模擬系統(tǒng)處理遞歸的實(shí)現(xiàn)方法，這樣就可以把一個(gè)遞歸過(guò)程轉(zhuǎn)換成非遞歸過(guò)程，一方面可以進(jìn)一步加深對(duì)棧和遞歸的理解，另一方面也可以解決一些遞歸無(wú)法解決的問(wèn)題。但帶來(lái)的問(wèn)題是程序會(huì)很復(fù)雜。遞歸轉(zhuǎn)換為非遞歸設(shè)P是一個(gè)遞歸算法，假定P中共有m個(gè)值參和局部變量，共有t處遞歸調(diào)用P的語(yǔ)句，則把P改寫成一個(gè)非遞歸算法的一般規(guī)則為：1、 定義一個(gè)棧S，用來(lái)保存每次遞歸調(diào)用前值參和局部變量的當(dāng)前值以及調(diào)用后的返回地址。即S應(yīng)該含有m+1個(gè)域，且S

6、的深度必須足夠大，使得遞歸過(guò)程中不會(huì)發(fā)生棧溢出。2、 定義t+2個(gè)語(yǔ)句標(biāo)號(hào)，其中用一個(gè)標(biāo)號(hào)標(biāo)在原算法中的第一條語(yǔ)句上，用另一個(gè)標(biāo)號(hào)標(biāo)在作返回處理的第一條語(yǔ)句上，其余t個(gè)標(biāo)號(hào)標(biāo)在t處遞歸調(diào)用的返回地址，分別標(biāo)在相應(yīng)的語(yǔ)句上。3、 把每一個(gè)遞歸調(diào)用語(yǔ)句改寫成如下形式：（1） 把值參和局部變量的當(dāng)前值以及調(diào)用后的返回地址壓入棧；（2） 把值參所對(duì)應(yīng)的實(shí)在參數(shù)表達(dá)式的值賦給值參變量；（3） 無(wú)條件轉(zhuǎn)向原算法的第一條語(yǔ)句；4、 在算法結(jié)束前增加返回處理，當(dāng)棧非空時(shí)做：（1） 出棧；（2） 把原棧頂中前m個(gè)域的值分別賦給各對(duì)應(yīng)的值參和局部變量；（3） 無(wú)條件轉(zhuǎn)向由本次返回地址所指定的位置；5、 增設(shè)一個(gè)同

7、S棧的成分類型（元素）相同的變量，作為進(jìn)出棧的緩沖變量，對(duì)于遞歸函數(shù)，還需要再增設(shè)一個(gè)保存函數(shù)值中間結(jié)果的臨時(shí)變量，用這個(gè)變量替換函數(shù)體中的所有函數(shù)名，待函數(shù)結(jié)束之前，在把這個(gè)變量的值賦給函數(shù)名返回。6、 在原算法的第一條語(yǔ)句之前，增加一條把棧置空的語(yǔ)句。7、 對(duì)于遞歸函數(shù)而言，若某條賦值語(yǔ)句中包含兩處或多處遞歸調(diào)用（假設(shè)為n處），則應(yīng)首先把它拆成n條賦值語(yǔ)句，使得每條賦值語(yǔ)句只包含一處遞歸調(diào)用，同時(shí)對(duì)增加的n-1條賦值語(yǔ)句，要增設(shè)n-1個(gè)局部變量，然后按以上六條規(guī)則轉(zhuǎn)換成非遞歸函數(shù)。應(yīng)用舉例例3、把例1中的遞歸過(guò)程改寫成非遞歸過(guò)程。procedure tran(n:integer); 非遞歸

8、過(guò)程label 1,2,3; 因?yàn)橹挥?處遞歸調(diào)用，所以定義t+2=3個(gè)標(biāo)號(hào)type node=record 定義棧的成分類型，因?yàn)橹祬⒑途植孔兞抗?個(gè)，所以m+1=3個(gè)域 n:integer; 值參n 的域k:integer; 局部變量k的域r:integer; 返回地址的域end;stack=record 定義一個(gè)棧類型，包括數(shù)據(jù)域（一個(gè)數(shù)組）和一個(gè)棧頂指針域 vec:array1.7 of node; 32000以內(nèi)的十進(jìn)制正整數(shù)轉(zhuǎn)換成八進(jìn)制數(shù)，不會(huì)超過(guò)七位數(shù)，數(shù)組元素類型為node類型top:integer; 棧頂指針end;var s:stack; 定義棧變量x:node; 進(jìn)出棧的

9、緩沖變量k:integer; 原來(lái)的局部變量procedure push(var s:stack;x:node); 進(jìn)棧過(guò)程，注意s 一定要定義成變量型參數(shù) begin 因?yàn)闂５淖兓獛С鲞^(guò)程if s.top=7 then begin write('up-overflow');exit;endelse begin s.top:=s.top+1;s.vecs.top:=x;end;end;procedure pop(var s:stack;var x:node); 出棧過(guò)程，都要定義成變量型參。一方面出棧的元素存放在x中要帶出過(guò)程，另外棧頂指針也變化了，所以s也要定義成變量型參

10、beginif s.top=0 then begin write('down-overflow');exit;endelse begin x:=s.vecs.top;s.top:=s.top-1;end;end;begins.top:=0; 按照第6條1:k:=n mod 8; 按照第2條的紅色語(yǔ)句n:=n div 8;if n<>0 then begin 按照第3條，3個(gè)步驟，本題不需要第（2）小句x.n:=n;x.k:=k;x.r:=2;push(s,x); （1）goto 1; （3）end;2:write(k:1); 按照第2條的藍(lán)色語(yǔ)句3:if s.top

11、>0 then begin 按照第4條，3個(gè)步驟pop(s,x); （1）n:=x.n;k:=x.k; （2）goto 2; （3）end;end; 建議：?jiǎn)尾礁櫢鱾€(gè)變量，觀察理解過(guò)程例4、把例2中的遞歸函數(shù)改寫成非遞歸函數(shù)function f(n:integer):longint; 非遞歸函數(shù)label 1,2,3;var s:array1.20 of integer;棧，必須大于等于n，保證不溢出top:integer; 棧頂f1:longint; 保存中間結(jié)果的臨時(shí)變量begintop:=0; 棧的初始化1:if n=0 then begin f1:=1;goto 3;end 遇

12、到邊界就結(jié)束轉(zhuǎn)返回處理else begin top:=top+1; 否則，進(jìn)棧atop:=n;n:=n-1; 實(shí)參減1goto 1; 轉(zhuǎn)向開(kāi)始，繼續(xù)end;2:f1:=n*f1; 根據(jù)n和f(n-1),求f(n)3:if top>0 then begin n:=atop; 做返回處理top:=top-1;goto 2; 轉(zhuǎn)向返回地址end;f:=f1; 賦值end;注意：1、 上面的程序其實(shí)已經(jīng)進(jìn)行了簡(jiǎn)化，一是棧只設(shè)置了一個(gè)保存值參n的域，二是忽略了緩沖變量，而直接用n，三是省略了返回地址，因?yàn)槊總€(gè)遞歸調(diào)用的返回地址都相同；2、 以上算法中，從標(biāo)號(hào)1到goto 1所構(gòu)成的循環(huán)，實(shí)際上是一

13、個(gè)遞推過(guò)程；從n推到0為止；從標(biāo)號(hào)2到goto 2所構(gòu)成的循環(huán)是一個(gè)回代過(guò)程；3、 假設(shè)n=5，請(qǐng)大家畫出棧的變化情況。小結(jié)思考從以上可以看出，遞歸算法簡(jiǎn)單直觀，是整個(gè)計(jì)算機(jī)算法和程序設(shè)計(jì)領(lǐng)域一個(gè)非常重要的方面，必須熟練掌握和應(yīng)用它。但計(jì)算機(jī)的執(zhí)行過(guò)程比較復(fù)雜，需要用系統(tǒng)棧進(jìn)行頻繁的進(jìn)出棧操作和轉(zhuǎn)移操作。遞歸轉(zhuǎn)化為非遞歸后，可以解決一些空間上不夠的問(wèn)題，但程序太復(fù)雜。所以，并不是一切遞歸問(wèn)題都要設(shè)計(jì)成非遞歸算法。實(shí)際上，很多稍微復(fù)雜一點(diǎn)的問(wèn)題（比如：二叉樹(shù)的遍歷、圖的遍歷、快速排序等），不僅很難寫出它們的非遞歸過(guò)程，而且即使寫出來(lái)也非常累贅和難懂。在這種情況下，編寫出遞歸算法是最佳選擇，有時(shí)比

14、較簡(jiǎn)單的遞歸算法也可以用迭代加循環(huán)或棧加循環(huán)的方法去實(shí)現(xiàn)。如：function f(n:integer):integer; 求第n個(gè)fibonacci數(shù)，迭代+循環(huán)var I,f1:integer;begini:=0;f1:=1;while i<n do begin i:=i+1;f1:=i*f1; end;f:=f1;end;procedure tran(n:integer);例1改寫成：棧+循環(huán)var s:array1.7 of integer;I,top:integer;BeginTop:=0;While n<>0 doBeginTop:=top+1;stop:=n m

15、od 8;n:=n div 8;end;for i:=top downto 1 do write(si:1);End;棧與回溯法由于回溯法采用的也是遞歸算法，所以在實(shí)現(xiàn)時(shí)也是用棧實(shí)現(xiàn)的。當(dāng)然，回溯法的程序也可以改成非遞歸的、用棧模擬執(zhí)行。比如下面的這個(gè)程序是驗(yàn)證“四色原理”的，請(qǐng)你改寫成非遞歸算法。const num=20; 最多20個(gè)區(qū)域var a:array 1.num,1.num of 0.1;用鄰接矩陣表示圖，0表示兩個(gè)區(qū)域不相鄰，1表示相鄰s:array 1.num of 0.4; 用1-4分別代表RBWY四種顏色;0代表末填進(jìn)任何顏色k1,k2,n:integer;function

16、 pd(i,j:integer):boolean;判斷可行性：第I個(gè)區(qū)域填上第J種顏色var k:integer;beginfor k:=1 to i-1 doif (ai,k=1) and (j=sk) 區(qū)域I和J相鄰且將填進(jìn)的顏色和已有的顏色相同then begin pd:=false; exit; end;pd:=true;end;procedure print;打印結(jié)果var k:integer;beginfor k:=1 to n do 將數(shù)字轉(zhuǎn)為RBWY串輸出case sk of1:write('R':4);2:write('B':4);3:writ

17、e('W':4);4:write('Y':4);end;writeln;end;procedure try(i:integer); 遞歸回溯var j:integer;beginfor j:=1 to 4 doif pd(i,j) then beginsi:=j;if i=n then printelse try(i+1);si:=0;end;end;BEGIN 主程序，輸入一個(gè)圖的鄰接矩陣，輸出一種“四色”填色方案write('please input city number: '); readln(n);writeln('please input the relation of