函數(shù)的嵌套調(diào)用和遞歸調(diào)用.ppt

《函數(shù)的嵌套調(diào)用和遞歸調(diào)用.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、函數(shù)的嵌套調(diào)用C語(yǔ)言中，所有函數(shù)的定義都是互相平行和獨(dú)立的，一個(gè)函數(shù)的定義不能包含另一個(gè)函數(shù)的定義，即不允許函數(shù)的嵌套定義，但函數(shù)的調(diào)用可以通過(guò)一個(gè)函數(shù)來(lái)調(diào)用另一個(gè)函數(shù)來(lái)實(shí)現(xiàn)，這就形成了函數(shù)的嵌套調(diào)用。下面是一個(gè)兩層嵌套的例子：[例7．9]利用公式：e=1+1/1!+1/2!+1/3!+1/4!+…近似計(jì)算自然數(shù)e。算法按兩層進(jìn)行：函數(shù)fac_v()計(jì)算1/m!(m=1,2,3,...,n).函數(shù)cai_e()計(jì)算整個(gè)公式右邊之和，作為e的近似值。函數(shù)cai_e()調(diào)用函數(shù)fac_v()以獲得1/m!的值，而主函數(shù)則調(diào)用cai_c得到e的近似值。

2、函數(shù)的嵌套調(diào)用#includemain(){doublecai_e(int)；intn；printf(”請(qǐng)輸入一個(gè)正整數(shù)：”)：scanf("％d”，&n)；printf(“自然數(shù)e的近似值為%lf”,cai_e(n))；}doublecai_e(intn){doublefac_v(int)；doublee＝1．0；while(n)e+＝fac_v(n--)；return(e)；}doublefac_v(intm){doublev=1．0；while(m)v/=m--；return(v)；}函數(shù)的嵌套調(diào)用整個(gè)程序執(zhí)行的流程如

3、圖所示：main()函數(shù){①調(diào)用cai_e(n)⑨結(jié)束}cai_e(n)函數(shù){③調(diào)用fac_v(m)⑦return語(yǔ)句}fac_v(m)函數(shù){⑤return語(yǔ)句}②⑧④⑥函數(shù)的遞歸調(diào)用函數(shù)的遞歸調(diào)用是指一個(gè)函數(shù)直接或間接地調(diào)用了該函數(shù)本身，它有兩種形式：·直接遞歸調(diào)用·間接遞歸調(diào)用1．遞歸的形式（1）直接遞歸[例7．10]下面函數(shù)sum()計(jì)算整數(shù)和：1+2+3+4+…+n。longsum(intn){if(n＝＝1)return(1)；return(sum(n-1)+n)；}函數(shù)的遞歸調(diào)用（2）間接遞歸上面的sum()函數(shù)改寫成兩個(gè)函數(shù)acc(

4、)和add()來(lái)共同實(shí)現(xiàn)這個(gè)計(jì)算：longacc(intn){longadd(int)；／*函數(shù)說(shuō)明*／if(n<＝1)return(1)；return(add(n));}longadd(intn){longacc(int)；／*函數(shù)說(shuō)明*／return(acc(n-1)+n)；}在函數(shù)acc()中嵌套調(diào)用了函數(shù)add()，而在函數(shù)add()中又來(lái)調(diào)用函數(shù)acc()，這樣就形成了間接遞歸調(diào)用。函數(shù)的遞歸調(diào)用2．遞歸的過(guò)程從嵌套的角度看，這里包含了一個(gè)循環(huán)過(guò)程，在這個(gè)循環(huán)過(guò)程中函數(shù)進(jìn)行遞推的計(jì)算或操作(遞推過(guò)程)；從循環(huán)的角度看，任何有效的循環(huán)都應(yīng)

5、有循環(huán)條件(遞歸條件)，或者說(shuō)循環(huán)結(jié)束的出口(遞歸出口)。[例6，10]中給出的sum()函數(shù)具有以上兩個(gè)遞歸函數(shù)的必備特征：·遞推過(guò)程：“return(sum(n一1)+n)；”語(yǔ)句計(jì)算sum(n-1)+n，并將它作為函數(shù)調(diào)用sum(n)的返回值，其中函數(shù)調(diào)用sum(n-1)維持循環(huán)，直至遞歸出口?！みf歸出口：“if(n＝＝1)return(1)；”語(yǔ)句在n=1時(shí)結(jié)束遞推過(guò)程(這里沒(méi)有sum()函數(shù)的調(diào)用)，并將數(shù)值1作為sum(1)的返回值。函數(shù)的遞歸調(diào)用如函數(shù)調(diào)用sum(5)的遞歸過(guò)程中，如下圖所示：sum(5)=sum(4)+5retur

6、n15sum(3)=sum(2)+3return6sum(4)=sum(3)+4return10遞歸出口sum(1)=1return1sum(2)=sum(1)+2return3求出sum(2)并返回求出sum(5)并返回求出sum(3)并返回求出sum(4)并返回遞推過(guò)程回推迭代過(guò)程圖6.3遞歸函數(shù)sum()的調(diào)用過(guò)程函數(shù)的遞歸調(diào)用3．遞歸的算法遞歸函數(shù)s(n)具有以下性質(zhì)：·遞推關(guān)系：s(m)＝s(m-1)+m，m＝1，2，…，n·極端情形：s(1)＝1遞推出口是極端情形的程序語(yǔ)言描述，完成了這兩點(diǎn)，就完成了遞歸函數(shù)的設(shè)計(jì)。遞歸函數(shù)sum()

7、也可以寫成如下形式：longsum(intn){if(n!＝1)return(sum(n一1)十n)；return(1)；}函數(shù)的遞歸調(diào)用4、示例[例7．12]編寫求兩個(gè)正整數(shù)的最大公約數(shù)的函數(shù)gcm().分析：以g表示正整數(shù)m和n的最大公約數(shù)。則(1)g可以整除min(m,n)和

8、m-n

9、.(2)若m==n,最大公約數(shù)g就是他們本身。用遞歸來(lái)表示：gcm(m,n)是求得正整數(shù)m和n的最大公約數(shù)。則遞推關(guān)系：gcm(m,n)=gcm(min(m,n)，

10、m-n

11、).極端情形：若m==n,最大公約數(shù)gcm(m,n)就是他們本身。函數(shù)的遞歸調(diào)用程序表

12、示：unsignedgcm(unsignedm,unsignedn){if(m==n)returnm;if(m>n)return(gcm