c語言--函數(shù)的遞歸調(diào)用PPT課件

.,1,張福祥主編遼寧大學(xué)出版社,C語言程序設(shè)計,.,2,我們先看這樣一個例子:,說有一只調(diào)皮的小猴子,摘了一堆水果,第一天吃了水果的一半,又多吃了一個;第二天吃了剩下水果的一半,又多吃了一個;依次類推.到第十天,發(fā)現(xiàn)只剩下了1個水果,請問這只猴子到底摘了多少個水果?,.,3,一、函數(shù)遞歸的特點(diǎn),5.4函數(shù)遞歸調(diào)用,1、定義：調(diào)用一個函數(shù)時直接或間接調(diào)用自身,稱之為函數(shù)的遞歸。2、一個問題能夠成為遞歸必須具備的條件是：,許多數(shù)學(xué)函數(shù)都是用遞歸的形式定義的：,.,4,1.直接遞歸調(diào)用：函數(shù)直接調(diào)用本身,二、程序中的遞歸方式,2.間接遞歸調(diào)用：函數(shù)間接調(diào)用本身,.,5,說明C語言對遞歸函數(shù)的自調(diào)用次數(shù)沒有限制必須有遞歸結(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);,.,6,思考如下問題：,例1:有5個人坐在一起,問第5個人多少歲,他說比第4個人大2歲;問第4個人歲數(shù),他說比第3個人大2歲;問第3個人,又說比第2個大2歲;問第2個人，說比第1個人大2歲；最后問第1個人，他說他10歲；請問第5個人多大?,比她大2歲,比她大2歲,比她大2歲,比她大2歲,我10歲,.,7,age(5)=16+2=18,age(4)=14+2=16,age(3)=12+2=14,age(2)=10+2=12,設(shè)age表示年齡，則有如下:,age(5)=age(4)+2,age(4)=age(3)+2,age(3)=age(2)+2,age(2)=age(1)+2,age(1)=10,.,8,main()printf(“%d”,age(5);,age(5),.,9,例2:漢諾塔(Hanoi)問題,問題:將A塔上n個盤子移至C(借助于B)。移動時,保證三個塔始終是大盤在下,小盤在上，并且每次只能移動一個盤子。,A,n個盤子,.,10,必須用遞歸方式解決,1)先將A塔n1個盤子借助于C移至B上,2)將A上剩下的一個移至C上.,3)將B上n1個盤子借助于A移至C上.,可以看到:1)、3)為同一問題,都為n1個盤子借助于一個空塔移至另一塔上。,.,11,例Hanoi問題,.,12,voidmove(chargetone,charputone)printf(%c-%cn,getone,putone);voidhanoi(intn,charA,charB,charC)if(n=1)move(A,C);elsehanoi(n-1,A,C,B);move(A,C);hanoi(n-1,B,A,C);main()intn;scanf(%d,程序如下：,.,13,inputthenumberofdiskes:3Thesteptomoving3diskes:ACABCBACBABCAC,運(yùn)行情況如下：,.,14,move(getone,putone)表示從getone塔移一個盤子至putone塔,hanoi(n,one,two,three)表示n個盤子從one塔借助于two塔(空)移至three塔，調(diào)用時塔用字符常量A,B,C表示。,在程序中有兩個函數(shù):,.,15,小結(jié),1.函數(shù)遞歸的定義,2.函數(shù)遞歸的特點(diǎn),3.函數(shù)遞歸調(diào)用的方式,本節(jié)課主要介紹的內(nèi)容：,.,16,上機(jī)作業(yè)：,說有一只調(diào)皮的小猴子,摘了一堆水果,