基礎(chǔ)7月22日pascal語(yǔ)言遞歸

遞歸遞歸概念

當(dāng)過(guò)程或函數(shù)的定義中，其內(nèi)部操作又直接或間接地出現(xiàn)對(duì)自身的調(diào)用，則稱(chēng)這樣的程序嵌套定義為遞歸定義。遞歸是一個(gè)過(guò)程或函數(shù)在其定義或說(shuō)明中又直接或間接調(diào)用自身的一種方法，它通常把一個(gè)大型復(fù)雜的問(wèn)題層層轉(zhuǎn)化為一個(gè)與原問(wèn)題相似的規(guī)模較小的問(wèn)題來(lái)求解，遞歸策略只需少量的程序就可描述出解題過(guò)程所需要的多次重復(fù)計(jì)算，大大地減少了程序的代碼量。遞歸的能力在于用有限的語(yǔ)句來(lái)定義對(duì)象的無(wú)限集合。用遞歸思想寫(xiě)出的程序往往十分簡(jiǎn)潔易懂。例如，在數(shù)學(xué)上，所有偶數(shù)的集合可遞歸地定義為：①0是一個(gè)偶數(shù)；②一個(gè)偶數(shù)與2的和是一個(gè)偶數(shù)?？梢?jiàn)，僅需兩句話就能定義一個(gè)由無(wú)窮多個(gè)元素組成的集合。在程序中，遞歸是通過(guò)函數(shù)或過(guò)程的調(diào)用來(lái)實(shí)現(xiàn)的。函數(shù)或過(guò)程直接調(diào)用其自身，稱(chēng)為直接遞歸；函數(shù)或過(guò)程間接調(diào)用其自身，稱(chēng)為間接遞歸。遞歸應(yīng)用

例1

植樹(shù)節(jié)那天，有五位同學(xué)參加了植樹(shù)活動(dòng)，他們完成植樹(shù)的棵數(shù)都不相同。問(wèn)第一位同學(xué)植了多少棵時(shí)，他指著旁邊的第二位同學(xué)說(shuō)比他多植了兩棵；追問(wèn)第二位同學(xué)，他又說(shuō)比第三位同學(xué)多植了兩棵；…如此，都說(shuō)比另一位同學(xué)多植兩棵，最后問(wèn)到第五位同學(xué)時(shí)，他說(shuō)自己植了10棵。問(wèn)第一位同學(xué)到底植了多少棵樹(shù)？【分析】把原問(wèn)題求第一位同學(xué)的植樹(shù)棵數(shù)a1轉(zhuǎn)化為a1=a2+2，即求a2；而求a2又轉(zhuǎn)化為a2=a3+2;a3=a4+2;a4=a5+2逐層轉(zhuǎn)化為求a2,a3,a4,a5且都采用與求a1相同的方法，最后的a5為已知值，用a5=10返回到上一層并代入計(jì)算出a4；又用a4的值代入上一層去求a3;…,如此,直到求出a1。因此：

10(x=5)Ax=Ax+1+2(x<5)其中求Ax+1

又采用求Ax

的方法。所以:①定義一個(gè)處理問(wèn)題的子程序Num(x)，如果X<5就遞歸調(diào)用子程序Num(x+1);②當(dāng)遞歸調(diào)用到達(dá)一定條件(X=5)，就直接執(zhí)行num:=10，再執(zhí)行后繼語(yǔ)句，遇End返回到調(diào)用子程序的地方。③最后返回到開(kāi)頭的原問(wèn)題，此時(shí)所得到的運(yùn)算結(jié)果就是原問(wèn)題Num(1)的答案。程序如下：Programex6_24_1; //采用函數(shù)編寫(xiě)Functionnum(x:integer):integer;beginifx=5thennum:=10 //遞歸邊界

elsenum:=num(x+1)+2;//遞歸式end;BEGINwriteln('TheNumis',num(1));END.

利用全局變量或變參的形式，也可以傳遞數(shù)據(jù)，下面采用過(guò)程編寫(xiě)。程序如下：Programex1; //采用過(guò)程編寫(xiě)Vara:integer; //定義一個(gè)全局變量a，通過(guò)全局變量傳遞數(shù)值ProcedureNum(x:integer);//過(guò)程N(yùn)um(x)求第x位同學(xué)的棵數(shù)beginifx=5thena:=10 elsebeginNum(x+1);//遞歸調(diào)用過(guò)程N(yùn)um(x+1)a:=a+2;//求(x+1)的棵數(shù)

