函數(shù)嵌套調(diào)用和遞歸調(diào)用省公開(kāi)課一等獎(jiǎng)全國(guó)示范課微課金獎(jiǎng)

《C語(yǔ)言程序設(shè)計(jì)》學(xué)習(xí)內(nèi)容：函數(shù)嵌套調(diào)用和遞歸調(diào)用第1頁(yè)6.9函數(shù)嵌套調(diào)用和遞歸調(diào)用引例編程函數(shù)求解：y=(x+y)2!然后調(diào)用函數(shù)求解(2+3)2！以及(3+4)2！要求：

1、首先編寫(xiě)求和函數(shù)，求解x+y和。2、編寫(xiě)函數(shù)求解(x+y)

平方(x+y)2

3、編寫(xiě)函數(shù)求解(x+y)2！第2頁(yè)main(){inta,b,c;scanf(“%d,%d”,&a,&b);jc(a,b);printf(“sumis%d",c);}intjc(intk,intj){intz,m,i,s=1;sum(k,j);pf(z);for(i=1;i<=m;i++)s=s*i;

returns;}intsum(intx,inty){

return(x+y);}intpf(inth){

return(h*h);}c=z=m=第3頁(yè)6.9.1函數(shù)嵌套調(diào)用C語(yǔ)言中不允許嵌套函數(shù)定義，各函數(shù)之間是平行，不存在上一級(jí)函數(shù)和下一級(jí)函數(shù)問(wèn)題。voidprint(){putchar('*');

voidprnline(intn){inti;for(i=0;i<=n;i++)putchar('\n');}}第4頁(yè)C語(yǔ)言允許在一個(gè)函數(shù)定義中出現(xiàn)對(duì)另一個(gè)函數(shù)調(diào)用(使用)。這么就出現(xiàn)了函數(shù)嵌套調(diào)用，即在被使用函數(shù)中又調(diào)用其它函數(shù)。第5頁(yè)#include<stdio.h>

longsum(inta,intb);longfactorial(intn);main(){intn1,n2;longa;scanf("%d,%d",&n1,&n2);a=sum(n1,n2);printf("a=%1d",a);}longsum(inta,intb){longc1,c2;factorial(a);factorial(b);

return(c1+c2);}

longfactorial(intn){longrtn=1;inti;for(i=1;i<=n;i++)rtn*=i;

return(rtn);}longsum(inta,intb);longfactorial(intn);文件包含編譯預(yù)處理命令函數(shù)申明函數(shù)定義函數(shù)調(diào)用函數(shù)調(diào)用函數(shù)返回值形參實(shí)參c1=c2=

longfactorial(intn){longrtn=1;inti;for(i=1;i<=n;i++)rtn*=i;

return(rtn);}第6頁(yè)例2求三個(gè)數(shù)中最大數(shù)和最小數(shù)差值#include<stdio.h>

intdif(intx,inty,intz);intmax(intx,inty,intz);intmin(intx,inty,intz);voidmain(){inta,b,c,d;scanf("%d%d%d",&a,&b,&c);

d=dif(a,b,c);printf("Max-Min=%d\n",d);}intmin(intx,inty,intz){intr;r=x<y?x:y;return(r<z?r:z);}intmax(intx,inty,intz){intr;r=x>y?x:y;return(r>z?r:z);}intdif(intx,inty,intz){returnmax(x,y,z)-min(x,y,z);}第7頁(yè)f(x+y)2x+y(x<=y)g(x,y)=f(x-y)2x+y(x>y)

其中：f(t)=(1+e-t)/(1+et)求result=g(2.5,3.4)。練習(xí)第8頁(yè)練習(xí)例：編寫(xiě)求組合數(shù)函數(shù)。第9頁(yè)6.9.2函數(shù)遞歸調(diào)用

遞歸:

一個(gè)函數(shù)直接或間接地使用本身。

1.直接遞歸調(diào)用：函數(shù)直接調(diào)用本身

2.間接遞歸調(diào)用：函數(shù)間接調(diào)用本身第10頁(yè)intf(intx){inty,z;……

z=f(y);…….return(2*z);}intf1(intx){inty,z;……

z=f2(y);…….return(2*z);}intf2(intt){inta,c;……

c=f1(a);…….return(3+c);}直接調(diào)用間接調(diào)用第11頁(yè)【例1】有5個(gè)人，第5個(gè)人說(shuō)他比第4個(gè)人大2歲，第4個(gè)人說(shuō)他對(duì)第3個(gè)人大2歲，第3個(gè)人說(shuō)他對(duì)第2個(gè)人大2歲，第2個(gè)人說(shuō)他比第1個(gè)人大2歲，第1個(gè)人說(shuō)他10歲。求第5個(gè)人多少歲。經(jīng)過(guò)分析，設(shè)計(jì)遞歸函數(shù)以下：10(n=1)age(n)=age(n-1)+2(n>1)第12頁(yè)遞歸函數(shù)：

10(n=1)age(n)=age(n-1)+2(n>1)age(intn){intc;if(n==1)c=10;elsec=age(n-1)+2;returnc;}main(){intx;x=age(5);

printf("%d",x);}程序以下：請(qǐng)看看單步運(yùn)行情況……第13頁(yè)age(5)

c=age(4)+2;

returnc;age(intn){intc;if(n==1)c=10;elsec=age(n-1)+2;returnc;}遞歸過(guò)程跟蹤分析：age(4)

c=age(3)+2;

returnc;age(3)

c=age(2)+2;

returnc;age(2)

c=age(1)+2;

returnc;age(1)

c=10

returnc;c=10c=12c=14c=16c=18第14頁(yè)main(){intx;age(3);

printf("%d",x);}age(intn){intc;

elsereturnc;}3age(n-1)2age(intn){intc;

elsereturnc;}2age(n-1)1age(intn){intc;if(n==1)c=10;

returnc;}1c=+2+2c=x=第15頁(yè)總結(jié)：遞歸算法遞歸函數(shù)名f(參數(shù)x){if(x==初值)//遞歸結(jié)束條件結(jié)果=…；else結(jié)果=含f(x-1)表示式；返回結(jié)果（return）；}f(n){f(n-1)

}main(){f(n)…}f(n-1){f(n-2)

}f(n-2){f(n-3)

}f(1或者0){f(0)==…)

}第16頁(yè)例2：用遞歸算法計(jì)算n！n!=n*(n-1)!(n-1)!=(n-1)*(n-2)!…..5!=5*4!4!=4*3!3!=3*2!2!=2*1!1!=1第17頁(yè)longjc(intn){longk;if(n==1)k=1;elsek=n*jc(n-1);returnk;}main(){longx;x=jc(6);

printf("%ld",x);}

