子程序的遞歸與嵌套

子程序的遞歸與嵌套第一頁(yè)，共二十七頁(yè)，編輯于2023年，星期二1、復(fù)習(xí)函數(shù)與過(guò)程——子程序子程序的定義定義位置如何定義？子程序的調(diào)用在何處調(diào)用？如何調(diào)用？參數(shù)的傳遞值傳遞，地址傳遞變量的作用域全局，局部子程序如何返回值到調(diào)用處函數(shù)通過(guò)函數(shù)名帶回值子程序可通過(guò)變量參數(shù)和全局變量的方式帶回值到調(diào)用處第二頁(yè)，共二十七頁(yè)，編輯于2023年，星期二【例1】：輸入一個(gè)正整數(shù)，如果是回文素?cái)?shù)則輸出“Yes”，否則輸出“No”【分析】定義兩個(gè)并列關(guān)系的函數(shù)，分別判斷一個(gè)數(shù)是否為素?cái)?shù)和是否為回文數(shù)教材P93例5-11第三頁(yè)，共二十七頁(yè)，編輯于2023年，星期二注意：1）內(nèi)、外層子程序不得相互交叉，內(nèi)層必須完全嵌套在外層之中；2）一般情況下，在子程序內(nèi)部需要使用的變量應(yīng)在子程序的內(nèi)部進(jìn)行定義。外層子程序不能訪問(wèn)內(nèi)層子程序所定義的變量。【例2】：求組合數(shù)的和。vars:real;functioncnm(n,m:integer):real;functionfac(k:integer):longint;vari:integer;t:real;begint:=1;fori:=2tokdot:=t*i;fac:=t;end;begincnm:=fac(n)/(fac(m)*fac(n-m));end;begins:=cnm(6,3)+cnm(9,5);writeln(‘s=’,s:8:2);end.2、子程序的嵌套：第四頁(yè)，共二十七頁(yè)，編輯于2023年，星期二functionfac(k:integer):longint;vari:integer;t:real;begint:=1;fori:=2tokdot:=t*i;fac:=t;end;functioncnm(n,m:integer):real;begincnm:=fac(n)/(fac(m)*fac(n-m));end;functionfac(k:integer):longint;Forward；functioncnm(n,m:integer):real;begincnm:=fac(n)/(fac(m)*fac(n-m));end;functionfac(k:integer):real;vari:integer;t:real;begint:=1;fori:=2tokdot:=t*i;fac:=t;end;超前引用第五頁(yè)，共二十七頁(yè)，編輯于2023年，星期二【例3】：求組合數(shù)（）/7！的和。vars:real;functionfac(k:integer):longint;vari:integer;t:longint;begint:=1;fori:=2tokdot:=t*i;fac:=t;end;functioncnm(n,m:integer):real;begincnm:=fac(n)/(fac(m)*fac(n-m));end;begins:=cnm(6,3)+cnm(9,5);writeln(‘s=’,(s/fac(7)):8:2);end.學(xué)校舉行晚會(huì)，要從M個(gè)學(xué)生中選N個(gè)學(xué)生到舞臺(tái)上表演一個(gè)游戲，問(wèn)有多少種選擇方法。這是數(shù)學(xué)中的組合運(yùn)算，可用下列公式計(jì)算：第六頁(yè)，共二十七頁(yè)，編輯于2023年，星期二3.遞歸調(diào)用：①遞歸的定義：