end;end;BEGINNum(1);//主程序調(diào)用Num(1)求第1個(gè)人的棵數(shù)

writeln(’TheNumis’,a);END.Ex6_24_2程序中的遞歸過(guò)程圖解如下：遞歸方法說(shuō)明如下：①調(diào)用原問(wèn)題的處理子程序（過(guò)程或函數(shù)）時(shí)，調(diào)用程序應(yīng)給出具體的子程序形參值（與形參結(jié)合的實(shí)參）;②在處理子問(wèn)題中，如果又調(diào)用原問(wèn)題的處理子程序，但形參值應(yīng)是不斷改變的量(表達(dá)式);③每遞歸調(diào)用一次自身，系統(tǒng)就打開(kāi)一“層”與自身相同的程序系列;④由于調(diào)用參數(shù)不斷改變，將使條件滿足，此時(shí)就是最后一“層”，不需再調(diào)用自身，而是在本層往下執(zhí)行后繼語(yǔ)句，遇到end，就返回到上“層”調(diào)用此子程序的地方并繼續(xù)往下執(zhí)行，如此直到返回主程序。⑤整個(gè)遞歸過(guò)程可視為由往返雙向“運(yùn)動(dòng)”組成，先是逐層遞進(jìn)，逐層打開(kāi)新的“篇章”，（有可能無(wú)具體計(jì)算值）當(dāng)最終遞進(jìn)達(dá)到邊界，執(zhí)行完本“層”的語(yǔ)句，才由最末一“層”逐次返回到上“層”，每次返回均帶回新的計(jì)算值，直至回到第一次由主程序調(diào)用的地方，完成對(duì)原問(wèn)題的處理。

遞歸算法表現(xiàn)出處理問(wèn)題的強(qiáng)大能力。然而，如同循環(huán)一樣，遞歸也會(huì)帶來(lái)無(wú)終止調(diào)用的可能性，因此，在設(shè)計(jì)遞歸過(guò)程（函數(shù)）時(shí)，必須考慮遞歸調(diào)用的終止問(wèn)題，就是遞歸調(diào)用要受限于某一條件，而且要保證這個(gè)條件在一定情況下肯定能得到滿足。例2

用遞歸函數(shù)求x!

1(x=0)x!=x(x-1)!(x>0)【分析】

根據(jù)數(shù)學(xué)中的定義把求x!定義為求x*(x-1)!,其中求(x-1)!仍采用求x!的方法，需要定義一個(gè)求x！的過(guò)程或函數(shù)，逐級(jí)調(diào)用此過(guò)程或函數(shù)，即：當(dāng)x=0時(shí)，x!=1；當(dāng)x>0時(shí)，x!=x*(x-1)！。假設(shè)用函數(shù)Fac(x)表示x的階乘，當(dāng)x=3時(shí)，F(xiàn)ac(3)的求解方法可表示為：

Fac(3)=3*fac(2)=3*2*Fac(1)=3*2*1*Fac(0)=3*2*1*1=6①定義函數(shù)：fac(n:integer):integer;

如果n=0，則fac:=1;如果n>0，則繼續(xù)調(diào)用函數(shù)fac:=n*fac(n-1);②返回主程序，打印fac(x)的結(jié)果。它的執(zhí)行流程如下圖所示：Fac(3)Fac(2)Fac(1)Fac(0)3*Fac(2)2*Fac(1)1*Fac(0)Fac(0)=1Fac(3)采用函數(shù)編寫(xiě)程序如下：Programex2_1;Varx:integer;Functionfac(n:integer):integer; //函數(shù)fac(n)求n!beginifn=0thenfac:=1elsefac:=n*fac(n-1) //調(diào)用函數(shù)fac(n-1)遞歸求(n-1)!end;BEGINreadln(x);writeln(x,’!=’,fac(x));//主程序調(diào)用fac(x)求x!END.采用過(guò)程編寫(xiě)程序如下：Programex2_2;varx:integer;t:longint;Procedurefac(x:longint);beginifx=1thent:=1elsebeginfac(x-1);t:=t*x;end;end;BEGINread(x);fac(x);writeln(t);END.例3

用遞歸算法求Xn

?！痉治觥堪裍n

分解成：

X0=1

(n=0)X1=X*X0(n=1)X2=X*X1(n>1)X3=X*X2(n>1)……(n>1)

因此將Xn

轉(zhuǎn)化為：X*Xn-1，，其中求Xn-1又用求Xn

