子程序的遞歸與嵌套

1、子程序的嵌套與遞歸11、復(fù)習(xí)函數(shù)與過(guò)程子程序子程序的定義定義位置如何定義？子程序的調(diào)用在何處調(diào)用？如何調(diào)用？參數(shù)的傳遞值傳遞，地址傳遞變量的作用域全局，局部子程序如何返回值到調(diào)用處函數(shù)通過(guò)函數(shù)名帶回值子程序可通過(guò)變量參數(shù)和全局變量的方式帶回值到調(diào)用處2【例1】：輸入一個(gè)正整數(shù)，如果是回文素?cái)?shù)則輸出“Yes”，否則輸出“No”【分析】定義兩個(gè)并列關(guān)系的函數(shù)，分別判斷一個(gè)數(shù)是否為素?cái)?shù)和是否為回文數(shù)教材P93 例5-113注意：1）內(nèi)、外層子程序不得相互交叉，內(nèi)層必須完全嵌套在外層之中；2）一般情況下，在子程序內(nèi)部需要使用的變量應(yīng)在子程序的內(nèi)部進(jìn)行定義。外層子程序不能訪問(wèn)內(nèi)層子程序所定義的變量。【例

2、2】：求組合數(shù) 的和。var s:real;function cnm(n,m:integer):real; function fac(k:integer):longint; var i:integer; t:real; begin t:=1; for i:=2 to k do t:=t*i; fac:=t; end; begin cnm:=fac(n)/(fac(m)*fac(n-m); end;begin s:=cnm(6,3)+cnm(9,5); writeln(s=,s:8:2);end.2、子程序的嵌套：4function fac(k:integer):longint; var i:i

3、nteger; t:real; begin t:=1; for i:=2 to k do t:=t*i; fac:=t; end;function cnm(n,m:integer):real; begin cnm:=fac(n)/(fac(m)*fac(n-m); end;function fac(k:integer):longint;Forward；function cnm(n,m:integer):real; begin cnm:=fac(n)/(fac(m)*fac(n-m); end;function fac(k:integer):real; var i:integer; t:real

4、; begin t:=1; for i:=2 to k do t:=t*i; fac:=t; end;超前引用5【例3】：求組合數(shù)（ ）/7！ 的和。var s:real;function fac(k:integer):longint; var i:integer; t:longint; begin t:=1; for i:=2 to k do t:=t*i; fac:=t; end;function cnm(n,m:integer):real; begin cnm:=fac(n)/(fac(m)*fac(n-m); end;begin s:=cnm(6,3)+cnm(9,5); writel

5、n(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ì)算：63.遞歸調(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)用其自身，稱為間接遞歸。直接遞歸

6、間接遞歸7遞歸應(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的值代入上一層

7、去求a3; ,如此,直到求出a1。因此： 10 (x=5) Ax= Ax+1 + 2 (x5)其中求Ax+1 又采用求Ax 的方法。所以:定義一個(gè)處理問(wèn)題的子程序Num(x)，如果X 0【例7】：用遞歸計(jì)算n!n!可以由下面公式表示：var n,s:integer;function fac(a:integer):integer; begin if a=0 then fac:=1 else fac:=a*fac(a-1); end;begin readln(n); s:=fac(n); writeln(n,!=,s)end. 使用遞歸求解問(wèn)題，通?？梢詫⒁粋€(gè)比較大的問(wèn)題層層轉(zhuǎn)化為一個(gè)與原問(wèn)題相類

8、似的、規(guī)模較小的問(wèn)題進(jìn)行求解，最終達(dá)到對(duì)原問(wèn)題的求解。13棧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*14遞歸過(guò)程【例8】：把一個(gè)十進(jìn)制整數(shù)轉(zhuǎn)換成K進(jìn)制數(shù)(k10)。 K number815781982053215分析根據(jù)數(shù)制轉(zhuǎn)換規(guī)則，把一個(gè)十進(jìn)制整數(shù)轉(zhuǎn)換成K進(jìn)制數(shù)

9、，要用“除K取余”法。也就是用K依次去除這個(gè)數(shù)及其商，所得余數(shù)依次作為K進(jìn)制數(shù)相繼的低位數(shù)字，一直到商為0即可。 如果我們不用數(shù)組存儲(chǔ)每次求得的低位數(shù)字，怎么讓程序按順序輸出K進(jìn)制的各位數(shù)字？16分析可以用遞歸的方法實(shí)現(xiàn)這一過(guò)程。算法過(guò)程tentok(number,k)如下：步一digitnumber mod k;步二numbernumber div k步三如果number不為0則調(diào)用tentok(number,k)步四輸出digit17參考程序：program convert(input,output);var number ,k:integer;procedure tentok(numbe

10、r,k:Integer); var digit:integer; begin digit:=number mod k; number:=number div k; if number0 then tentok(number,k); write(digit); end;begin write(Enter number and converted basis k(2-9):); readln(number,k); tentok(number,k); writeln;end. 18執(zhí)行過(guò)程分析第2次調(diào)用digit=3number=2tentok(2,8)第1次調(diào)用digit=5number=19te

11、ntok(19,8)Tentok(157,8)第3次調(diào)用digit=2number=0write(digit)write(digit)write(digit)K number815781982053219遞歸結(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é)束的條件。20例9、漢諾塔問(wèn)題 有n個(gè)半徑各不相同的圓盤(pán)，按半徑從大到小，

12、自下而上依次套在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)柱A B C21var a,b,c,number:integer;procedure move(n: integer;a,b,c:char);begin if n=1 then writeln

13、(a,-,c) else begin move(n-1,a,c,b); writeln(a,-,c); move(n-1,b,a,c) end;end;begin write(the number of dish:); readln(number); move(number,A,B,C);end.22【例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滿足條件的

14、數(shù)為 6 16 26 126 36 136輸出: 6 var n,i:integer; s:real; procedure qiu(x:integer); var k:integer; begin if x0 then begin s:=s+1; for k:=1 to x div 2 do qiu(k) end end; begin readln(n); s:=0; qiu(n); writeln(s:2:0) end.23【例11】、求m與n的最大公約數(shù)分析：從數(shù)學(xué)上可以知道求m與n的最大公約數(shù)等價(jià)于求n與(m mod n)的最大公約數(shù)。這時(shí)可以把n當(dāng)作新的m, (m mod n)當(dāng)作新的

15、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;function gys(a,b:integer):integer;var r:integer;begin r:=a mod b; if r=0 then gys:b else gys:=gys(b,r);end;begin readln(m,n); writeln(gys is:,gys(m,n);end.24【分析】對(duì)于一個(gè)已確定的數(shù)組a1

16、至an和一個(gè)確定的數(shù)m，判斷能否使數(shù)組a中任意幾個(gè)元素之和等于m，等價(jià)于判斷能否從數(shù)組a中取任意數(shù)使其和為m。 此時(shí)若an=m，則可以輸出“YES”，否則若n=1，則可以輸出“NO”。 否則可以按以下規(guī)則進(jìn)行判斷：對(duì)于a中任意元素an只有取與不取兩種情況： ()取an： 則此時(shí)問(wèn)題轉(zhuǎn)化為：對(duì)于一個(gè)已確定的數(shù)組a1至an-1和一個(gè)確定的數(shù)m-an，判斷能否使數(shù)組a中任意幾個(gè)元素之和等于m-an。 ()不取an： 則此時(shí)問(wèn)題轉(zhuǎn)化為：對(duì)于一個(gè)已確定的數(shù)組a1至an-1和一個(gè)確定的數(shù)m，判斷能否使數(shù)組a中任意幾個(gè)元素之和等于m。 若用函數(shù)sum(n,m)表示能否從數(shù)組a1至an中取任意數(shù)使其和為m，只

17、要sum(n-1,m-an)和sum(n-1,m)當(dāng)中有一個(gè)值為真，則sum(n,m)為真，否則為假。因此，可以用遞歸來(lái)解此題。 遞歸終止條件為： if an=m then sum:=true else if n=1 then sum:=false;【例12】 已知一個(gè)一維數(shù)組A1.N(N50)，又已知一整數(shù)M。 如能使數(shù)組A中任意幾個(gè)元素之和等于M，則輸出YES，反之則為NO。25Program digui (input,output);Const n=8;Type mat=array1.n of char;Var i:integer;a:mat;Procedure print(i:integer);begin If i=n then write(ai) else begin print(i+1);write(ai); end;end;Beginfor i:=1 to n do readln(ai);i:=1; p