模塊化編程-遞歸本講內(nèi)容：遞歸的概念遞歸方法求n！遞歸方法解決Hanoi問題復(fù)習(xí)：函數(shù)的定義與調(diào)用1.為什么要引入函數(shù)①

模塊化編程的需要。②

軟件重用的需要。2.函數(shù)的定義函數(shù)類型函數(shù)名(類型參數(shù)1,類型參數(shù)2,…){聲明部分

語句部分}表示函數(shù)的返回值類型合法的標(biāo)識符表示函數(shù)的輸入3.函數(shù)的調(diào)用函數(shù)名(實際參數(shù)1，實際參數(shù)2，…)復(fù)習(xí)：函數(shù)的定義與調(diào)用void

list(void){printf("******\n");}該函數(shù)沒有參數(shù)，也沒有返回值voidmax(inta,intb){intt;if(a>b)t=a;elset=b;

printf("%d\n",t);}該函數(shù)有參數(shù)，但沒有返回值list();//函數(shù)調(diào)用max(3,5);//函數(shù)調(diào)用max(x,y);max(2*x,y+8);floatfunc(intm){inti;floatfact=1;for(i=1;i<=m;i++)fact=fact*i;

returnfact;}該函數(shù)有參數(shù)，也有返回值復(fù)習(xí)：函數(shù)的定義與調(diào)用voidmain(){intn;floatr;scanf("%d",&n);

r=func(n);

printf("%d!=%.0f\n",n,r);}函數(shù)調(diào)用voidfunc(intm)

//無返回值{inti;floatfact=1;for(i=1;i<=m;i++)fact=fact*i;

printf("%d!=%.0f\n",m,fact);}voidmain(){intn;scanf("%d",&n);func(n);

}復(fù)習(xí)：函數(shù)的嵌套1.函數(shù)的定義是平行的，獨立的。不允許嵌套定義。2.函數(shù)允許嵌套調(diào)用voidfun(){voidg(){printf("hello");}}

voidf1(){putchar('a');}

voidf2(){f1()putchar('t');}voidmain(){putchar('c');f2();}嵌套定義嵌套調(diào)用f1函數(shù)遞歸調(diào)用的概念:在調(diào)用一個函數(shù)的過程中又出現(xiàn)直接或間接地調(diào)用該函數(shù)自己，稱為函數(shù)的遞歸調(diào)用。（遞歸就是“自己調(diào)用自己”）f函數(shù)調(diào)用f函數(shù)f1函數(shù)調(diào)用f2函數(shù)f2函數(shù)調(diào)用f1函數(shù)直接調(diào)用間接調(diào)用5.5.1遞歸函數(shù)2.用遞歸求解問題的特點(1)遞歸的終止條件存在某個特定條件,在此條件下可以得到指定的解.(2)存在導(dǎo)致問題求解的遞歸方式對任意給定的條件有明確的定義規(guī)則,可以產(chǎn)生新的狀態(tài),并將最終導(dǎo)出終止?fàn)顟B(tài).3.優(yōu)點:程序簡潔,代碼緊湊,可讀性強缺點:占用存儲空間較多,時間效率較差5.5.1遞歸函數(shù)1n=0,1n*(n-1)!n>1n!=遞歸的終止條件遞歸方式fac(4)=4*fac(3)返回值6返回值2返回值1fac(3)=3*fac(2)fac(2)=2*fac(1)fac(1)=1求fac(4)返回值24如果求階乘的函數(shù)為fac，那么求4的階乘用fac(4)表示例1-1:用遞歸的方法求n!double

Fac(intn){doublef;if(n==0||n==1)f=1;elsef=n*Fac(n-1);returnf;}1n=0,1n*(n-1)!n>1

n!=

if(n<0){printf("error!");

exit(0);}例1-1

:用遞歸的方法求n!程序是否完善?遞歸結(jié)束條件遞歸的方式能否替換為Fac(n)

=n*Fac(n-1)？#include<stdio.h>#include<stdlib.h>double

fac(intn){doublef;if(n<0){printf("error!");exit(0);}

if(n==0||

n==1)f=1;elsef=n*fac(n-1);returnf;}voidmain(){intm;

doubley;scanf("%d",&m);

y=fac(m);

printf("%d!=%.0lf\n",m,y);}退出程序遞歸調(diào)用n！的值增長很快,因此采用較高的數(shù)據(jù)類型注意正確輸出double型數(shù)據(jù)例1-1

:用遞歸的方法求n!main函數(shù)輸入m③y=fac(m)輸出y⑥調(diào)用facmn③因3!=0,1f=3*fac(3-1)返回f⑥調(diào)用facmn②返回f②返回f①因2!=0,1f=2*fac(2-1)調(diào)用facmn

①因1==1f=1結(jié)束計算fac(3)的遞歸調(diào)用過程:例1-2:

Hanoi問題問題描述：設(shè)A,B,C是3個塔座。在塔座A上有n個圓盤,這些圓盤自下而上,由大到小的疊放。要求將A上的圓盤移到C上,并仍按同樣順序疊放。移動圓盤應(yīng)遵守以下規(guī)則：規(guī)則1：每次只能移動1個圓盤規(guī)則2：任何時刻都不允許將大圓盤壓在小圓盤之上規(guī)則3：在滿足規(guī)則1和2的前提下,可將圓盤移至任一塔座上ABC3個圓盤的移動過程演示A→CA→B例1-2:

Hanoi問題ABC3個圓盤的移動過程演示C→B例1-2:

Hanoi問題ABC3個圓盤的移動過程演示A→C例1-2:

Hanoi問題ABC3個圓盤的移動過程演示B→AB→C例1-2:

Hanoi問題ABCn較大時怎么辦？3個圓盤的移動過程演示A→Cn個圓盤需要2n-1次移動n=64時,需要1844億億次移動若每次移動用1秒,則需要600億年！3個圓盤一共需要7次移動：A→C，A→B，C→B，A→C，B→A，B→C，A→C例1-2:

Hanoi問題移動步驟：①(n-1)個圓盤AB②第n個圓盤AC③(n-1)個圓盤BCACBn個圓盤的移動方法：n個圓盤分為2部分上面(n-1)個圓盤最下面的第n號圓盤(n-1)個圓盤怎么移動？遞歸何時結(jié)束？例1-2:

Hanoi問題第n個圓盤ACn=1(n-1)個圓盤AB第n個圓盤AC(n-1)個圓盤BCn>1voidHan(intn,intA,intB,intC){if(n==1)Move(n,A,C);else{Han(n-1,A,C,B);Move(n,A,C);Han(n-1,B,A,C);}}遞歸法求解hanoi問題//將n-1個盤子從A移到B,借助于C//將n-1個盤子從B移到C,借助于A//將第n個盤子從A移到C//將n個盤子從A移到C,借助于B//將1個盤子從A移到C請?zhí)貏e注意這3個參數(shù)的順序例1-2:

Hanoi問題Han(3,A,B,C){if(n==1)

Move(n,A,C);else{

Han(2,A,C,B);

Move(3,A,C);

Han(2,B,A,C);

}}Han(2,A,C,B){if(n==1)Move(n,A,B);else{

Han(1,A,B,C);

Move(2,A,B);Han(1,C,A,B);

}}Han(1,A,B,C){if(n==1)

Move(1,A,C);}Han(1,C,A,B){if(n==1)

Move(1,C,B);}Han(2,B,A,C){if(n==1)Move(n,B,C);else{

Han(1,B,C,A);

Move(2,B,C);Han(1,A,B,C);

}}Han(1,B,C,A){if(n==1)

Move(1,B,A);}Han(1,A,B,C){if