(6.29)-第28課（6.4節(jié)-遞歸函數(shù)）C語(yǔ)言程序設(shè)計(jì)

遞歸函數(shù)函數(shù)函數(shù)的嵌套調(diào)用不允許嵌套定義函數(shù)，函數(shù)間的關(guān)系是平行的、獨(dú)立的允許嵌套調(diào)用，即在調(diào)用某函數(shù)過(guò)程中又調(diào)用另一函數(shù)main()調(diào)用函數(shù)a結(jié)束a函數(shù)b函數(shù)調(diào)用函數(shù)b

【例1：】求三個(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);}intdif(intx,inty,intz){returnmax(x,y,z)-min(x,y,z);}intmax(intx,inty,intz){intr;r=x>y?x:y;return(r>z?r:z);}intmin(intx,inty,intz){intr;r=x<y?x:y;return(r<z?r:z);}main()調(diào)用函數(shù)dif輸出結(jié)束dif函數(shù)max函數(shù)調(diào)用函數(shù)max調(diào)用函數(shù)minmin函數(shù)

⑩⑾⑿函數(shù)的遞歸調(diào)用在函數(shù)調(diào)用過(guò)程中，直接或間接的調(diào)用自身直接遞歸調(diào)用：在函數(shù)體內(nèi)又調(diào)用自身間接遞歸調(diào)用：當(dāng)函數(shù)1去調(diào)用另一函數(shù)2時(shí)，而另一函數(shù)2反過(guò)來(lái)又調(diào)用函數(shù)1自身f()調(diào)fintf(intx){inty,z;……

z=f(y);…….return(2*z);}直接遞歸調(diào)用調(diào)f2調(diào)f1f1()f2()intf1(intx){inty,z;……

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

c=f1(a);…….return(3+c);}間接遞歸調(diào)用【例2：】有5個(gè)人，第5個(gè)人比第4個(gè)人大2歲，第4個(gè)人比第3個(gè)人大2歲，……第2個(gè)人比第1個(gè)人大2歲，第1個(gè)人10歲，問(wèn)第5個(gè)人多大？age(5)age(4)age(3)age(2)age(1)=2+age(4)=2+age(3)=2+age(2)=2+age(1)

遞推回推=10=12=14=16=18數(shù)學(xué)模型10n=1age(n)=age(n-1)+2n>1#include<stdio.h>intage(intn){intc;if(n==1)c=10;elsec=2+age(n-1);return(c);}voidmain()

{printf(“%d\n”,age(5));}遞歸的本質(zhì)將大問(wèn)題的求解轉(zhuǎn)化為較小問(wèn)題的求解持續(xù)不斷的分解過(guò)程最終將問(wèn)題化簡(jiǎn)成一個(gè)最基本的形式（該形式是一個(gè)已知解）

條件成立，進(jìn)行遞歸用if語(yǔ)句控制條件不成立，結(jié)束遞歸解決無(wú)終止遞歸調(diào)用的方法是：確定好結(jié)束遞歸的條件【例3：】用遞歸方法計(jì)算n!分析4!=4*3*2*14!=4*3!3!=3*2!......遞歸公式n!=1（n=0或1）n*(n-1)!

（n>1）#include<stdio.h>longfac(intn)

{longf;if(n==0||n==1)

f=1;elsef=n*fac(n-1);returnf;}voidmain(){printf("\n\t4!=%ld\n",fac(4));}f=fac(4);

n=4if(n==0||n==1)f=1;elsef=n*fac(n-1);return(f)n=3if(n==0||n==1)f=1;elsef=n*fac(n-1);return(f)n=2if(n==0||n==1)f=1;elsef=n*fac(n-1);return(f)n=1if(n==0||n==1)f=1;elsef=n*fac(n-1);return(f)

設(shè)n=44!遞歸結(jié)束條件244*3!6*43*2!2*1!12*31**21【例4：】求兩個(gè)整數(shù)的最大公約數(shù)求最大公約數(shù)可以采用輾轉(zhuǎn)相除法intgcd(inta,intb){ if(a%b==0)returnb; returngcd(b,a%b);}【例5：】使用遞歸算法生成斐波那契(Fibonacci)數(shù)列遞歸公式：f1=1(n=1)f2=1(n=2)fn=fn-1+fn-2(n≥3)intfib(intn){if(n<=2)

return1;else

returnfib(n-1)+fib(n-2);}【例6：】漢諾塔問(wèn)題問(wèn)題假設(shè)有三個(gè)分別命名為X，Y和Z的塔座，在塔座X上插有n個(gè)直徑大小各不相同、依從小到大編號(hào)為1，2，…，n的圓盤?，F(xiàn)要求將X軸上的n個(gè)圓盤移到塔座Z上，并按同樣的順序疊放移動(dòng)時(shí)必須遵循以下規(guī)則：每次只能移動(dòng)一個(gè)圓盤圓盤可以插在X，Y和Z中的任一塔座上任何時(shí)候都不能將一個(gè)較大的圓盤壓在較小的圓盤之上XYZ漢諾塔問(wèn)題分析n=1時(shí)將圓盤1從塔座X移到塔座ZXYZXYZ基本情形漢諾塔問(wèn)題分析n>1時(shí)利用塔座Z為輔助塔座，將壓在圓盤n之上的n-1個(gè)盤從塔座X移到塔座Y

（——與原問(wèn)題類似）將圓盤n從塔座X移到塔座Z利用塔座X為輔助塔座，將塔座Y上的n-1個(gè)圓盤移動(dòng)到塔座Z

（——與原問(wèn)題類似）XYZXYZXYZXYZ漢諾塔問(wèn)題設(shè)計(jì)move函數(shù)：移動(dòng)一個(gè)盤-把盤n從s塔移到d塔hanoi函數(shù)：移動(dòng)n個(gè)盤的漢諾塔問(wèn)題-把n個(gè)盤從x塔移到z塔，y塔作為輔助塔voidmove(intn,chars,chard);voidhanoi(intn,charx,chary,charz);漢諾塔問(wèn)題實(shí)現(xiàn)#include<stdio.h>voidmove(intn,chars,chard);voidhanoi(intn,charx,chary,charz);voidmain(){intn;printf("\tInputthenumberofdisks:");scanf("%d",&n);hanoi(n,'X','Y','Z');}voidhanoi(intn,charx,chary,charz){

if(n==1)move(n,x,z);else{hanoi(n-1,x,z,y);move(n,x,z);

hanoi(n-1,y,x,z