Pascal語(yǔ)言中，如果在一個(gè)函數(shù)、過(guò)程等的定義或說(shuō)明內(nèi)部又直接或間接地出現(xiàn)有對(duì)自身的引用，則稱它們是遞歸的或者是遞歸定義的。例如：在數(shù)學(xué)上，所有偶數(shù)的集合可遞歸地定義為：0是一個(gè)偶數(shù)；一個(gè)偶數(shù)和2的和是一個(gè)偶數(shù)?？梢?jiàn)，僅需兩句話就能定義一個(gè)由無(wú)窮多個(gè)元素組成的集合。②遞歸的實(shí)現(xiàn)：通過(guò)函數(shù)或過(guò)程的調(diào)用來(lái)實(shí)現(xiàn)。函數(shù)或過(guò)程直接調(diào)用其自身，稱為直接遞歸；函數(shù)或過(guò)程間接調(diào)用其自身，稱為間接遞歸。直接遞歸間接遞歸第七頁(yè)，共二十七頁(yè)，編輯于2023年，星期二遞歸應(yīng)用

【例5】、植樹(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)的答案。第八頁(yè)，共二十七頁(yè)，編輯于2023年，星期二程序如下：Programex5; Functionnum(x:integer):integer;//采用函數(shù)編寫(xiě)beginifx=5thennum:=10 //遞歸邊界

elsenum:=num(x+1)+2;//遞歸式end;BEGINwriteln('TheNumis',num(1));END.程序執(zhí)行過(guò)程？【例6】、猴子吃棗問(wèn)題：猴子摘了一堆棗，第一天吃了一半，還嫌不過(guò)癮，又吃了一個(gè)；第二天，又吃了剩下的一半零一個(gè)；以后每天如此。到第十天，猴子一看只剩下一個(gè)了。問(wèn)最初有多少個(gè)棗子？要求：寫(xiě)出遞推表達(dá)式，嘗試用遞推函數(shù)編寫(xiě)程序第九頁(yè)，共二十七頁(yè)，編輯于2023年，星期二課堂練習(xí)1、programlx1(input,output);vars,n:integer;functionf(n:integer):integer;

begin

ifn=1thenf:=1elsef:=n*n+f(n-1)

end;begin

write(‘inputn:’);readln(n);s:=f(n);writeln(‘f(’,n,‘)=’,s)end.該程序的功能是：

。當(dāng)n的值為６時(shí)，程序的運(yùn)行結(jié)果是：