的方法進(jìn)行求解。①定義子程序cf(n:integer)求Xn;如果n>1則遞歸調(diào)用cf(n-1)求Xn-1;②當(dāng)遞歸調(diào)用到達(dá)n=0時(shí)終止調(diào)用,然后執(zhí)行本“層”的后繼語(yǔ)句;③遇到子程序中的END就結(jié)束本次的調(diào)用，返回到上一“層”調(diào)用語(yǔ)句的地方，并執(zhí)行其后繼語(yǔ)句;④繼續(xù)執(zhí)行步驟③，從調(diào)用中逐“層”返回，最后返回到主程序。采用函數(shù)編寫(xiě)程序如下：Programex3_1; //采用函數(shù)編寫(xiě)varx,n:integer;Functioncf(n:integer):integer;beginifn=0thencf:=1 //遞歸邊界

elsecf:=x*cf(n-1); //遞歸式end;BEGINreadln(x,n);write(x,'^',n,'is:',cf(n));END.采用過(guò)程編寫(xiě)程序如下：Programex3_2; //采用過(guò)程編寫(xiě)Vartt,x,n:integer;//利用全局變量tt傳遞結(jié)果Procedurecf(n:integer);//過(guò)程cf(n)求xnbeginifn=0thentt:=1elsebegincf(n-1);//遞歸調(diào)用過(guò)程cf(n-1)求xn-1tt:=tt*xend;end;BEGINreadln(x,n);//輸入x,ncf(n);//主程序調(diào)用過(guò)程cf(n)求xnwriteln(x,’^’,n,’=‘,tt);END.例4

用遞歸方法求兩個(gè)數(shù)m和n的最大公約數(shù)。(m>0，n>0)【分析】求兩個(gè)數(shù)的最大公約數(shù)，可以用枚舉因子的方法，從兩者中較小的數(shù)到1枚舉能被兩個(gè)數(shù)同時(shí)整除且是最大的約數(shù)的方法；也可以用輾轉(zhuǎn)相除法，這里采用遞歸實(shí)現(xiàn)輾轉(zhuǎn)相除算法：①求X除以Y的余數(shù);②如果余數(shù)不為0，則讓X=Y，Y=余數(shù)，重復(fù)步驟①，即調(diào)用子程序;③如果余數(shù)為0，則終止調(diào)用子程序;④輸出此時(shí)的Y值。采用函數(shù)編寫(xiě)程序如下：Programex4_1;varm,n,g:integer;Functiongcd(m,n：integer)：integer;varr:integer;beginr:=mmodn;ifr=0thengcd:=nelsegcd:=gcd(n,r);end;BEGIN //主程序

read(m,n);g:=gcd(m,n);writeln(‘m=’,m,’n=’,n,’gcd=’,g);END.采用過(guò)程編寫(xiě)程序如下：Programex4_2;Vara,b,d:integer;Proceduregcd(x,y:nteger);//過(guò)程beginifxmody=0thend:=y //d是用于傳遞結(jié)果的全局變量

elsegcd(y,xmody)//遞歸調(diào)用過(guò)程end;BEGINreadln(a,b);gcd(a,b);writeln(‘m=’,a,’n=’,b,’gcd=’,d);END.運(yùn)行：輸入12848輸出m=128n=48gcd=16輸入6794輸出m=67n=94gcd=1例5

已知一個(gè)一維數(shù)組A[1..N](N<50)，又已知一整數(shù)M。如能使數(shù)組A中任意幾個(gè)元素之和等于M，則輸出YES，反之則為NO。【分析】對(duì)于一個(gè)已確定的數(shù)組a[1]至a[n]和一個(gè)確定的數(shù)m，判斷能否使數(shù)組a中任意幾個(gè)元素之和等于m，等價(jià)于判斷能否從數(shù)組a中取任意數(shù)使其和為m。此時(shí)若a[n]=m，則可以輸出“YES”，否則若n=1，則可以輸出“NO”。否則可以按以下規(guī)則進(jìn)行判斷：對(duì)于a中任意元素a[n]只有取與不取兩種情況：

(１)取a[n]：則此時(shí)問(wèn)題轉(zhuǎn)化為：對(duì)于一個(gè)已確定的數(shù)組a[1]至a[n-1]和一個(gè)確定的數(shù)m-a[n]，判斷能否使數(shù)組a中任意幾個(gè)元素之和等于m-a[n]。

