函數(shù)嵌套調(diào)用和遞歸調(diào)用省公開課一等獎全國示范課微課金獎

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

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

平方(x+y)2

3、編寫函數(shù)求解(x+y)2！第2頁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頁6.9.1函數(shù)嵌套調(diào)用C語言中不允許嵌套函數(shù)定義，各函數(shù)之間是平行，不存在上一級函數(shù)和下一級函數(shù)問題。voidprint(){putchar('*');

voidprnline(intn){inti;for(i=0;i<=n;i++)putchar('\n');}}第4頁C語言允許在一個函數(shù)定義中出現(xiàn)對另一個函數(shù)調(diào)用(使用)。這么就出現(xiàn)了函數(shù)嵌套調(diào)用，即在被使用函數(shù)中又調(diào)用其它函數(shù)。第5頁#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ù)返回值形參實參c1=c2=

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

return(rtn);}第6頁例2求三個數(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頁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)。練習第8頁練習例：編寫求組合數(shù)函數(shù)。第9頁6.9.2函數(shù)遞歸調(diào)用

遞歸:

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

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

2.間接遞歸調(diào)用：函數(shù)間接調(diào)用本身第10頁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頁【例1】有5個人，第5個人說他比第4個人大2歲，第4個人說他對第3個人大2歲，第3個人說他對第2個人大2歲，第2個人說他比第1個人大2歲，第1個人說他10歲。求第5個人多少歲。經(jīng)過分析，設(shè)計遞歸函數(shù)以下：10(n=1)age(n)=age(n-1)+2(n>1)第12頁遞歸函數(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);}程序以下：請看看單步運行情況……第13頁age(5)

c=age(4)+2;

returnc;age(intn){intc;if(n==1)c=10;elsec=age(n-1)+2;returnc;}遞歸過程跟蹤分析：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頁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頁總結(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頁例2：用遞歸算法計算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頁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頁

例3、用遞歸法計算Fibonacci序列第20項。f=1n=1或者n=2f(n-1)+f(n-2)n>2依據(jù)數(shù)學(xué)公式，很輕易將n階問題轉(zhuǎn)化成n-1階和n-2階問題，即：f(n)=f(n-1)+f(n-2)，遞歸出口：n=1或者n=2。第19頁程序以下：#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頁例4:漢諾塔(Hanoi)問題BC問題:將A塔上n個盤子移至C(借助于B)。移動時,確保三個塔一直是大盤在下,小盤在上。An個盤子第21頁必須用遞歸方式處理，將n階問題轉(zhuǎn)為n-1階：1)先將A塔n–1個盤子借助于C移至B上：2)將A上剩下一個移至C上.3)

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

#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盤子已經(jīng)到y(tǒng)上printf("%c-->%c\n",x,z);move(n-1,y,x,z);//y上n-1盤子想方法放到z}}第23頁

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

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