數(shù)據(jù)結(jié)構(gòu) 教學(xué)課件 作者 戴敏5

數(shù)據(jù)結(jié)構(gòu)第5章遞歸本章目標(biāo)5.1

遞歸的定義5.2遞歸算法的工作原理5.3遞歸算法的實(shí)現(xiàn)形式5.4遞歸算法的分類5.5遞歸的簡單應(yīng)用舉例35.1

遞歸的定義遞歸的定義在數(shù)學(xué)和程序設(shè)計(jì)方法學(xué)中遞歸的定義是：若一個(gè)對象部分地包含它自己，或用它自己給自己定義，則稱這個(gè)對象是遞歸的；若一個(gè)過程直接或間接地調(diào)用自己，則稱這個(gè)過程是遞歸過程5遞歸的定義在以下三種情況下，常常要用到遞歸的方法定義是遞歸的數(shù)學(xué)上常用的階乘函數(shù)、冪函數(shù)、Fibonacci數(shù)列等，它們的定義和計(jì)算都是遞歸的例如階乘函數(shù) {1當(dāng)n=0時(shí) n!= < {n·(n-1)!當(dāng)n>0時(shí)階乘可以用下面的遞歸函數(shù)來表達(dá)longFactorial(longn){

if(n==0)return1;

else

returnn*Factorial(n-1);}6遞歸的定義類似地，可給出x的n次冪函數(shù)的一個(gè)遞歸定義：{1n=0 xn=< {x·xn-1n>0可以直接寫出計(jì)算xn的power函數(shù)doublepower(doublex,intn){

if(n==0)return1.0;

else

returnx*power(x,n-1);}7遞歸的定義類似地，可給出計(jì)算Fibonacci數(shù)列的函數(shù)Fib(n)的定義： {n當(dāng)n=0,1時(shí) Fib(n)=< {Fib(n-1)+Fib(n-2) 當(dāng)n>1時(shí)該序列為0,1,1,2,3,5,8,13,21,34,55,89,…Fabonacci數(shù)列對應(yīng)的函數(shù)為longFib(longn){

if(n<=1)returnn;

else

return

Fib(n-1)+Fib(n-2);}8遞歸的定義數(shù)據(jù)結(jié)構(gòu)是遞歸的某些數(shù)據(jù)結(jié)構(gòu)就是遞歸的。例如，鏈表就是一種遞歸的數(shù)據(jù)結(jié)構(gòu)。鏈表結(jié)點(diǎn)LNode的定義由數(shù)據(jù)域data和指針域next組成；而指針域next則又由LNode定義^………h(huán)ead

head指向單鏈表，而每個(gè)結(jié)點(diǎn)LNode的指針域next指向一個(gè)更小的單鏈表。對單鏈表的遍歷操作則可以采用遞歸算法voidTraverse(LNode*p){

if(p){

cout<<pdata;

Traverse(pnext);

}}9遞歸的定義不僅單鏈表，廣義表、樹、圖也都是遞歸結(jié)構(gòu)。所以關(guān)于它們的一些算法，也需要用遞歸思想實(shí)現(xiàn)問題的解法是遞歸的有些問題只能用遞歸方法來解決，若不用遞歸就只能用枚舉法了一個(gè)典型的例子就是“TowerofHanoi”問題：婆羅門神廟里有一個(gè)塔臺(tái)，臺(tái)上有3根柱子(假設(shè)叫x,y,z)。在x柱上有64個(gè)金盤，每一個(gè)都比下面的小。把x柱上的金盤全部移到z柱上，移動(dòng)的條件是：一次只能移動(dòng)一個(gè)金盤，移動(dòng)過程中大盤子只能放在小盤子下面10遞歸的定義我們用遞歸解法設(shè)x柱上最初有n個(gè)盤子，如果n=1，則將這一個(gè)盤子直接從x柱移到z柱上；否則，執(zhí)行以下三步(1)用z做過渡，將x的n-1個(gè)小盤子移到y(tǒng)上(2)將x上最后的一個(gè)大盤子移到z上(3)用x做過渡，將y上的n-1個(gè)盤子移到z柱上，很顯然這就能重復(fù)上述過程，只是盤子個(gè)數(shù)減為n-1了11遞歸的定義它的遞歸算法如下voidHanoi(intn,charx,chary,charz){

if(n==1)

cout<<“move”<<x<<“to”<<z<<endl;

else{

Hanoi(n-1,x,z,y);

cout<<“move”<<x<<“to”<<z<<endl;

Hanoi(n-1,y,x,z);}}125.2遞歸算法

的工作原理函數(shù)的調(diào)用在函數(shù)調(diào)用中，一個(gè)函數(shù)的執(zhí)行沒有結(jié)束，又開始另一個(gè)函數(shù)的執(zhí)行，因此必須用棧來保存函數(shù)中的返回地址，以便調(diào)用返回時(shí)能從斷點(diǎn)繼續(xù)往下執(zhí)行例：設(shè)有一個(gè)主程序，它調(diào)用函數(shù)a，a又調(diào)用函數(shù)b，b又調(diào)用函數(shù)c，其中r，s，t分別表示返回地址main函數(shù)函數(shù)a函數(shù)b函數(shù)crst14函數(shù)的調(diào)用sr(b)調(diào)用函數(shù)b，s進(jìn)棧sr(d)返回到函數(shù)b,t退棧r(e)返回到函數(shù)a,s退棧(a)調(diào)用函數(shù)a，r進(jìn)棧r(f)返回到main，r退棧(c)調(diào)用函數(shù)c，t進(jìn)棧tsr15函數(shù)的調(diào)用操作系統(tǒng)通常為我們維護(hù)著一個(gè)運(yùn)行棧(runtimestack)每一個(gè)函數(shù)(包括main()函數(shù))通常包含返回地址、局部變量、形式參數(shù)、返回值包含所有這些信息的結(jié)構(gòu)位于運(yùn)行棧中，稱為這個(gè)函數(shù)的活動(dòng)記錄(activationrecords)。只要一個(gè)函數(shù)在運(yùn)行，屬于它的活動(dòng)記錄就存在于運(yùn)行棧中。棧頂?shù)幕顒?dòng)記錄表示正處在該函數(shù)中運(yùn)行16函數(shù)的調(diào)用返回值返回地址r…參數(shù)與局部變量返回值返回地址

s…參數(shù)與局部變量返回值返回地址

t…參數(shù)與局部變量main()的活動(dòng)記錄函數(shù)a的活動(dòng)記錄函數(shù)b的活動(dòng)記錄函數(shù)c的活動(dòng)記錄所以，圖放大后應(yīng)該是這樣(c)調(diào)用函數(shù)c，t進(jìn)棧tsr17剖析一個(gè)遞歸調(diào)用我們以power函數(shù)為例，剖析遞歸調(diào)用的過程在這個(gè)過程中，利用了操作系統(tǒng)維護(hù)的運(yùn)行棧(runtimestack)。我們以n=4為例 調(diào)用1power(x,4)

調(diào)用2power(x,3)

調(diào)用3power(x,2)

調(diào)用4 power(x,1)

調(diào)用5 power(x,0) 5返回 1 4返回 x 3返回 x·x 2返回 x·x·x 1返回x·x·x·x18剖析一個(gè)遞歸調(diào)用(0)(1)(x,4)(2)(x,4)(x,3)(3)(x,4)(x,3)(x,2)(4)(x,4)(x,3)(x,2)(x,1)(5)(x,4)(x,3)(x,2)(x,1)(x,0)(5)(x,3)(x,4)(x,2)(x,1)1(4)(x,3)(x,4)(x,2)x(3)(x,3)(x,4)x2(2)x3(x,4)(1)x4(0)power函數(shù)調(diào)用過程運(yùn)行棧的變化19分治法與遞歸思想現(xiàn)實(shí)中，我們經(jīng)常會(huì)遇到這樣的問題：為了解決它，我們可以把它分解為兩個(gè)或多個(gè)子問題，而解決每個(gè)子問題的解法與解決這個(gè)大問題的解法相同，即把每個(gè)子問題再進(jìn)一步分解為兩個(gè)或多個(gè)更小的子問題來加以解決，從而降低了問題的規(guī)模。只要解決了這些子問題，則原問題就迎刃而解了我們把這種解決問題的“先分解再求解”的策略稱為“分而治之”(divideandconquer)的策略，簡稱“分治法”一個(gè)問題如能用“分治法”解決，就可以用遞歸算法實(shí)現(xiàn)“分治法”和遞歸思想是一致的前面看到的階乘函數(shù)、冪函數(shù)、單鏈表的遍歷、漢諾塔等問題的求解過程都蘊(yùn)含著分而治之或先分解再求解的思想，因此都能用遞歸方法解決。而在其他學(xué)科中，如“運(yùn)籌學(xué)”和“現(xiàn)代控制論”中的“動(dòng)態(tài)規(guī)劃”也是采用了分治的思想205.3遞歸算法

的實(shí)現(xiàn)形式遞歸的結(jié)構(gòu)由于遞歸本身具有一定的特點(diǎn)，它是自己調(diào)用自己的過程，只不過每次調(diào)用時(shí)，問題的規(guī)模更小而已。因此在構(gòu)造遞歸函數(shù)時(shí)，切忌按堆棧方式思考問題，這樣很容易“鉆牛角尖”而不能自拔遞歸函數(shù)有其自身的獨(dú)特結(jié)構(gòu)任何一個(gè)遞歸函數(shù)都由兩部分組成初始情況：又叫結(jié)束條件或終止條件，即可以直接解決而無需再做遞歸的簡單輸入遞歸部分：包含對本算法的遞歸調(diào)用，但每次調(diào)用時(shí)傳遞進(jìn)去的參數(shù)較上次調(diào)用時(shí)傳遞進(jìn)去的參數(shù)更接近于初始情況如果我們本著這兩個(gè)原則去寫函數(shù)，則一定是遞歸函數(shù)22遞歸的結(jié)構(gòu)這樣，遞歸函數(shù)的基本結(jié)構(gòu)就非常清晰了，它是一個(gè)if-else結(jié)構(gòu)注意：不是while或for循環(huán)結(jié)構(gòu)if(…)初始情況或

if(…)else遞歸部分遞歸部分例如前面講過的階乘函數(shù)Factorial()、冪函數(shù)power()，費(fèi)氏函數(shù)Fib()、鏈表遍歷函數(shù)Traver-se()、漢諾塔Hanoi()都具有這種結(jié)構(gòu)。以后我們還會(huì)遇到許多遞歸函數(shù)也都具有這種結(jié)構(gòu)235.4遞歸算法的分類尾遞歸尾遞歸的特點(diǎn)是僅在一個(gè)函數(shù)實(shí)現(xiàn)的最后進(jìn)行一次遞歸調(diào)用。換句話說，當(dāng)某一層遞歸調(diào)用返回后，由于后面沒有任何語句，所以繼續(xù)向上一層返回。這種遞歸函數(shù)的特點(diǎn)是在調(diào)用返回之前完成本次調(diào)用的一切處理或計(jì)算任務(wù)，然后再返回。因此，這種遞歸通常體現(xiàn)為從我們給定的初始參數(shù)開始，到結(jié)束條件為止，依次進(jìn)行處理或計(jì)算。25非尾遞歸非尾遞歸的特點(diǎn)是遞歸調(diào)用語句并非是函數(shù)的最后一條語句。當(dāng)調(diào)用進(jìn)入到某一層時(shí)，