張福祥主編遼寧大學出版社

C語言程序設計1計算機科學系陳垚我們先看這樣一個例子:說有一只調皮的小猴子,摘了一堆水果,第一天吃了水果的一半,又多吃了一個;第二天吃了剩下水果的一半,又多吃了一個;依次類推….到第十天,發(fā)現(xiàn)只剩下了1個水果,請問這只猴子到底摘了多少個水果?2計算機科學系陳垚一、函數(shù)遞歸的特點5.4函數(shù)遞歸調用

后一部分與原始問題類似

后一部分是原始問題的簡化1、定義：調用一個函數(shù)時直接或間接調用自身,

稱之為函數(shù)的遞歸。2、一個問題能夠成為遞歸必須具備的條件是：許多數(shù)學函數(shù)都是用遞歸的形式定義的：3計算機科學系陳垚1.直接遞歸調用：函數(shù)直接調用本身二、程序中的遞歸方式2.間接遞歸調用：函數(shù)間接調用本身4計算機科學系陳垚說明C語言對遞歸函數(shù)的自調用次數(shù)沒有限制必須有遞歸結束條件

int

f(x)

intx;{inty,z;……z=f(y);……return(2*z);}直接調用間接調用int

f1(x)intx;{inty,z;……z=f2(y);……return(2*z);}int

f2(t)intt;{inta,c;……c=f1(a);……return(3+c);}5計算機科學系陳垚

思考如下問題：例1:

有5個人坐在一起,問第5個人多少歲,他說比第4個人大2歲;問第4個人歲數(shù),他說比第3個人大2歲;問第3個人,又說比第2個大2歲;問第2個人，說比第1個人大2歲；最后問第1個人，他說他10歲；請問第5個人多大?比她大2歲比她大2歲比她大2歲比她大2歲我10歲6計算機科學系陳垚age(5)=16+2=18age(4)=14+2=16age(3)=12+2=14age(2)=10+2=12

10(n=1)

age(n)=age(n-1)+2(n>1)

設

age表示年齡，則有如下:age(5)=age(4)+2age(4)=age(3)+2age(3)=age(2)+2age(2)=age(1)+2age(1)=107計算機科學系陳垚

main(){

printf(“%d”,age(5));}

age(intn){intc;

if(n==1)c=10;elsec=age(n-1)+2;

return(c);}age(5)c=10

n=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=188計算機科學系陳垚例2:

漢諾塔(Hanoi)問題BC問題:

將A塔上n個盤子移至C(借助于B)。移動時,保證三個塔始終是大盤在下,小盤在上，并且每次只能移動一個盤子。An個盤子9計算機科學系陳垚必須用遞歸方式解決1)

先將A塔n–1個盤子借助于C移至B上2)將A上剩下的一個移至C上.3)將B上n–1個盤子借助于A移至C上.可以看到:

1)、3)為同一問題,都為n–1個盤子借助于一個空塔移至另一塔上。10計算機科學系陳垚ABC例

Hanoi問題11計算機科學系陳垚voidmove(char

getone,charputone){printf("%c--->%c\n",getone,putone);}voidhanoi(int

n,char

A,char

B,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',‘C');}程序如下：ABCABCABCABC12計算機科學系陳垚

inputthenumberofdiskes:3

Thesteptomoving3diskes:A>CA>BC>BA>CB>AB>CA>C運行情況如下：13計算機科學系陳垚

move(getone,putone)

表示從getone

塔移一個盤子至putone塔

hanoi(n,one,two,three)

表示n個盤子從one塔借助于two塔(空)移

至three塔，調用時塔用字符常量'A','B','C'表示。在程序中有兩個函數(shù):14計算機科學系陳垚小結1.函數(shù)遞歸的定義2.函數(shù)遞歸的特點3.函數(shù)遞歸調用的方式本節(jié)課主要介紹的內容：15計算機科學系陳垚上機作業(yè)：說有一只調皮的小猴子,摘了一堆水果,第一天吃了水果的一半,又多吃了一個;第二天吃了剩下水果的一半,又多吃了一個;依次類推….到第十天,發(fā)現(xiàn)只剩下了10個水果,請問這只猴子到底摘了多