longjc(intn){longk;inti;for(i=1;i<=n;i++)k=k*i;returnk;}main(){longx;x=jc(6);

printf("%ld",x);}第18頁(yè)

例3、用遞歸法計(jì)算Fibonacci序列第20項(xiàng)。f=1n=1或者n=2f(n-1)+f(n-2)n>2依據(jù)數(shù)學(xué)公式，很輕易將n階問(wèn)題轉(zhuǎn)化成n-1階和n-2階問(wèn)題，即：f(n)=f(n-1)+f(n-2)，遞歸出口：n=1或者n=2。第19頁(yè)程序以下：#include"stdio.h"intfib(intn){if((n==1)||(n==2))return1;elsereturn(fib(n-1)+fib(n-2));}main(){inti;printf("\n");printf("%d",fib(20));}第20頁(yè)例4:漢諾塔(Hanoi)問(wèn)題BC問(wèn)題:將A塔上n個(gè)盤(pán)子移至C(借助于B)。移動(dòng)時(shí),確保三個(gè)塔一直是大盤(pán)在下,小盤(pán)在上。An個(gè)盤(pán)子第21頁(yè)必須用遞歸方式處理，將n階問(wèn)題轉(zhuǎn)為n-1階：1)先將A塔n–1個(gè)盤(pán)子借助于C移至B上：2)將A上剩下一個(gè)移至C上.3)

將B上n–1個(gè)盤(pán)子借助于A移至C上.能夠看到:1)、3)為同一問(wèn)題,都為n–1個(gè)盤(pán)子借助于一個(gè)空塔移至另一塔上。遞歸出口：n=1，此時(shí)A座上只有一個(gè)盤(pán)子，直接將其移動(dòng)到C座上即可。第22頁(yè)

#include"stdio.h"voidmove(intn,charx,chary,charz){if(n==1)printf("%c-->%c\n",x,z);else{move(n-1,x,z,y);//n-1盤(pán)子已經(jīng)到y(tǒng)上printf("%c-->%c\n",x,z);move(n-1,y,x,z);//y上n-1盤(pán)子想方法放到z}}第23頁(yè)

main(){intn;printf("inputthenumberofdiskes":);scanf("%d",&n);move(n,'a','b','c');}第24頁(yè)運(yùn)行情況以下：inputthenumberofdiskes:3

A>CA>BC>BA>CB>AB>CA