第06講棧與遞歸

1、1/44,Essential of Lecture Six ：,一、遞歸 二、漢諾塔問題 三、遞歸與非遞歸的轉(zhuǎn)化,第六講 棧與遞歸,難點(diǎn),2/44,一、遞歸,遞歸是程序設(shè)計(jì)中最有力的方法之一。優(yōu)點(diǎn)：采用遞歸編出的程序簡潔、清晰，程序結(jié)構(gòu)符合結(jié)構(gòu)化程序設(shè)計(jì)，可讀性好。問題：編譯程序是如何處理這類帶有遞歸調(diào)用功能的程序的？如果使用了無遞歸功能的程序設(shè)計(jì)語言，應(yīng)該如何設(shè)計(jì)和實(shí)現(xiàn)這類程序呢？,3/44,一、遞歸,遞歸: 在定義自身

2、的同時(shí)又出現(xiàn)了對(duì)自身的調(diào)用。直接遞歸函數(shù):如果一個(gè)函數(shù)在其定義體內(nèi)直接調(diào)用自己，則稱直接遞歸函數(shù)。間接遞歸函數(shù)：如果一個(gè)函數(shù)經(jīng)過一系列的中間調(diào)用語句，通過其它函數(shù)間接調(diào)用自己，則稱間接遞歸函數(shù)。,4/44,數(shù)學(xué)中常常利用遞歸手段來定義一些概念，如求階乘的運(yùn)算。n的階乘定義為： n * ( n – 1 ) ! n>0 n! =

3、 1 n=0,例如:,,顯然，該遞歸的出口是 0! =1。,5/44,求階乘的算法如下： long fac (int n) { long p; if (n==0|| n==1) p=1; else p=n*fac(n-1) ; return p; }v

4、oid main(){ long x=fac(5); cout<<x;},6/44,求階乘的算法如下： long fac (int n) { long p; if (n==0 || n==1) p=1; else p=n*fac(n-1) ; return p; },遞歸函

5、數(shù)包含：1、遞歸調(diào)用語句，如 fac (n-1)；2、基值判斷，如n==0 || n==1即為基值，保證了遞歸可以終止，滿足基值條件后的計(jì)算 p=1, 一般稱為最終計(jì)算；3、調(diào)用之后的返回處理。如 p= n * fac (n-1) ，是返回之后要進(jìn)行的操作。,7/44,,fac(2)=2,fac(1)=1,,fac(3)=6,,fac(4)=24,,fac(5)=120,,輸出,假設(shè)調(diào)用該遞歸函數(shù)的主函數(shù)為第0層，則從主函數(shù)調(diào)用

6、遞歸函數(shù)為進(jìn)入第1層；從第 i層遞歸調(diào)用本身為進(jìn)入“下一層”，即第 i+1 層。反之，退出第 i 層遞歸應(yīng)返回至“上一層”，即第 i-1 層。,遞歸層次:,8/44,為了保證遞歸函數(shù)正確執(zhí)行，系統(tǒng)需設(shè)立一個(gè)“遞歸工作?！弊鳛檎麄€(gè)遞歸函數(shù)運(yùn)行期間使用的數(shù)據(jù)存儲(chǔ)區(qū)。每一層遞歸所需信息構(gòu)成一個(gè)“工作記錄”，其中包括所有的實(shí)參、所有的局部變量以及上一層的返回地址。 每進(jìn)入一層遞歸，就產(chǎn)生一個(gè)新的工作記錄壓入棧頂。每退出一層遞歸就從棧頂彈

7、出一個(gè)工作記錄，則當(dāng)前執(zhí)行層的工作記錄必須是遞歸工作棧棧頂?shù)墓ぷ饔涗洠Q這個(gè)記錄為“活動(dòng)記錄”，并稱指示活動(dòng)記錄的棧頂指針為“當(dāng)前環(huán)境指針”。,遞歸工作棧,9/44,分治算法,分治算法與軟件設(shè)計(jì)的模塊化方法類似。為了解決一個(gè)大的問題，將一個(gè)規(guī)模為n的問題分解為規(guī)模較小的子問題，這些子問題互相獨(dú)立并且和原問題相同。分別解這些子問題，最后將將各個(gè)子問題的解合并得到原問題的解。 子問題通常與原問題相似，可以遞歸地使用分治策略來解決。,

8、設(shè)計(jì)遞歸算法的方法,遞歸算法就是在算法中直接或間接調(diào)用算法本身的算法。,使用遞歸算法的前提有兩個(gè)：,⑵規(guī)模最小的子問題具有直接解。,⑴原問題可以層層分解為類似的的子問題，且子問題比原問題的規(guī)模更小。,設(shè)計(jì)遞歸算法的方法,⑴尋找分解方法,⑵設(shè)計(jì)遞歸出口,10/44,遞歸算法具有兩個(gè)特性：,(1) 遞歸算法是一種分而治之、把復(fù)雜問題分解為簡單問題的求解問題方法，對(duì)求解某些復(fù)雜問題，遞歸算法的分析方法是有效的。,（2）遞歸算法的效率較低。,1