第十頁(yè)，共二十七頁(yè)，編輯于2023年，星期二②在處理子問(wèn)題時(shí)，如果又調(diào)用原問(wèn)題的處理子程序，但形參值應(yīng)是不斷改變的量(表達(dá)式);遞歸方法說(shuō)明如下：①調(diào)用原問(wèn)題的子程序（過(guò)程或函數(shù)）時(shí)，調(diào)用程序應(yīng)給出具體的子程序形參值（與形參結(jié)合的實(shí)參）;遞歸算法表現(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è)條件在一定情況下肯定能得到滿足。⑤整個(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)題的處理。④由于調(diào)用參數(shù)不斷改變，將使條件滿足，此時(shí)就是最后一“層”，不需再調(diào)用自身，而是在本層往下執(zhí)行后繼語(yǔ)句，遇到end，就返回到上“層”調(diào)用此子程序的地方并繼續(xù)往下執(zhí)行，如此直到返回主程序③每遞歸調(diào)用一次自身，系統(tǒng)就打開(kāi)一“層”與自身相同的程序系列;第十一頁(yè)，共二十七頁(yè)，編輯于2023年，星期二如何設(shè)計(jì)遞歸算法？1.確定遞歸公式2.確定邊界(終了)條件課堂練習(xí)2：求：1+2+3+...+n的值。n從鍵盤(pán)上輸入。有一對(duì)雌雄兔,每?jī)蓚€(gè)月就繁殖雌雄各一對(duì)兔子.問(wèn)n個(gè)月后共有多少對(duì)兔子?用遞歸的方法求Xn（X和n由鍵盤(pán)輸入）已知:數(shù)列1,1,2,4,7,13,24,44,...求數(shù)列的第n項(xiàng).第十二頁(yè)，共二十七頁(yè)，編輯于2023年，星期二n!1n=0n(n-1)!n>0【例7】：用遞歸計(jì)算n!n!可以由下面公式表示：varn,s:integer;functionfac(a:integer):integer;beginifa=0thenfac:=1elsefac:=a*fac(a-1);end;beginreadln(n);s:=fac(n);writeln(n,‘!=’,s)end.使用遞歸求解問(wèn)題，通?？梢詫⒁粋€(gè)比較大的問(wèn)題層層轉(zhuǎn)化為一個(gè)與原問(wèn)題相類似的、規(guī)模較小的問(wèn)題進(jìn)行求解，最終達(dá)到對(duì)原問(wèn)題的求解。第十三頁(yè)，共二十七頁(yè)，編輯于2023年，星期二棧……fac(5)=5*……fac(5)=5*fac(4)=4*fac(3)=3*……fac(5)=5*fac(4)=4*……fac(5)=5*fac(4)=4*fac(3)=3*fac(2)=2*fac(5)=5*fac(4)=4*fac(3)=3*fac(2)=2*fac(1)=1*fac(5)=5*fac(4)=4*fac(3)=3*fac(2)=2*fac(0)=1fac(1)=1*第十四頁(yè)，共二十七頁(yè)，編輯于2023年，星期二遞歸過(guò)程【例8】：把一個(gè)十進(jìn)制整數(shù)轉(zhuǎn)換成K進(jìn)制數(shù)(k<10)。Knumber8157819820532第十五頁(yè)，共二十七頁(yè)，編輯于2023年，星期二分析根據(jù)數(shù)制轉(zhuǎn)換規(guī)則，把一個(gè)十進(jìn)制整數(shù)轉(zhuǎn)換成K進(jìn)制數(shù)，要用“除K取余”法。也就是用K依次去除這個(gè)數(shù)及其商，所得余數(shù)依次作為K進(jìn)制數(shù)相繼的低位數(shù)字，一直到商為0即可。如果我們不用數(shù)組存儲(chǔ)每次求得的低位數(shù)字，怎么讓程序按順序輸出K進(jìn)制的各位數(shù)字？第十六頁(yè)，共二十七頁(yè)，編輯于2023年，星期二分析可以用遞歸的方法實(shí)現(xiàn)這一過(guò)程。算法過(guò)程tentok(number,k)如下：步一digitnumbermodk;步二numbernumberdivk步三如果number不為0則調(diào)用

tentok(number,k)步四輸出digit第十七頁(yè)，共二十七頁(yè)，編輯于2023年，星期二參考程序：programconvert(input,output);varnumber,k:integer;proceduretentok(number,k:Integer);vardigit:integer;begindigit:=numbermodk;number:=numberdivk;ifnumber<>0thententok(number,k);write(digit);end;beginwrite('Enternumberandconvertedbasisk(2-9):');readln(number,k);tentok(number,k);writeln;end.第十八頁(yè)，共二十七頁(yè)，編輯于2023年，星期二執(zhí)行過(guò)程分析第2次調(diào)用digit=3number=2tentok(2,8)第1次調(diào)用digit=5number=19tentok(19,8)Tentok(157,8)第3次調(diào)用digit=2number=0write(digit)write(digit)write(digit)Knumber8157819820532第十九頁(yè)，共二十七頁(yè)，編輯于2023年，星期二遞歸結(jié)構(gòu)的優(yōu)點(diǎn)：結(jié)構(gòu)清晰、容易閱讀和理解。遞歸結(jié)構(gòu)的缺點(diǎn)：需要保留每次遞歸調(diào)用時(shí)的參數(shù)和局部變量，占用內(nèi)存大，耗費(fèi)機(jī)時(shí)多，程序運(yùn)行的效率較低。遞歸算法的實(shí)用情況：1.符合遞歸的描述：需要解決的問(wèn)題可以化為子問(wèn)題求解，而子問(wèn)題求解的方法與原問(wèn)題相同，只是數(shù)量增大或減少。2.遞歸調(diào)用的次數(shù)是有限的。3.必須有遞歸結(jié)束的條件。第二十頁(yè)，共二十七頁(yè)，編輯于2023年，星期二例9、漢諾塔問(wèn)題有n個(gè)半徑各不相同的圓盤(pán)，按半徑從大到小，自下而上依次套在A柱上，另外還有B、C兩根空柱。要求將A柱上的n個(gè)圓盤(pán)全部搬到C柱上去，每次只能搬動(dòng)一個(gè)盤(pán)子，且必須始終保持每根柱子上是小盤(pán)在上，大盤(pán)在下。在移動(dòng)盤(pán)子的過(guò)程當(dāng)中發(fā)現(xiàn)要搬動(dòng)n個(gè)盤(pán)子，必須先將n-1個(gè)盤(pán)子從A柱搬到B柱去，再將A柱上的最后一個(gè)盤(pán)子搬到C柱，最后從B柱上將n-1個(gè)盤(pán)子搬到C柱去。搬動(dòng)n個(gè)盤(pán)子和搬動(dòng)n-1個(gè)盤(pán)子時(shí)的方法是一樣的，當(dāng)盤(pán)子搬到只剩一個(gè)時(shí)，遞歸結(jié)束。源柱工作柱目標(biāo)柱ABC第二十一頁(yè)，共二十七頁(yè)，編輯于2023年，星期二vara,b,c,number:integer;proceduremove(n:integer;a,b,c:char);begin

