子程序的遞歸與嵌套

子程序的遞歸與嵌套第1頁，課件共27頁，創(chuàng)作于2023年2月1、復習函數(shù)與過程——子程序子程序的定義定義位置如何定義？子程序的調(diào)用在何處調(diào)用？如何調(diào)用？參數(shù)的傳遞值傳遞，地址傳遞變量的作用域全局，局部子程序如何返回值到調(diào)用處函數(shù)通過函數(shù)名帶回值子程序可通過變量參數(shù)和全局變量的方式帶回值到調(diào)用處第2頁，課件共27頁，創(chuàng)作于2023年2月【例1】：輸入一個正整數(shù)，如果是回文素數(shù)則輸出“Yes”，否則輸出“No”【分析】定義兩個并列關(guān)系的函數(shù)，分別判斷一個數(shù)是否為素數(shù)和是否為回文數(shù)教材P93例5-11第3頁，課件共27頁，創(chuàng)作于2023年2月注意：1）內(nèi)、外層子程序不得相互交叉，內(nèi)層必須完全嵌套在外層之中；2）一般情況下，在子程序內(nèi)部需要使用的變量應在子程序的內(nèi)部進行定義。外層子程序不能訪問內(nèi)層子程序所定義的變量?！纠?】：求組合數(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、子程序的嵌套：第4頁，課件共27頁，創(chuàng)作于2023年2月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;超前引用第5頁，課件共27頁，創(chuàng)作于2023年2月【例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.學校舉行晚會，要從M個學生中選N個學生到舞臺上表演一個游戲，問有多少種選擇方法。這是數(shù)學中的組合運算，可用下列公式計算：第6頁，課件共27頁，創(chuàng)作于2023年2月3.遞歸調(diào)用：①遞歸的定義：

Pascal語言中，如果在一個函數(shù)、過程等的定義或說明內(nèi)部又直接或間接地出現(xiàn)有對自身的引用，則稱它們是遞歸的或者是遞歸定義的。例如：在數(shù)學上，所有偶數(shù)的集合可遞歸地定義為：0是一個偶數(shù)；一個偶數(shù)和2的和是一個偶數(shù)。可見，僅需兩句話就能定義一個由無窮多個元素組成的集合。②遞歸的實現(xiàn)：通過函數(shù)或過程的調(diào)用來實現(xiàn)。函數(shù)或過程直接調(diào)用其自身，稱為直接遞歸；函數(shù)或過程間接調(diào)用其自身，稱為間接遞歸。直接遞歸間接遞歸第7頁，課件共27頁，創(chuàng)作于2023年2月遞歸應用

【例5】、植樹節(jié)那天，有五位同學參加了植樹活動，他們完成植樹的棵數(shù)都不相同。問第一位同學植了多少棵時，他指著旁邊的第二位同學說比他多植了兩棵；追問第二位同學，他又說比第三位同學多植了兩棵；…如此，都說比另一位同學多植兩棵，最后問到第五位同學時，他說自己植了10棵。問第一位同學到底植了多少棵樹？【分析】把原問題求第一位同學的植樹棵數(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返回到上一層并代入計算出a4；又用a4的值代入上一層去求a3;…,如此,直到求出a1。因此：

10(x=5)Ax=Ax+1+2(x<5)其中求Ax+1又采用求Ax的方法。所以:①定義一個處理問題的子程序Num(x)，如果X<5就遞歸調(diào)用子程序Num(x+1);②當遞歸調(diào)用到達一定條件(X=5)，就直接執(zhí)行num:=10，再執(zhí)行后繼語句，遇End返回到調(diào)用子程序的地方。③最后返回到開頭的原問題，此時所得到的運算結(jié)果就是原問題Num(1)的答案。第8頁，課件共27頁，創(chuàng)作于2023年2月程序如下：Programex5; Functionnum(x:integer):integer;//采用函數(shù)編寫beginifx=5thennum:=10 //遞歸邊界

elsenum:=num(x+1)+2;//遞歸式end;BEGINwriteln('TheNumis',num(1));END.程序執(zhí)行過程？【例6】、猴子吃棗問題：猴子摘了一堆棗，第一天吃了一半，還嫌不過癮，又吃了一個；第二天，又吃了剩下的一半零一個；以后每天如此。到第十天，猴子一看只剩下一個了。問最初有多少個棗子？要求：寫出遞推表達式，嘗試用遞推函數(shù)編寫程序第9頁，課件共27頁，創(chuàng)作于2023年2月課堂練習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.該程序的功能是：

。當n的值為６時，程序的運行結(jié)果是：

第10頁，課件共27頁，創(chuàng)作于2023年2月②在處理子問題時，如果又調(diào)用原問題的處理子程序，但形參值應是不斷改變的量(表達式);遞歸方法說明如下：①調(diào)用原問題的子程序（過程或函數(shù)）時，調(diào)用程序應給出具體的子程序形參值（與形參結(jié)合的實參）;遞歸算法表現(xiàn)出處理問題的強大能力。然而，如同循環(huán)一樣，遞歸也會帶來無終止調(diào)用的可能性，因此，在設(shè)計遞歸過程（函數(shù)）時，必須考慮遞歸調(diào)用的終止問題，就是遞歸調(diào)用要受限于某一條件，而且要保證這個條件在一定情況下肯定能得到滿足。⑤整個遞歸過程可視為由往返雙向“運動”組成，先是逐層遞進，逐層打開新的“篇章”，（有可能無具體計算值）當最終遞進達到邊界，執(zhí)行完本“層”的語句，才由最末一“層”逐次返回到上“層”，每次返回均帶回新的計算值，直至回到第一次由主程序調(diào)用的地方，完成對原問題的處理。④由于調(diào)用參數(shù)不斷改變，將使條件滿足，此時就是最后一“層”，不需再調(diào)用自身，而是在本層往下執(zhí)行后繼語句，遇到end，就返回到上“層”調(diào)用此子程序的地方并繼續(xù)往下執(zhí)行，如此直到返回主程序③每遞歸調(diào)用一次自身，系統(tǒng)就打開一“層”與自身相同的程序系列;第11頁，課件共27頁，創(chuàng)作于2023年2月如何設(shè)計遞歸算法？1.確定遞歸公式2.確定邊界(終了)條件課堂練習2：求：1+2+3+...+n的值。n從鍵盤上輸入。有一對雌雄兔,每兩個月就繁殖雌雄各一對兔子.問n個月后共有多少對兔子?用遞歸的方法求Xn（X和n由鍵盤輸入）已知:數(shù)列1,1,2,4,7,13,24,44,...求數(shù)列的第n項.第12頁，課件共27頁，創(chuàng)作于2023年2月n!1n=0n(n-1)!n>0【例7】：用遞歸計算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.使用遞歸求解問題，通?？梢詫⒁粋€比較大的問題層層轉(zhuǎn)化為一個與原問題相類似的、規(guī)模較小的問題進行求解，最終達到對原問題的求解。第13頁，課件共27頁，創(chuàng)作于2023年2月?！璮ac(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*第14頁，課件共27頁，創(chuàng)作于2023年2月遞歸過程【例8】：把一個十進制整數(shù)轉(zhuǎn)換成K進制數(shù)(k<10)。Knumber8157819820532第15頁，課件共27頁，創(chuàng)作于2023年2月分析根據(jù)數(shù)制轉(zhuǎn)換規(guī)則，把一個十進制整數(shù)轉(zhuǎn)換成K進制數(shù)，要用“除K取余”法。也就是用K依次去除這個數(shù)及其商，所得余數(shù)依次作為K進制數(shù)相繼的低位數(shù)字，一直到商為0即可。如果我們不用數(shù)組存儲每次求得的低位數(shù)字，怎么讓程序按順序輸出K進制的各位數(shù)字？第16頁，課件共27頁，創(chuàng)作于2023年2月分析可以用遞歸的方法實現(xiàn)這一過程。算法過程tentok(number,k)如下：步一digitnumbermodk;步二numbernumberdivk步三如果number不為0則調(diào)用

tentok(number,k)步四輸出digit第17頁，課件共27頁，創(chuàng)作于2023年2月參考程序：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.第18頁，課件共27頁，創(chuàng)作于2023年2月執(zhí)行過程分析第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第19頁，課件共27頁，創(chuàng)作于2023年2月遞歸結(jié)構(gòu)的優(yōu)點：結(jié)構(gòu)清晰、容易閱讀和理解。遞歸結(jié)構(gòu)的缺點：需要保留每次遞歸調(diào)用時的參數(shù)和局部變量，占用內(nèi)存大，耗費機時多，程序運行的效率較低。遞歸算法的實用情況：1.符合遞歸的描述：需要解決的問題可以化為子問題求解，而子問題求解的方法與原問題相同，只是數(shù)量增大或減少。2.遞歸調(diào)用的次數(shù)是有限的。3.必須有遞歸結(jié)束的條件。第20頁，課件共27頁，創(chuàng)作于2023年2月例9、漢諾塔問題有n個半徑各不相同的圓盤，按半徑從大到小，自下而上依次套在A柱上，另外還有B、C兩根空柱。要求將A柱上的n個圓盤全部搬到C柱上去，每次只能搬動一個盤子，且必須始終保持每根柱子上是小盤在上，大盤在下。在移動盤子的過程當中發(fā)現(xiàn)要搬動n個盤子，必須先將n-1個盤子從A柱搬到B柱去，再將A柱上的最后一個盤子搬到C柱，最后從B柱上將n-1個盤子搬到C柱去。搬動n個盤子和搬動n-1個盤子時的方法是一樣的，當盤子搬到只剩一個時，遞歸結(jié)束。源柱工作柱目標柱ABC第21頁，課件共27頁，創(chuàng)作于2023年2月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.第22頁，課件共27頁，創(chuàng)作于2023年2月【例10】求找出具有下列性質(zhì)的數(shù)的個數(shù)(包含輸入的自然數(shù)n)：先輸入一個自然數(shù)n(n<=500),然后對此自然數(shù)按照如下方法進行處理:①.不作任何處理;②.在它的左邊加上一個自然數(shù),但該自然數(shù)不能超過原數(shù)的一半;③.加上數(shù)后,繼續(xù)按此規(guī)則進行處理,直到不能再加自然數(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.第23頁，課件共27頁，創(chuàng)作于2023年2月【例11】、求m與n的最大公約數(shù)分析：從數(shù)學上可以知道求m與n的最大公約數(shù)等價于求n與(mmodn)的最大公約數(shù)。這時可以把n當作新的m,(mmodn)當作新的n，這樣問題又變成了求新的m與n的最大公約數(shù)……這種方法我們稱為輾轉(zhuǎn)相除法。設(shè)兩個整數(shù)分別為m和n，將m整除n得到一個余數(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.第24頁，課件共27頁，創(chuàng)作于2023年2月【分析】對于一個已確定的數(shù)組a[1]至a[n]和一個確定的數(shù)m，判斷能否使數(shù)組a中任意幾個元素之和等于m，等價于判斷能否從數(shù)組a中取任意數(shù)使其和為m。此時若a[n]=m，則可以輸出“YES”，否則若n=1，則可以輸出“NO”。否則可以按以下規(guī)則進行判斷：對于a中任意元素a[n]只有取與不取兩種情況：

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

(２)不取a[n]：則此時問題轉(zhuǎn)化為：對于一個已確定的數(shù)組a[1]至a[n-1]和一個確定的數(shù)m，判斷能否使數(shù)組a中任意幾個元素之和等于m。若用函數(shù)sum(n,m