c語(yǔ)言 函數(shù)的遞歸調(diào)用參考幻燈片

1、1,第五章,函數(shù),計(jì),1,張福祥,主編,遼寧大學(xué)出版社,2,第五章,函數(shù),計(jì),2,我們先看這樣一個(gè)例子,說(shuō)有一只調(diào)皮的小猴子,摘了一堆水果,第一天,吃了水果的一半,又多吃了一個(gè),第二天吃了剩,下水果的一半,又多吃了一個(gè),依次類推,到第,十天,發(fā)現(xiàn)只剩下了,1,個(gè)水果,請(qǐng)問(wèn)這只猴子到,底摘了多少個(gè)水果,3,第五章,函數(shù),計(jì),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ù)都是用遞歸的形式定義的,1,1,1,0,1,n,n,n,n,n

2、,0,0,1,1,n,x,x,n,x,n,n,4,第五章,函數(shù),計(jì),4,1,直接遞歸調(diào)用,函數(shù)直接調(diào)用本身,二、程序中的遞歸方式,2,間接遞歸調(diào)用,函數(shù)間接調(diào)用本身,5,第五章,函數(shù),計(jì),5,說(shuō)明,C,語(yǔ)言對(duì)遞歸函數(shù)的自調(diào)用次數(shù)沒有限制,必須有遞歸結(jié)束條件,int,f(x,int x,int y, z,z,f(y,return(2*z),直接調(diào)用,間接調(diào)用,int,f1(x,int x,int y, z,z,f2(y,return(2*z),int,f2(t,int t,int a, c,c,f1(a,return(3+c),6,第五章,函數(shù),計(jì),6,思考如下問(wèn)題,例,1,有,5,個(gè)人坐在一起

3、,問(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è)人，說(shuō)比第,1,個(gè)人大,2,歲；最后問(wèn)第,1,個(gè)人，他說(shuō)他,10,歲；請(qǐng)問(wèn)第,5,個(gè)人多大,比她大,2,歲,我,10,歲,7,第五章,函數(shù),計(jì),7,age(5,16,2=18,age(4,14,2=16,age(3,12,2=14,age(2,10,2=12,10 (n=1,age(n),age(n-1)+2 (n1,設(shè),age,表示年齡，則有如下,age(5,age(4)+2,age(4,age(3)+2,age(3,age(2)+

4、2,age(2,age(1)+2,age(1,10,8,第五章,函數(shù),計(jì),8,main(,printf(“%d”, age(5,age(int n,int c,if(n=1) c=10,else c = age(n-1)+2,return(c),age(5,c=10,n=1,c=age(3)+2,n=4,c=age(2)+2,n=3,c=age(1)+2,n=2,c=age(4)+2,n=5,c=10+2=12,c=12+2=14,c=14+2=16,c=16+2=18,9,第五章,函數(shù),計(jì),9,例,2,漢諾塔,Hanoi,問(wèn)題,B,C,問(wèn)題,將,A,塔上,n,個(gè)盤子移至,C,借助于,B,移動(dòng)

5、,時(shí),保證三個(gè)塔始終是大盤在下,小盤在上,并且每次只能移動(dòng)一個(gè)盤子,A,n,個(gè)盤子,10,第五章,函數(shù),計(jì),10,必須用遞歸方式解決,1,先將,A,塔,n,1,個(gè)盤子借助于,C,移至,B,上,2,將,A,上剩下的一個(gè)移至,C,上,3,將,B,上,n,1,個(gè)盤子借助于,A,移至,C,上,可以看到,1,3,為同一問(wèn)題,都為,n,1,個(gè)盤子借助于一個(gè),空塔移至另一塔上,11,第五章,函數(shù),計(jì),11,A,B,C,例,Hanoi,問(wèn)題,12,第五章,函數(shù),計(jì),12,void move(char getone, char putone,printf(%c-%cn,getone,putone);,void

6、hanoi(int n,char A,char B,char C,if(n=1) move(A,C,else,hanoi(n-1,A,C,B,move(A,C,hanoi(n-1,B,A,C,main(,int n,scanf(%d,hanoi(n,A,B,C,程序如下,A,B,C,A,B,C,A,B,C,A,B,C,13,第五章,函數(shù),計(jì),13,input the number of diskes:3,The step to moving 3 diskes,A,C,A,B,C,B,A,C,B,A,B,C,A,C,運(yùn)行情況如下,14,第五章,函數(shù),計(jì),14,move (getone, putone,表示從,getone,塔移一個(gè)盤子至,putone,塔,hanoi(n, one, two, three,表示,n,個(gè)盤子從,one,塔借助于,two,塔,空,移,至,three,塔，調(diào)用時(shí)塔用字符常量,A , B,C,表示,在程序中有兩個(gè)函數(shù),15,第五章,函數(shù),計(jì),15,小,結(jié),1,函數(shù)遞歸的定義,2,函數(shù)遞歸的特點(diǎn),3,函數(shù)遞歸調(diào)用的方式,本節(jié)課主要介紹的內(nèi)容,16,第五章,函數(shù),計(jì),16,上機(jī)作業(yè),說(shuō)有一只調(diào)皮的小猴子,摘了一堆水果,第一天,吃了水果的一