9、1/44,12/44,例：Hanoi塔問題,,傳說在古代印度的貝拿勒圣廟里，安裝著三根插至黃銅板上的寶石針，印度主神梵天在其中一根針上從下到上由大到小的順序放64片金圓盤，稱為梵塔，然后要僧侶輪流值班把這些金圓盤移到另一根針上，移動(dòng)時(shí)必須遵守如下規(guī)則： （1）每次只能移動(dòng)一個(gè)盤片； （2）任何時(shí)候大盤片不能壓在小盤片之上； （3）盤片只允許套在三根針中的某一根上。 這位印度主神號(hào)稱如

10、果這64片盤全部移到另一根針上時(shí)，世界在一聲霹靂中毀滅，Hanoi塔問題又稱“世界末日”問題。下圖為3階Hanoi塔的初始情況。,,13/44,,n階Hanoi塔問題Hanoi(n, a, b, c)，當(dāng)n=0時(shí)，沒盤子可供移動(dòng)，什么也不做；當(dāng)n=1時(shí)，可直接將1號(hào)盤子從a軸移動(dòng)到c軸上；當(dāng)n=2時(shí)，可先將1號(hào)盤子移動(dòng)到b軸，再將2號(hào)盤子移動(dòng)到c軸，最后將1號(hào)盤子移動(dòng)到c軸；對(duì)于一般n>0的一般情況可采用如下分治策略進(jìn)行移動(dòng)

11、 （1）將1至n-1號(hào)盤從 a 軸移動(dòng)至 b 軸，可遞歸求解Hanoi(n-1, a, c, b)； （2）將 n號(hào)盤從 a 軸移動(dòng)至 c 軸； （3）將1至n-1號(hào)盤從b軸移動(dòng)至c軸，可遞歸求解 Hanoi(n-1, b, a, c)。,,14/44,例：分析Hanoi塔問題移動(dòng)圓盤的次數(shù),,設(shè)T(n)表示n個(gè)圓盤的Hanoi塔問題移動(dòng)圓盤的次數(shù)，顯然T(0)=0，對(duì)于n>0的一般情況采用如

12、下分治策略： （1）將1至n-1號(hào)盤從 a 軸移動(dòng)至 b 軸，可遞歸求解Hanoi(n-1, a, c, b)； （2）將 n號(hào)盤從 a 軸移動(dòng)至 c 軸； （3）將1至n-1號(hào)盤從b軸移動(dòng)至c軸，可遞歸求解 Hanoi(n-1, b, a, c)。 在（1）與（3）中需要移動(dòng)圓盤次數(shù)T(n-1)，（2）需要移動(dòng)一次圓盤?？傻萌缦碌年P(guān)系：T(n)=2T(n-1)+

13、1展開上式可得：T(n)=2T(n-1)+1=2[2T(n-2)+1]+1=22T(n-2)+1+2……=2nT(n-n)+1+2+…+2n-1=2n-1,,15/44,二、漢諾塔問題的遞歸算法,void move (char x, int n, char y){ cout<<"移動(dòng)"<<n<<"號(hào)盤子"

14、;<<"從柱子"<<x<<"到柱子"<<y;},16/44,Hanoi(n, x, y, z) 可以分成三個(gè)子問題：問題1.Hanoi(n-1, x, z, y) //將X柱上的n-1個(gè)圓盤借助Z柱移到Y(jié)柱上，此時(shí)X柱只剩下第n個(gè)圓盤；問題2.Move( n, x， z) //將X柱上的第n個(gè)移動(dòng)到Z柱問題3.Hanoi(n-1, y,

15、 x, z) //將Y柱上的n-1個(gè)圓盤借助X柱移到Z柱上；n=1時(shí)可以直接求解,17/44,三、遞歸程序到非遞歸程序的轉(zhuǎn)換,選擇遞歸 還是 非遞歸： 采用遞歸方式實(shí)現(xiàn)問題的算法程序具有結(jié)構(gòu)清晰、讀性好、易于理解等優(yōu)點(diǎn)，但遞歸程序較之非遞歸程序無論是空間需求還是時(shí)間需求都更高，因此在希望節(jié)省存儲(chǔ)空間和追求執(zhí)行效率的情況下，人們更希望使用非遞歸方式實(shí)現(xiàn)問題的算法程序。,18/44,實(shí)戰(zhàn):,m個(gè)蘋果放到n個(gè)盤子上(允許有空盤子

16、)，問有多少種放法?,,遞歸出口：沒有蘋果或者盤子剩下1個(gè)：1種,蘋果數(shù)少于盤子數(shù)：去掉多余的盤子,蘋果數(shù)多于盤子數(shù): 至少有一個(gè)盤子空著和 所有的盤子都有蘋果(從每個(gè)盤子拿走一個(gè)蘋果),19/44,實(shí)戰(zhàn):,以下是該函數(shù)的程序段，請(qǐng)補(bǔ)充完整。 int f(int m, int n)        { 

17、 if(m==0 || n==1) return ; //沒有蘋果或者盤子剩下1個(gè)   if(m<n) return ; //蘋果數(shù)少于盤子數(shù)，只需要相同的盤子數(shù)就足夠了    return f(m,n-1) + f(m-n, );

18、 //蘋果數(shù)多于盤子數(shù) },20/44,實(shí)戰(zhàn):,以下是該函數(shù)的程序段，請(qǐng)補(bǔ)充完整。 int f(int m, int n)        {  if(m==0 || n==1) return 1 ; //沒有蘋果或者盤子剩下1個(gè) &#