版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
數(shù)據(jù)結(jié)構(gòu)(第六章遞歸)
DataStructures胡學(xué)鋼張晶計算機(jī)與信息學(xué)院2009年2月1第六章遞歸
(Recursive)
6.1遞歸的定義
6.2遞歸的內(nèi)部實現(xiàn)原理
6.3遞歸程序的閱讀
6.4遞歸程序的正確性證明
6.5遞歸程序的模擬——轉(zhuǎn)換為非遞歸
2第六章遞歸6.1遞歸的定義
(1)作為一種程序形式的遞歸:在函數(shù)的執(zhí)行過程中調(diào)用自身??赡苡袃煞N形式:直接遞歸----在函數(shù)體內(nèi)調(diào)用自身,間接遞歸----函數(shù)中調(diào)用其他函數(shù),并由其他函數(shù)調(diào)用自身
(2)更是作為一種程序設(shè)計(算法設(shè)計)的技術(shù)的遞歸。因為一些問題的求解具有這樣的特點:原問題可以分解為若干子問題分別進(jìn)行求解,適當(dāng)?shù)睾喜⒆訂栴}的解可以得到原問題的解。而子問題的求解方式與原問題的求解相同,因而需要調(diào)用相同的函數(shù)來實現(xiàn),由此而涉及到遞歸技術(shù)。36.1遞歸的定義例6.1
階乘n!的定義如下:
1當(dāng)n=0時n!=n(n-1)!當(dāng)n>0時對應(yīng)的求階乘的遞歸函數(shù)如下:intfact(intn){if(n==0)return1;
elsereturnn*fact(n–1);}
函數(shù)fact的函數(shù)體內(nèi)調(diào)用自身,即fact(n–1);
46.1遞歸的定義例6.2
下面是一個遞歸函數(shù)fn的定義----斐波諾契函數(shù):f1=1f2=2
fn=fn-1+fn-2n>2例6.3
下面是一個對鏈表執(zhí)行操作的函數(shù),請判斷其功能。
voidprint(node*L){if(L!=NULL){cout<<L->data;print(L->next);}}56.1遞歸的定義遞歸函數(shù)的一般形式:
voidPname(參數(shù)表){if(條件)簡單操作;else{簡單操作;Pname(實參表);簡單操作;[Pname(實參表);簡單操作;]}}遞歸出口可能有多次的調(diào)用例如:在階乘函數(shù)intfact(intn){if(n==0)return1;
elsereturnn*fact(n–1);}
遞歸出口是n==0函數(shù)也可以是其他類型;調(diào)用方式自然也不同66.2遞歸的內(nèi)部實現(xiàn)原理6.2.1一般函數(shù)的內(nèi)部實現(xiàn)程序A:…a1;B;a2;B;a3;B;a4;…程序A’:…a1;B;a2;B;a3;B;a4;…子程序BCallBCallBCallB76.2遞歸的內(nèi)部實現(xiàn)原理(1)從程序的執(zhí)行過程來討論:在執(zhí)行調(diào)用時,計算機(jī)內(nèi)部至少執(zhí)行如下操作:(a)保存返回地址,也就是將返回地址入棧。(b)為被調(diào)子程序準(zhǔn)備數(shù)據(jù):計算實在參數(shù)的值,并賦給對應(yīng)的形參。(c)轉(zhuǎn)入子程序執(zhí)行。
在執(zhí)行返回操作時,計算機(jī)內(nèi)部至少執(zhí)行如下操作:
(a)
從棧頂取出返回地址,并出棧。(b)按返回地址返回。86.2遞歸的內(nèi)部實現(xiàn)原理(2)關(guān)于局部變量的實現(xiàn)的討論在執(zhí)行調(diào)用時,內(nèi)部操作如下:(a)保存返回地址入棧,同時在棧頂為被調(diào)函數(shù)的局部變量和形參開辟存儲空間。
(b)為被調(diào)子程序準(zhǔn)備數(shù)據(jù):計算實在參數(shù)的值,并賦給對應(yīng)的形參(在棧頂)。(c)轉(zhuǎn)入子程序執(zhí)行。
在執(zhí)行返回操作時,計算機(jī)內(nèi)部至少執(zhí)行如下操作:(a)從棧頂取出返回地址,并出棧(同時撤消了被調(diào)函數(shù)的局部變量和形參)。(b)按返回地址返回。96.2遞歸的內(nèi)部實現(xiàn)原理(3)關(guān)于返回值的實現(xiàn)的討論
返回操作的內(nèi)部實現(xiàn)修改為如下幾項:(a)若函數(shù)需要返回值,將其值保存到回傳變量中。(b)從棧頂取出返回地址,并退棧。(c)按返回地址返回。(d)在返回后自動執(zhí)行以下操作:若函數(shù)需要返回值,從回傳變量中取出所保存的值,并傳送到相應(yīng)的變量或位置上。106.2遞歸的內(nèi)部實現(xiàn)原理6.2.2遞歸調(diào)用的內(nèi)部實現(xiàn)原理可將遞歸調(diào)用理解為:調(diào)用與自己有相同的代碼和同名的局部變量的子程序。由此可知:執(zhí)行遞歸調(diào)用及返回的內(nèi)部實現(xiàn)與前述實現(xiàn)相同:
在執(zhí)行遞歸調(diào)用時,計算機(jī)內(nèi)部執(zhí)行如下操作:
(a)開辟棧頂存儲空間,用于保存:返回地址、被調(diào)層(函數(shù))中的形參和局部變量的值。
(b)為被調(diào)層(函數(shù))準(zhǔn)備數(shù)據(jù):計算實參的值,并賦給對應(yīng)的形參(在棧頂元素中)。
(c)轉(zhuǎn)入子程序執(zhí)行。
116.2遞歸的內(nèi)部實現(xiàn)原理在執(zhí)行返回操作時,內(nèi)部實現(xiàn)如下:(a)若函數(shù)需要返回值,將其值保存到回傳變量中。(b)從棧頂取出返回地址,并退棧
----同時撤消被調(diào)層子程序的局部變量及形參。(c)按返回地址返回。(d)在返回后自動執(zhí)行如下操作:若函數(shù)需要返回值,從回傳變量中取出所保存的值,并傳送到相應(yīng)的實變參或位置上。126.2遞歸的內(nèi)部實現(xiàn)原理例:根據(jù)遞歸程序的內(nèi)部實現(xiàn)過程求解returnhcf(28,6)的執(zhí)行結(jié)果。inthcf(intM,intN){(1)if(N==0)(2){cout<<M;returnM;}(3)elsereturnhcf(N,M%N);(4)}解:為便于描述,程序的每一行用其序號標(biāo)識,用序號0表示最外層調(diào)用的下面(即表示返回地址)。執(zhí)行過程用表3-1表示。說明:
后面一些行中最左邊的字母序號為接著上一行第三列的內(nèi)容,即表示上一行中調(diào)用或返回的余下操作的序號,只是出于棧的描述的需要而分開。13returnhcf(28,6)的執(zhí)行結(jié)果返回:c,d0返回:a,b2語句操作序號回傳變量棧狀態(tài):(返址,m,n)輸出結(jié)果0調(diào)用:a,b
(0,28,6)調(diào)用:c1,3調(diào)用:a,b(0,28,6)(4,6,4)
調(diào)用:c1,3調(diào)用:a,b(0,28,6)(4,6,4)(4,4,2)調(diào)用:c1,3調(diào)用:a,b(0,28,6)(4,6,4)(4,4,2)(4,2,0)調(diào)用:c1,2,4返回:a,b2(0,28,6)(4,6,4)(4,4,2)2返回:c,d4返回:a,b2(0,28,6)(4,6,4)
返回:c,d4返回:a,b2(0,28,6)146.3遞歸程序的閱讀例:voidp(intn){調(diào)用p(3)
if(n>0){cout<<n;p(n-1);}
}n=1n=2P(3)3P(2)-1n=3n=0與p(3)等價的操作2P(1)1P(0)有效輸出結(jié)果的操作次序如紅線所示。輸出結(jié)果為3,2,1156.3遞歸程序的閱讀對下面算法p(n),用前述方法求出調(diào)用p(3)所得到的輸出結(jié)果。voidp(intn){if(n>0){
cout<<n;p(n-1);cout<<n;
}}166.3遞歸程序的閱讀例:函數(shù)F定義如下,用上述方法求出F(6)的值。
intF(intN){if(N<=2)return1;return(2*F(N-1)+3*F(N-2));}解:
F(6)2*F(5)3*F(4)2*F(4)+3*F(3)2*F(3)+3*F(2)2*F(3)+3*F(2)2*F(2)+3*F(1)2*F(2)+3*F(1)2*F(2)+3*F(1)+11115111551131341121最終解為121176.4遞歸程序的正確性證明例證明下面的函數(shù)fact(n)所實現(xiàn)的是球階乘的功能,即1當(dāng)n=0時fact(n)等價于n!=n(n-1)!當(dāng)n>0時fact(n)函數(shù)如下:intfact(intn){
if(n==0)return1;elsereturnn*fact(n–1);}證明:(1)當(dāng)n=0時,調(diào)用函數(shù)得到值為1,符合函數(shù)定義,功能正確。
(2)假設(shè)0≤n<k時,函數(shù)正確,即函數(shù)fact(n)的結(jié)果為n(n-1)!,則當(dāng)n=k>0時,由程序可知fact(n)=n*fact(n-1)=n*(n-1)(n-2)!=n*(n-1)!,功能正確。綜上所述,程序功能正確。186.4遞歸程序的正確性證明例:對右面的函數(shù),證明:(1)調(diào)用P(n)所產(chǎn)生的輸出項數(shù)為2n-1。(n≥0)(2)調(diào)用P(n)所產(chǎn)生的輸出項中的奇數(shù)項為1。(n≥0)證明(1):
(1)當(dāng)n=0時,由程序描述可知,不產(chǎn)生輸出,即項數(shù)為0,符合命題。
(2)設(shè)0≤n<k時,命題正確,即調(diào)用P(n)產(chǎn)生2n-1項輸出,則當(dāng)n=k時,由程序描述可知,要依次執(zhí)行如下操作:P(n-1);cout<<n;P(n-1);
其中第二個操作產(chǎn)生一個輸出,由假設(shè)知第一個和第三個操作分別產(chǎn)生2n-1-1項輸出,因此總輸出項數(shù)為2(2n-1-1)+1=2n-1。符合命題。綜上所述,命題正確。問題(2)留給讀者自己練習(xí)。voidP(intn){if(n>0){P(n-1);cout<<n;P(n-1);}}196.4遞歸程序的正確性證明練習(xí):(1)證明print(L)能輸出鏈表L中所有結(jié)點值。
voidprint(linkL){if(L!=NULL){
cout<<L->data;
print(L->next);}}(2)證明print(L)能按反序輸出鏈表L中所有結(jié)點值。
voidprint(linkL){if(L!=NULL){
print(L->next);
cout<<L->data;
}}206.5遞歸程序的模擬——轉(zhuǎn)換為非遞歸背景:為何要將遞歸程序轉(zhuǎn)換為等價的非遞歸程序?遞歸程序雖然有良好的可讀性,但由于以下一些原因,需要將遞歸程序轉(zhuǎn)化為等價的非遞歸程序:時間花費空間開銷一部分編程環(huán)境的不支持,或者編寫起來復(fù)雜。如何轉(zhuǎn)換?一種方式是重新設(shè)計
——沒有利用已有的工作基礎(chǔ)還有一種方式是對給定的遞歸程序,用一組規(guī)則進(jìn)行等價的轉(zhuǎn)換。問題是,規(guī)則包括哪些?216.5遞歸程序的模擬機(jī)械地將任何一個遞歸程序轉(zhuǎn)換為與其等價的非遞歸程序五條規(guī)則:(1)設(shè)置一個棧(不妨用S表示),并且開始時將其置為空。(2)在子程序入口處設(shè)置一個標(biāo)號(不妨設(shè)為L0)。(3)對子程序中的每一遞歸調(diào)用,用以下幾個等價操作來替換:(a)保留現(xiàn)場:開辟棧頂存儲空間,用于保存返回地址(不妨用Li,i=1,2,3,…)、調(diào)用層中的形參和局部變量的值(最外層調(diào)用不必考慮)。(b)準(zhǔn)備數(shù)據(jù):為被調(diào)子程序準(zhǔn)備數(shù)據(jù),即計算實在參數(shù)的值,并賦給對應(yīng)的形參(c)轉(zhuǎn)入(子程序)執(zhí)行,即執(zhí)行g(shù)otoL0。(d)在返回處設(shè)一個標(biāo)號Li(i=1,2,3,…),并根據(jù)需要設(shè)置以下語句:若函數(shù)需要返回值,從回傳變量中取出所保存的值并傳送到相應(yīng)的位置。程序B:…a1;B;a2;B;a3;B;a4;…CallBCallBCallB226.5遞歸程序的模擬——轉(zhuǎn)換為非遞歸
(4)對返回語句,可用以下幾個等價操作來替換:如果棧不空,則依次執(zhí)行如下操作,否則結(jié)束本子程序,返回。(a)回傳數(shù)據(jù):若函數(shù)需要返回值,將其值保存到回傳變量中。(b)恢復(fù)現(xiàn)場:從棧頂取出返回地址(不妨保存到X中)及各變量、形參值,并退棧。(c)返回:按返回地址返回(即執(zhí)行g(shù)otoX)。(5)對其中的非遞歸調(diào)用和返回操作可照搬。例:將下面遞歸程序轉(zhuǎn)換為等價的非遞歸程序。
voidP(intn){if(n>0){P(n–1);cout<<n;}}236.5遞歸程序的模擬——轉(zhuǎn)換為非遞歸解:為了實現(xiàn)轉(zhuǎn)換,需要按照規(guī)則對下列各部分分別進(jìn)行轉(zhuǎn)換:
voidP(intn){
初始化棧-------規(guī)則1設(shè)入口標(biāo)號----規(guī)則2
P(n-1);
if(n>0){cout<<n;}遞歸調(diào)用p(n-1)的替換----規(guī)則3非遞歸調(diào)用和返回部分照搬--規(guī)則5返回部分的替換----規(guī)則4
}246.5遞歸程序的模擬——轉(zhuǎn)換為非遞歸由此得結(jié)果如下:
voidP1(intn){
}stacks;
L0:
s.push(n,L1);
n=n-1;gotoL0;
L1:
if(!s.empty()){
s.pop(n,X);gotoX;
}
if(n>0){cout<<n;}
//規(guī)則1
//規(guī)則2
//規(guī)則5
//規(guī)則3.a
//規(guī)則3.b
//規(guī)則3.c
//規(guī)則3.d
//規(guī)則5
//規(guī)則4
//規(guī)則4.b
//規(guī)則4.c
初始化棧-------規(guī)則1設(shè)入口標(biāo)號----規(guī)則2遞歸調(diào)用p(n-1)的替換----規(guī)則3非遞歸調(diào)用和返回部分照搬--規(guī)則5返回部分的替換----規(guī)則4
P(n-1);
256.5遞歸程序的模擬——轉(zhuǎn)換為非遞歸對應(yīng)的程序如下:voidP1(intn){stacks;L0:if(n>0){s.push(n,L1);
n=n-1;gotoL0;
L1:cout<<n;}if(!s.empty()){
s.pop(n,X);gotoX;
}}程序中的地址X代表什么?若不清楚,則無法轉(zhuǎn)換。對此稍作分析即可找到答案:X取自棧中,而所有入棧的地址只有一個值,即L1。因此,即使這一地址不入棧也可知道其值。由此得如下的簡化規(guī)則。簡化規(guī)則1:如果遞歸程序中只有一處遞歸調(diào)用,則在轉(zhuǎn)換時,返回地址不必入棧。由此可簡化程序,得到流程圖及相應(yīng)的程序。
此處的地址X代表什么?若不清楚,則無法轉(zhuǎn)換。266.5遞歸程序的模擬——轉(zhuǎn)換為非遞歸流程圖為:voidP1(intn){stacks;L0:if(n>0){s.push(n);
n=n-1;gotoL0;
L1:cout<<n;}if(!s.empty()){
s.pop(n);
gotoL1;
}}
stacks;n>0s.push(n);n=n-1;
s.empty()?
s.pop(n);
L1:cout<<n;NYL0NY276.5遞歸程序的模擬——轉(zhuǎn)換為非遞歸由此流程圖得程序如下:voidP1(intn){stacks;while(n>0){s.push(n);n=n-1;}while(!s.empty()){
s.pop(n);cout<<n;
}}
stacks;n>0s.push(n);n=n-1;
s.empty()?
s.pop(n);
L1:cout<<n;NYL0NY286.5遞歸程序的模擬——轉(zhuǎn)換為非遞歸例:將下面遞歸程序轉(zhuǎn)換為等價的非遞歸程序。voidP(intn){if(n>0){cout<<n;P(n–1);}}解:按轉(zhuǎn)換規(guī)則及簡化規(guī)則進(jìn)行轉(zhuǎn)換細(xì)節(jié)不再贅述,結(jié)果如右圖所式:
voidP1(intW){stackS;//規(guī)則1L0://規(guī)則2if(n>0)//規(guī)則5{cout<<n;//規(guī)則5S.push(n);//規(guī)則3.an=n-1;//規(guī)則3.bgotoL0;//規(guī)則3.cL1://規(guī)則3.d}if(!S.empty())//規(guī)則4{S.pop(n);//規(guī)則4.bgotoL1;//規(guī)則4.c}}296.5遞歸程序的模擬——轉(zhuǎn)換為非遞歸voidP1(intn){stacks;L0:if(n>0){cout<<n;s.push(n);n=n-1;gotoL0;L1:}if(!s.empty()){s.pop(n);gotoL1;}}
stackS;n>0cout<<n;s.push(n);n=n-1;
s.empty()?
s.pop(n);
L1:NYL0NY306.5遞歸程序的模擬——轉(zhuǎn)換為非遞歸由此流程圖得程序如下:voidP1(intn){stacks;while(n>0){cout<<n;s.push(n);n=n-1;}while(!s.empty())s.pop(n);}
觀察一下流程圖及程序,可以發(fā)現(xiàn):最后的退棧操作所退出的數(shù)據(jù)根本沒有使用就丟掉了,這說明所保存的這些數(shù)據(jù)是無用的。由此討論可得關(guān)于尾遞歸的簡化規(guī)則。
stacks;n>0cout<<n;s.push(n);n=n-1;
s.empty()?
s.pop(n);
L1:NYL0NY316.5遞歸程序的模擬——轉(zhuǎn)換為非遞歸簡化規(guī)則2:在模擬尾遞歸調(diào)用時,不必執(zhí)行入棧操作。下面用簡化規(guī)則2重新模擬上例程序。由于僅有這一個尾遞歸,不必執(zhí)行入棧操作,因而不需要用到棧。轉(zhuǎn)換結(jié)果如下:
voidP1(intn){L0://規(guī)則2if(n>0){//規(guī)則5cout<<n;//規(guī)則5s.push(n);//簡化規(guī)則2n=n-1;//規(guī)則3.bgotoL0;//規(guī)則3.c}}326.5遞歸程序的模擬——轉(zhuǎn)換為非遞歸流程圖為:
由此得程序如下:
voidP1(intn){while(n>0){cout<<n;n=n-1;}}n>0cout<<n;n=n-1;L0:NY33練習(xí)例:將下面遞歸程序轉(zhuǎn)換為等價的非遞歸程序。voidP(intn){if(n>0){cout<<n;P(n–1);P(n–1);}}voidP(intn){stacks;L0:if(n>0){cout<<n;s.push(n);n=n-1;gotoL0;L1:
n=n-1;gotoL0;L2:
}if(!s.empty()){s.pop(n);gotoL1;}}
346.6遞歸技術(shù)的應(yīng)用舉例求集合{1,2,…,N}的冪集。設(shè)計算法求n個元素的全排列。35課后練習(xí)寫出下面程序或調(diào)用的結(jié)果:(1)voidP1(intW){intA,B;A=W-1;B=W+1;cout<<A<<B;}voidP2(Wint){intA,B;A=2*W;B=W*W;P1(A);P1(B);cout<<A<<B;}
調(diào)用P2(5);(2)intHcf(intM,intN){intH;while(N!=0){H=M%N;M=N;N=H;}cout<<M;returnM;}
調(diào)用cout<<Hcf(100,350);cout<<Hcf(200,49);(3)intHcf(intM,intN){intH;while(N!=0){H=MmodN;M=N;N=H}returnM;}voidreduce(intM1,intN1;int*M2,int*N2){intR;R=Hcf(M1,N1);*M2=M1/R;*N2=N1/R;
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 眉山藥科職業(yè)學(xué)院《軟件工程與》2023-2024學(xué)年第一學(xué)期期末試卷
- 2024年度校園食堂承包與食品安全監(jiān)管合同3篇
- 2024年度汽車貸款信用保證保險合同3篇
- 2024年標(biāo)準(zhǔn)版房地產(chǎn)項目資本金監(jiān)管協(xié)議版B版
- 2024年版:教育貸款申請合同3篇
- 影調(diào)的造型作用
- 呂梁師范高等??茖W(xué)?!吨袊鞘邪l(fā)展史》2023-2024學(xué)年第一學(xué)期期末試卷
- 2024全新指紋鎖智能家居控制系統(tǒng)集成合同2篇
- 2024年特色手工藝品買賣合同詳細(xì)
- 2024年標(biāo)準(zhǔn)膩子施工勞務(wù)分包合同樣本版B版
- 管道承諾質(zhì)量保證書范本
- DB14-T 1049.1-2020 山西省用水定額 第1部分:農(nóng)業(yè)用水定額
- 10以內(nèi)連加連減練習(xí)題(直接打印版)
- 預(yù)防性侵害安全教育
- 2024秋期國家開放大學(xué)《機(jī)械設(shè)計基礎(chǔ)》一平臺在線形考(形考任務(wù)1至4)試題及答案
- 2024秋期國家開放大學(xué)專科《液壓與氣壓傳動》一平臺在線形考(形考任務(wù)+實驗報告)試題及答案
- 北師版八年級數(shù)學(xué)上冊 第四章 一次函數(shù)(壓軸專練)(十大題型)
- 計算機(jī)網(wǎng)絡(luò)技術(shù)基礎(chǔ)考核試卷
- 2024中國鋁業(yè)集團(tuán)限公司應(yīng)屆高校畢業(yè)生招聘高頻難、易錯點500題模擬試題附帶答案詳解
- 第1課時淘氣的一天(教學(xué)設(shè)計)-2024-2025學(xué)年北師大版(2024)一年級上冊數(shù)學(xué)
- 醫(yī)院醫(yī)技科室與臨床科室定期溝通制度
評論
0/150
提交評論