資源描述:
《函數(shù)的嵌套調(diào)用和遞歸調(diào)用.ppt》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、函數(shù)的嵌套調(diào)用C語言中,所有函數(shù)的定義都是互相平行和獨立的,一個函數(shù)的定義不能包含另一個函數(shù)的定義,即不允許函數(shù)的嵌套定義,但函數(shù)的調(diào)用可以通過一個函數(shù)來調(diào)用另一個函數(shù)來實現(xiàn),這就形成了函數(shù)的嵌套調(diào)用。下面是一個兩層嵌套的例子:[例7.9]利用公式:e=1+1/1!+1/2!+1/3!+1/4!+…近似計算自然數(shù)e。算法按兩層進行:函數(shù)fac_v()計算1/m!(m=1,2,3,...,n).函數(shù)cai_e()計算整個公式右邊之和,作為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(”請輸入一個正整數(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)用整個程序執(zhí)行的流程如
3、圖所示:main()函數(shù){①調(diào)用cai_e(n)⑨結(jié)束}cai_e(n)函數(shù){③調(diào)用fac_v(m)⑦return語句}fac_v(m)函數(shù){⑤return語句}②⑧④⑥函數(shù)的遞歸調(diào)用函數(shù)的遞歸調(diào)用是指一個函數(shù)直接或間接地調(diào)用了該函數(shù)本身,它有兩種形式:·直接遞歸調(diào)用·間接遞歸調(diào)用1.遞歸的形式(1)直接遞歸[例7.10]下面函數(shù)sum()計算整數(shù)和:1+2+3+4+…+n。longsum(intn){if(n==1)return(1);return(sum(n-1)+n);}函數(shù)的遞歸調(diào)用(2)間接遞歸上面的sum()函數(shù)改寫成兩個函數(shù)acc(
4、)和add()來共同實現(xiàn)這個計算:longacc(intn){longadd(int);/*函數(shù)說明*/if(n<=1)return(1);return(add(n));}longadd(intn){longacc(int);/*函數(shù)說明*/return(acc(n-1)+n);}在函數(shù)acc()中嵌套調(diào)用了函數(shù)add(),而在函數(shù)add()中又來調(diào)用函數(shù)acc(),這樣就形成了間接遞歸調(diào)用。函數(shù)的遞歸調(diào)用2.遞歸的過程從嵌套的角度看,這里包含了一個循環(huán)過程,在這個循環(huán)過程中函數(shù)進行遞推的計算或操作(遞推過程);從循環(huán)的角度看,任何有效的循環(huán)都應(yīng)
5、有循環(huán)條件(遞歸條件),或者說循環(huán)結(jié)束的出口(遞歸出口)。[例6,10]中給出的sum()函數(shù)具有以上兩個遞歸函數(shù)的必備特征:·遞推過程:“return(sum(n一1)+n);”語句計算sum(n-1)+n,并將它作為函數(shù)調(diào)用sum(n)的返回值,其中函數(shù)調(diào)用sum(n-1)維持循環(huán),直至遞歸出口?!みf歸出口:“if(n==1)return(1);”語句在n=1時結(jié)束遞推過程(這里沒有sum()函數(shù)的調(diào)用),并將數(shù)值1作為sum(1)的返回值。函數(shù)的遞歸調(diào)用如函數(shù)調(diào)用sum(5)的遞歸過程中,如下圖所示: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)并返回遞推過程回推迭代過程圖6.3遞歸函數(shù)sum()的調(diào)用過程函數(shù)的遞歸調(diào)用3.遞歸的算法遞歸函數(shù)s(n)具有以下性質(zhì):·遞推關(guān)系:s(m)=s(m-1)+m,m=1,2,…,n·極端情形:s(1)=1遞推出口是極端情形的程序語言描述,完成了這兩點,就完成了遞歸函數(shù)的設(shè)計。遞歸函數(shù)sum()
7、也可以寫成如下形式:longsum(intn){if(n!=1)return(sum(n一1)十n);return(1);}函數(shù)的遞歸調(diào)用4、示例[例7.12]編寫求兩個正整數(shù)的最大公約數(shù)的函數(shù)gcm().分析:以g表示正整數(shù)m和n的最大公約數(shù)。則(1)g可以整除min(m,n)和
8、m-n
9、.(2)若m==n,最大公約數(shù)g就是他們本身。用遞歸來表示: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