資源描述:
《c語(yǔ)言--函數(shù)的遞歸調(diào)用》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、計(jì)算機(jī)科學(xué)系陳垚1張福祥主編遼寧大學(xué)出版社C語(yǔ)言程序設(shè)計(jì)計(jì)算機(jī)科學(xué)系陳垚2我們先看這樣一個(gè)例子:說(shuō)有一只調(diào)皮的小猴子,摘了一堆水果,第一天吃了水果的一半,又多吃了一個(gè);第二天吃了剩下水果的一半,又多吃了一個(gè);依次類推….到第十天,發(fā)現(xiàn)只剩下了1個(gè)水果,請(qǐng)問(wèn)這只猴子到底摘了多少個(gè)水果?計(jì)算機(jī)科學(xué)系陳垚3一、函數(shù)遞歸的特點(diǎn)5.4函數(shù)遞歸調(diào)用后一部分與原始問(wèn)題類似后一部分是原始問(wèn)題的簡(jiǎn)化1、定義:調(diào)用一個(gè)函數(shù)時(shí)直接或間接調(diào)用自身,稱之為函數(shù)的遞歸。2、一個(gè)問(wèn)題能夠成為遞歸必須具備的條件是:許多數(shù)學(xué)函數(shù)都是用遞歸的形式定義的:計(jì)算機(jī)科學(xué)系陳垚41.直接遞歸調(diào)用:函數(shù)直接調(diào)用本身二、程序
2、中的遞歸方式2.間接遞歸調(diào)用:函數(shù)間接調(diào)用本身計(jì)算機(jī)科學(xué)系陳垚5說(shuō)明C語(yǔ)言對(duì)遞歸函數(shù)的自調(diào)用次數(shù)沒(méi)有限制必須有遞歸結(jié)束條件intf(x)intx;{inty,z;……z=f(y);……return(2*z);}直接調(diào)用間接調(diào)用intf1(x)intx;{inty,z;……z=f2(y);……return(2*z);}intf2(t)intt;{inta,c;……c=f1(a);……return(3+c);}計(jì)算機(jī)科學(xué)系陳垚6思考如下問(wèn)題:例1:有5個(gè)人坐在一起,問(wèn)第5個(gè)人多少歲,他說(shuō)比第4個(gè)人大2歲;問(wèn)第4個(gè)人歲數(shù),他說(shuō)比第3個(gè)人大2歲;問(wèn)第3個(gè)人,又說(shuō)比第2個(gè)大2歲;問(wèn)第2個(gè)
3、人,說(shuō)比第1個(gè)人大2歲;最后問(wèn)第1個(gè)人,他說(shuō)他10歲;請(qǐng)問(wèn)第5個(gè)人多大?比她大2歲比她大2歲比她大2歲比她大2歲我10歲計(jì)算機(jī)科學(xué)系陳垚7age(5)=16+2=18age(4)=14+2=16age(3)=12+2=14age(2)=10+2=1210(n=1)age(n)=age(n-1)+2(n>1)設(shè)age表示年齡,則有如下:age(5)=age(4)+2age(4)=age(3)+2age(3)=age(2)+2age(2)=age(1)+2age(1)=10計(jì)算機(jī)科學(xué)系陳垚8main(){printf(“%d”,age(5));}age(intn){intc;if(
4、n==1)c=10;elsec=age(n-1)+2;return(c);}age(5)c=10n=1c=age(3)+2n=4c=age(2)+2n=3c=age(1)+2n=2c=age(4)+2n=5c=10+2=12c=12+2=14c=14+2=16c=16+2=18計(jì)算機(jī)科學(xué)系陳垚9例2:漢諾塔(Hanoi)問(wèn)題BC問(wèn)題:將A塔上n個(gè)盤(pán)子移至C(借助于B)。移動(dòng)時(shí),保證三個(gè)塔始終是大盤(pán)在下,小盤(pán)在上,并且每次只能移動(dòng)一個(gè)盤(pán)子。An個(gè)盤(pán)子計(jì)算機(jī)科學(xué)系陳垚10必須用遞歸方式解決1)先將A塔n–1個(gè)盤(pán)子借助于C移至B上2)將A上剩下的一個(gè)移至C上.3)將B上n–1個(gè)盤(pán)子借
5、助于A移至C上.可以看到:1)、3)為同一問(wèn)題,都為n–1個(gè)盤(pán)子借助于一個(gè)空塔移至另一塔上。計(jì)算機(jī)科學(xué)系陳垚11ABC例Hanoi問(wèn)題計(jì)算機(jī)科學(xué)系陳垚12voidmove(chargetone,charputone){printf("%c--->%c",getone,putone);}voidhanoi(intn,charA,charB,charC){if(n==1)move(A,C);else{hanoi(n-1,A,C,B);move(A,C);hanoi(n-1,B,A,C);}}main(){intn;scanf("%d",&n);hanoi(n,‘A',‘B',‘
6、C');}程序如下:ABCABCABCABC計(jì)算機(jī)科學(xué)系陳垚13inputthenumberofdiskes:3?Thesteptomoving3diskes:A??>CA??>BC??>BA??>CB??>AB??>CA??>C運(yùn)行情況如下:計(jì)算機(jī)科學(xué)系陳垚14計(jì)算機(jī)科學(xué)系陳垚15?move(getone,putone)表示從getone塔移一個(gè)盤(pán)子至putone塔?hanoi(n,one,two,three)表示n個(gè)盤(pán)子從one塔借助于two塔(空)移至three塔,調(diào)用時(shí)塔用字符常量'A','B','C'表示。在程序中有兩個(gè)函數(shù):計(jì)算機(jī)科學(xué)系陳垚16小結(jié)1.函數(shù)遞歸的定義
7、2.函數(shù)遞歸的特點(diǎn)3.函數(shù)遞歸調(diào)用的方式本節(jié)課主要介紹的內(nèi)容:計(jì)算機(jī)科學(xué)系陳垚17上機(jī)作業(yè):說(shuō)有一只調(diào)皮的小猴子,摘了一堆水果,第一天吃了水果的一半,又多吃了一個(gè);第二天吃了剩下水果的一半,又多吃了一個(gè);依次類推….到第十天,發(fā)現(xiàn)只剩下了10個(gè)水果,請(qǐng)問(wèn)這只猴子到底摘了多少個(gè)水果?1(n=10)num(n)=2*(num(n+1)+1)(n<10)