(２)不取a[n]：則此時(shí)問(wèn)題轉(zhuǎn)化為：對(duì)于一個(gè)已確定的數(shù)組a[1]至a[n-1]和一個(gè)確定的數(shù)m，判斷能否使數(shù)組a中任意幾個(gè)元素之和等于m。若用函數(shù)sum(n,m)表示能否從數(shù)組a[1]至a[n]中取任意數(shù)使其和為m，只要sum(n-1,m-a[n])和sum(n-1,m)當(dāng)中有一個(gè)值為真，則sum(n,m)為真，否則為假。因此，可以用遞歸來(lái)解此題。遞歸終止條件為：ifa[n]=mthensum:=trueelseifn=1thensum:=false;采用函數(shù)編寫(xiě)程序如下：Programex5_1;Constmax=50;Vara:array[1..max]ofinteger;n,m,i:integer;Functionsum(n,m:integer):boolean;Beginifa[n]=mthensum:=trueelseifn=1thensum:=falseelsesum:=sum(n-1,m-a[n])orsum(n-1,m);End;Beginreadln(n);fori:=1tondoreadln(a[i]);readln(m);ifsum(n,m)thenwriteln('YES')elsewriteln('NO');End.采用過(guò)程編寫(xiě)程序如下：Programex5_2;Constmax=50;Vara:array[1..max]ofinteger;n,m,i:integer;flag:boolean;Proceduresum(n,m:integer);Beginifa[n]=mthenflag:=true ` //利用全局變量flag傳遞結(jié)果

elseifn=1thenexit //n=1作為遞歸邊界，不再遞歸下去

elsebeginsum(n-1,m-a[n]);sum(n-1,m);end;End;Beginreadln(n);fori:=1tondoreadln(a[i]);readln(m);flag:=false;sum(n,m);ifflagthenwriteln('YES')elsewriteln('NO');End.例6：利用遞歸，將一個(gè)十進(jìn)制整數(shù)K轉(zhuǎn)化為N進(jìn)制整數(shù)（N<=10）。測(cè)試數(shù)據(jù)：輸入：K和N的值193輸出：轉(zhuǎn)化后的N進(jìn)制整數(shù)201programaa;varn,k:integer;proceduretentok(k,n:integer);varr:integer;beginr:=kmodn;

k:=kdivn;ifk<>0thententok(k,n);write(r);end;beginread(k,n);tentok(k,n);writeln;end.判斷運(yùn)行結(jié)果1.programd1;

var

s,n:integer;

functionf(n:integer):integer;

begin

ifn=1thenf:=1

elsef:=n*n+f(n-1);

end;

begin

write('inputn:');readln(n);

s:=f(n);

writeln('f(',n,')=',s)

end.輸入:inputn:3輸出:練習(xí)一2．programd2;

var

a,b:integer;

functionf(n:integer):integer;

begin

ifn=1thenf:=1

elseifn=2thenf:=2

elsef:=f(n-1)+f(n-2);

end;

begin

read(a);

b:=f(a);

writeln(b);

end.輸入:4輸出:3．programd3;

var

a,b,c,d:integer;

procedurep(a:integer;varb:integer);

var

c:integer;

begin

a:=a+1;b:=b+1;c:=2;d:=d+1;

writeln('m',a,b,c,d);

ifa<3thenp(a,b);

writeln('n',a,b,c,d)

end;

begin

a:=1;b:=1;c:=1;d:=1;

writeln('x',a,b,c,d);

p(a,b);

writeln('y',a,b,c,d);

end.練習(xí)2:樓梯有N階臺(tái)階，上樓可以一步上一階，也可以一步上二階，計(jì)算共有多少種不同走法。測(cè)試數(shù)據(jù)：輸入：輸入N的值6輸出：走法總數(shù)13提示：N=1f(1)=1N=2f(2)=2當(dāng)N>=3時(shí)f(N)=f(N-1)+f(N-2)練習(xí)1：讀入一串字符倒序輸出，以字符’&’為結(jié)束標(biāo)志，用過(guò)程來(lái)實(shí)現(xiàn)。練習(xí)題遞歸及其應(yīng)用請(qǐng)計(jì)算ack(m,n)的值。(m,n<=5)例1:已知:ack(m,n)函數(shù)的計(jì)算公式如下:programaa;

var

m,n:longint;

a:longint;

functionack(m,n:longint):longint;

begin

ifm=0thenack:=n+1

elseifn=0thenack:=ack(m-1,1)

elseack:=ack(m-1,ack(m,n-1))

end;

begin

read(m,n);

a:=ack(m,n);

writeln(a);

end.測(cè)試數(shù)據(jù)輸入：34輸出：125其Pascal程序如下：例2:用輾轉(zhuǎn)相除法求兩個(gè)自然數(shù)m,n的最大公約數(shù)。思路：輾轉(zhuǎn)相除法規(guī)定：求兩個(gè)正整數(shù)m,n（m>=n）的最大公約數(shù)，應(yīng)先將m除以n；求得余數(shù)r,如果等于零，除數(shù)n就是m,n的最大公約數(shù)；如果r不等于零，就用n除以r，再看所得余數(shù)是否為零。重復(fù)上面過(guò)程，直到余數(shù)r為零時(shí)，則上一次的余數(shù)值即為m,n的最大公約數(shù)。用其數(shù)學(xué)方式描述如下:programaa;

var

m,n,t:integer;

functionf(m,n:integer):integer;

varr:integer;

begin

if(mmodn)=0thenf:=n

else

begin

r:=mmodn;

f:=f(n,r);

end;

end;begin

readln(m,n);

ifm<nthen

begin

t:=m;

m:=n;

n:=t;

end;

writeln('gd=',f(m,n));end.測(cè)試數(shù)據(jù)輸入：2018輸出：gd=2例3:移盤(pán)子游戲(漢諾塔問(wèn)題)已知有三根針?lè)謩e用1,2,3表示，在1號(hào)針中從小到大放了N個(gè)盤(pán)子，如圖3.2所示，現(xiàn)要求把所有盤(pán)子從1針全部移到3針，移動(dòng)規(guī)則是：允許使用2號(hào)針作為過(guò)渡針，每次只準(zhǔn)移動(dòng)一塊盤(pán)子，且每根針上不能出現(xiàn)大盤(pán)子壓小盤(pán)子的情況。請(qǐng)找出移動(dòng)次數(shù)最少的移動(dòng)方案。思路：假定可以通過(guò)某個(gè)過(guò)程把1針上面的N-1個(gè)盤(pán)搬到過(guò)渡針2中，然后把1針中剩下的1個(gè)盤(pán)移動(dòng)到3針，然后再把過(guò)渡針2中的N-1個(gè)盤(pán)移到3針去，這樣完成了移盤(pán)。思路是很明確的，我們把N個(gè)盤(pán)子移動(dòng)問(wèn)題轉(zhuǎn)化成N-1個(gè)盤(pán)子移動(dòng)問(wèn)題，即如何從1針把N-1個(gè)盤(pán)子移動(dòng)到2針和從2針把N-1個(gè)盤(pán)子移動(dòng)到3針。同理，移N-1個(gè)盤(pán)子問(wèn)題又可以進(jìn)一步簡(jiǎn)化為移N-2盤(pán)子問(wèn)題，這種簡(jiǎn)化過(guò)程實(shí)質(zhì)就是一個(gè)遞歸過(guò)程。但遞歸過(guò)程不能永遠(yuǎn)遞歸下去，必須有邊界條件令過(guò)程停止調(diào)用。顯然，邊界條件是當(dāng)只有一個(gè)盤(pán)子時(shí)，僅需作最后一次移動(dòng)即可。下面為移盤(pán)子游戲PASCAL程序。programaa;

var

n:integer;

proceduremove(n,a,b,c:integer);

begin

ifn=1then

writeln(a,'------>',c)

else

begin

move(n-1,a,c,b);

writeln(a,'------>',c);

move(n-1,b,a,c);

end;

end;

begin

readln(n);

move(n,1,2,3);

end.測(cè)試數(shù)據(jù)：輸入:3輸出:1------>31------>23------>21------>32------>12------>31------>3例4:數(shù)的計(jì)算（1）問(wèn)題描述我們要求找出具有下列性質(zhì)數(shù)的個(gè)數(shù)(包含輸入的自然數(shù)n):先輸入一個(gè)自然數(shù)n(n<=1000),然后對(duì)此自然數(shù)按照如下方法進(jìn)行處理:1、不作任何處理;2、在它的左邊加上一個(gè)自然數(shù),但該自然數(shù)不能超過(guò)原數(shù)的一半;3、加上數(shù)后,繼續(xù)按此規(guī)則進(jìn)行處理,直到不能再加自然數(shù)為止.樣例:

輸入:

6

滿足條件的數(shù)為

6(此部分不必輸出)