ifn=1thenwriteln(a,'->',c)

else

begin

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

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

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

end;end;begin

write('thenumberofdish:');

readln(number);

move(number,’A’,’B’,’C’);end.第二十二頁(yè)，共二十七頁(yè)，編輯于2023年，星期二【例10】求找出具有下列性質(zhì)的數(shù)的個(gè)數(shù)(包含輸入的自然數(shù)n)：先輸入一個(gè)自然數(shù)n(n<=500),然后對(duì)此自然數(shù)按照如下方法進(jìn)行處理:①.不作任何處理;②.在它的左邊加上一個(gè)自然數(shù),但該自然數(shù)不能超過(guò)原數(shù)的一半;③.加上數(shù)后,繼續(xù)按此規(guī)則進(jìn)行處理,直到不能再加自然數(shù)為止.樣例:

輸入:

6滿足條件的數(shù)為

6

16

26

126

36

136輸出:

6

varn,i:integer;

s:real;procedureqiu(x:integer);vark:integer;begin

ifx<>0then

begin

s:=s+1;

fork:=1toxdiv2doqiu(k)

endend;begin

readln(n);

s:=0;

qiu(n);

writeln(s:2:0)end.第二十三頁(yè)，共二十七頁(yè)，編輯于2023年，星期二【例11】、求m與n的最大公約數(shù)分析：從數(shù)學(xué)上可以知道求m與n的最大公約數(shù)等價(jià)于求n與(mmodn)的最大公約數(shù)。這時(shí)可以把n當(dāng)作新的m,(mmodn)當(dāng)作新的n，這樣問(wèn)題又變成了求新的m與n的最大公約數(shù)……這種方法我們稱為輾轉(zhuǎn)相除法。設(shè)兩個(gè)整數(shù)分別為m和n，將m整除n得到一個(gè)余數(shù)r，若r=0，則除數(shù)n就是最大公約數(shù)，否則，將除數(shù)作為被除數(shù)，余數(shù)作為除數(shù)繼續(xù)相除，直到余數(shù)=0為止。

Var

m,n:integer;

functiongys(a,b:integer):integer;

var

r:integer;

begin

r:=amodb;

ifr=0thengys:b

elsegys:=gys(b,r);

end;

begin

readln(m,n);

writeln(‘gysis:’,gys(m,n));

end.第二十四頁(yè)，共二十七頁(yè)，編輯于2023年，星期二【分析】對(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)表