數(shù)據(jù)結(jié)構(gòu) 遞歸

數(shù)據(jù)結(jié)構(gòu)遞歸第1頁，課件共41頁，創(chuàng)作于2023年2月6.1什么是遞歸6.1.1遞歸的定義

在定義一個過程或函數(shù)時出現(xiàn)調(diào)用本過程或本函數(shù)的成分,稱之為遞歸。若調(diào)用自身,稱之為直接遞歸。若過程或函數(shù)p調(diào)用過程或函數(shù)q,而q又調(diào)用p,稱之為間接遞歸。如果一個遞歸過程或遞歸函數(shù)中遞歸調(diào)用語句是最后一條執(zhí)行語句,則稱這種遞歸調(diào)用為尾遞歸。第2頁，課件共41頁，創(chuàng)作于2023年2月例6.1以下是求n!(n為正整數(shù))的遞歸函數(shù)。intfun(intn){if(n==1) /*語句1*/return1; /*語句2*/else /*語句3*/returnfun(n-1)*n; /*語句4*/}在該函數(shù)fun(n)求解過程中,直接調(diào)用fun(n-1)(語句4)自身,所以它是一個直接遞歸函數(shù)。又由于遞歸調(diào)用是最后一條語句,所以它又屬于尾遞歸。第3頁，課件共41頁，創(chuàng)作于2023年2月6.1.2何時使用遞歸在以下三種情況下,常常要用到遞歸的方法。1.定義是遞歸的有許多數(shù)學(xué)公式、數(shù)列等的定義是遞歸的。例如,求n!和Fibonacci數(shù)列等。這些問題的求解過程可以將其遞歸定義直接轉(zhuǎn)化為對應(yīng)的遞歸算法。第4頁，課件共41頁，創(chuàng)作于2023年2月2.數(shù)據(jù)結(jié)構(gòu)是遞歸的有些數(shù)據(jù)結(jié)構(gòu)是遞歸的。例如,第2章中介紹過的單鏈表就是一種遞歸數(shù)據(jù)結(jié)構(gòu),其結(jié)點類型定義如下：typedefstructLNode{ElemTypedata;structLNode*next; }LinkList;該定義中,結(jié)構(gòu)體LNode的定義中用到了它自身,即指針域next是一種指向自身類型的指針,所以它是一種遞歸數(shù)據(jù)結(jié)構(gòu)。第5頁，課件共41頁，創(chuàng)作于2023年2月對于遞歸數(shù)據(jù)結(jié)構(gòu),采用遞歸的方法編寫算法既方便又有效。例如,求一個不帶頭結(jié)點的單鏈表head的所有data域(假設(shè)為int型)之和的遞歸算法如下：intSum(LinkList*head){if(head==NULL)return0;elsereturn(head->data+Sum(head->next));}第6頁，課件共41頁，創(chuàng)作于2023年2月3.問題的求解方法是遞歸的有些問題的解法是遞歸的,典型的有Hanoi問題求解,該問題描述是：設(shè)有3個分別命名為X,Y和Z的塔座,在塔座X上有n個直徑各不相同,從小到大依次編號為1,2,…,n的盤片,現(xiàn)要求將X塔座上的n個盤片移到塔座Z上并仍按同樣順序疊放,盤片移動時必須遵守以下規(guī)則：每次只能移動一個盤片；盤片可以插在X,Y和Z中任一塔座；任何時候都不能將一個較大的盤片放在較小的盤片上。設(shè)計遞歸求解算法,并將其轉(zhuǎn)換為非遞歸算法。設(shè)Hanoi(n,x,y,z)表示將n個盤片從x通過y移動到z上,遞歸分解的過程是：第7頁，課件共41頁，創(chuàng)作于2023年2月Hanoi(n,x,y,z)Hanoi(n-1,x,z,y)；move(n,x,z):將第n個圓盤從x移到z；Hanoi(n-1,y,x,z)第8頁，課件共41頁，創(chuàng)作于2023年2月6.1.3遞歸模型遞歸模型是遞歸算法的抽象,它反映一個遞歸問題的遞歸結(jié)構(gòu),例如,前面的遞歸算法對應(yīng)的遞歸模型如下：fun(1)=1(1)fun(n)=n*fun(n-1)n>1(2)其中,第一個式子給出了遞歸的終止條件,第二個式子給出了fun(n)的值與fun(n-1)的值之間的關(guān)系,我們把第一個式子稱為遞歸出口,把第二個式子稱為遞歸體。第9頁，課件共41頁，創(chuàng)作于2023年2月一般地,一個遞歸模型是由遞歸出口和遞歸體兩部分組成,前者確定遞歸到何時結(jié)束,后者確定遞歸求解時的遞推關(guān)系。遞歸出口的一般格式如下：f(s1)=m1 (6.1)這里的s1與m1均為常量,有些遞歸問題可能有幾個遞歸出口。遞歸體的一般格式如下：f(sn+1)=g(f(si),f(si+1),…,f(sn),cj,cj+1,…,cm) (6.2)其中,n,i,j,m均為正整數(shù)。這里的sn+1是一個遞歸“大問題”,si,si+1,…,sn為遞歸“小問題”,cj,cj+1,…,cm是若干個可以直接(用非遞歸方法)解決的問題,g是一個非遞歸函數(shù),可以直接求值。第10頁，課件共41頁，創(chuàng)作于2023年2月實際上,遞歸思路是把一個不能或不好直接求解的“大問題”轉(zhuǎn)化成一個或幾個“小問題”來解決,再把這些“小問題”進一步分解成更小的“小問題”來解決,如此分解,直至每個“小問題”都可以直接解決(此時分解到遞歸出口)。但遞歸分解不是隨意的分解,遞歸分解要保證“大問題”與“小問題”相似,即求解過程與環(huán)境都相似。第11頁，課件共41頁，創(chuàng)作于2023年2月為了討論方便,簡化上述遞歸模型為：f(s1)=m1 (6.3)f(sn)=g(f(sn-1),c) (6.4)求f(sn)的分解過程如下：f(sn)↓f(sn-1)↓…↓f(s2)↓f(s1)第12頁，課件共41頁，創(chuàng)作于2023年2月

一旦遇到遞歸出口,分解過程結(jié)束,開始求值過程,所以分解過程是“量變”過程,即原來的“大問題”在慢慢變小,但尚未解決,遇到遞歸出口后,便發(fā)生了“質(zhì)變”,即原遞歸問題便轉(zhuǎn)化成直接問題。上面的求值過程如下：f(s1)=m1↓f(s2)=g(f(s1),c1)↓f(s3)=g(f(s2),c2)↓…↓f(sn)=g(f(sn-1),cn-1)第13頁，課件共41頁，創(chuàng)作于2023年2月這樣f(sn)便計算出來了,因此,遞歸的執(zhí)行過程由分解和求值兩部分構(gòu)成。第14頁，課件共41頁，創(chuàng)作于2023年2月求解fun(5)的過程如下：第15頁，課件共41頁，創(chuàng)作于2023年2月6.2遞歸算法的設(shè)計遞歸的求解的過程均有這樣的特征：先將整個問題劃分為若干個子問題,通過分別求解子問題,最后獲得整個問題的解。而這些子問題具有與原問題相同的求解方法,于是可以再將它們劃分成若干個子問題,分別求解,如此反復(fù)進行,直到不能再劃分成子問題,或已經(jīng)可以求解為止。這種自上而下將問題分解、求解,再自上而下引用、合并,求出最后解答的過程稱為遞歸求解過程。這是一種分而治之的算法設(shè)計方法。遞歸算法設(shè)計先要給出遞歸模型,再轉(zhuǎn)換成對應(yīng)的C/C++語言函數(shù)。第16頁，課件共41頁，創(chuàng)作于2023年2月遞歸設(shè)計的步驟如下：(1)對原問題f(s)進行分析,假設(shè)出合理的“較小問題”f(s')(與數(shù)學(xué)歸納法中假設(shè)n=k-1時等式成立相似)；(2)假設(shè)f(s')是可解的,在此基礎(chǔ)上確定f(s)的解,即給出f(s)與f(s')之間的關(guān)系(與數(shù)學(xué)歸納法中求證n=k時等式成立的過程相似)；(3)確定一個特定情況(如f(1)或f(0))的解,由此作為遞歸出口(與數(shù)學(xué)歸納法中求證n=1時等式成立相似)。第17頁，課件共41頁，創(chuàng)作于2023年2月

例如,采用遞歸算法求實數(shù)數(shù)組A[0..n-1]中的最小值。

假設(shè)f(A,i)函數(shù)求數(shù)組元素A[0]～A[i]中的最小值。當(dāng)i=0時,有f(A,i)=A[0]；假設(shè)f(A,i-1)已求出,則f(A,i)=MIN(f(A,i-1),A[i]),其中MIN()為求兩個值較小值函數(shù)。因此得到如下遞歸模型：A[0] 當(dāng)i=0時f(A,i)=MIN(f(A,i-1),A[i]) 其他情況第18頁，課件共41頁，創(chuàng)作于2023年2月由此得到如下遞歸求解算法：floatf(floatA[],inti){floatm;if(i==0)returnA[0];else{m=f(A,i-1); if(m>A[i])returnA[i]; elsereturnm; }}第19頁，課件共41頁，創(chuàng)作于2023年2月例求1，2，…，n的全排列。解：用數(shù)組a存放n個不同字符的字符串，設(shè)f(a,k,n)為a[0..k]的所有字符的全排序。則f(a,k-1,n)為a[0..k-1]的所有字符的全排序。假設(shè)f(a,k-1,n)可求，對于a[k]位置，可以取a[0..k]任何之值，再組合f(a,k-1,n)，則得到f(a,k,n)遞歸模型為：

f(a,k,n)：輸出a 當(dāng)k=0時f(a,k,n)：a[k]位置取a[0..k]任何之值,其他情況并組合f(a,k-1,n)的結(jié)果;第20頁，課件共41頁，創(chuàng)作于2023年2月voidf(charstr[],intk,intn){ inti,j; chartmp; if(k==0) {for(j=0;j<n;j++) printf("%c",a[j]); printf("\n"); } else {for(i=0;i<=k;i++) { a[k]<->a[j]; f(a,k-1,n); a[k]<->a[i] } }}第21頁，課件共41頁，創(chuàng)作于2023年2月例采用遞歸算法求解皇后問題：在n×n的方格棋盤上，放置n個皇后，要求每個皇后不同行、不同列、不同左右對角線。解：設(shè)place(k,n)表示在前面1，…，k-1個皇后放置好后，用于放置k，…，n的皇后。求解皇后問題的遞歸模型如下：place(i,n)：n個皇后放置完畢，輸出解 若i=nplace(k,n)：對于第k列的每個合適的位置i,在其上放置一個皇后;place(k+1,n);其他情況第22頁，課件共41頁，創(chuàng)作于2023年2月6.3遞歸算法到非遞歸算法的轉(zhuǎn)換遞歸算法有兩個基本特性：一是遞歸算法是一種分而治之的、把復(fù)雜問題分解為簡單問題的求解問題方法,對求解某些復(fù)雜問題,遞歸算法分析問題的方法是十分有效的；二是遞歸算法的時間效率通常比較差。因此,對求解某些問題時,我們希望用遞歸算法分析問題,用非遞歸算法具體求解問題。這就需要把遞歸算法轉(zhuǎn)換為非遞歸算法。第23頁，課件共41頁，創(chuàng)作于2023年2月把遞歸算法轉(zhuǎn)化為非遞歸算法有如下三種基本方法：(1)對于尾遞歸和單向遞歸的算法,可用循環(huán)結(jié)構(gòu)的算法替代。(2)自己用棧模擬系統(tǒng)的運行時棧,通過分析只保存必須保存的信息,從而用非遞歸算法替代遞歸算法。(3)利用棧保存參數(shù),由于棧的后進先出特性吻合遞歸算法的執(zhí)行過程,因而可以用非遞歸算法替代遞歸算法。本節(jié)討論第(1)種和第(2)種情況的遞歸算法轉(zhuǎn)化為非遞歸算法的問題,前者是一種是直接轉(zhuǎn)化法,不需要使用棧,后者是間接轉(zhuǎn)化法,需要使用棧。第(3)種情況也需要使用棧,但因具體情況而異,例如,在第7章的例7.6就是這種情況的一個例子。第24頁，課件共41頁，創(chuàng)作于2023年2月6.3.1尾遞歸和單向遞歸的消除

采用循環(huán)結(jié)構(gòu)消除尾遞歸和單向遞歸。求解Fibonacci數(shù)列的算法如下：intFib(intn){inti,f1,f2,f3;if(n==1||n==2)return(n);f1=1;f2=2;for(i=3;i<=n;i++){f3=f1+f2;f1=f2;f2=f3;}return(f3);}第25頁，課件共41頁，創(chuàng)作于2023年2月

采用循環(huán)結(jié)構(gòu)消除遞歸沒有通用的轉(zhuǎn)換算法,對于具體問題要深入分析對應(yīng)的遞歸結(jié)構(gòu),設(shè)計有效的循環(huán)語句進行遞歸到非遞歸的轉(zhuǎn)換。第26頁，課件共41頁，創(chuàng)作于2023年2月6.3.2模擬系統(tǒng)的運行時棧消除遞歸對于不屬于尾遞歸和單向遞歸的遞歸算法,很難轉(zhuǎn)化為與之等價的循環(huán)算法。但所有的遞歸程序都可以轉(zhuǎn)化為與之等價的非遞歸程序(例如,C/C++語言就是先將遞歸程序轉(zhuǎn)化為非遞歸程序,然后求解的)。有一個通用的算法可以將遞歸程序轉(zhuǎn)化為非遞歸程序(詳見參考文獻[2]8.4節(jié)),由于這個算法過于通用,比較復(fù)雜,不易理解,而且通常需要使用goto轉(zhuǎn)移語句,違反結(jié)構(gòu)化程序設(shè)計規(guī)定,因此,在這里不作介紹。下面討論直接使用棧保存中間結(jié)果,從而將遞歸算法轉(zhuǎn)化為非遞歸算法的過程。第27頁，課件共41頁，創(chuàng)作于2023年2月1．等值關(guān)系等值關(guān)系是指“大問題”的函數(shù)值等于“小問題”的函數(shù)值的某種運算結(jié)果，例如求n！對應(yīng)的遞歸模型就是等值關(guān)系。仍以例6.1討論等值關(guān)系遞歸模型的轉(zhuǎn)換方法。分析：該遞歸模型有一個遞歸出口和一個遞歸體兩個式子，分別稱為（1）式和（2）式。（2）式中有一次分解過程：f(n)f(n-1)對應(yīng)的求值過程是：f(n-1)f(n)=n*f(n-1)。第28頁，課件共41頁，創(chuàng)作于2023年2月設(shè)計一個棧，其結(jié)構(gòu)如下：

struct{ intn; /*保存n值*/ intf; /*保存fun2(n)值*/ inttag;/*標識是否求出fun2(n)值,1:未求出,0:已求出*/}St[MaxSize]; /*定義棧*/inttop=-1; /*棧指針初始化*/第29頁，課件共41頁，創(chuàng)作于2023年2月計算fun2(5)之值的過程如下：將(5,*,1)進棧; /*其中*表示沒有設(shè)定值*/while(棧不空){ if(棧頂元素未計算出f值即St[top].tag==1) {if(棧頂元素滿足(1)式) 求出對應(yīng)的St[top].f值,并置St[top].tag=0表示已求出對應(yīng)的函數(shù)值; else/*棧頂元素滿足(2)式*/ 將(St[top].n-1,*,1)進棧; /*分解過程*/}elseif(棧頂元素已計算出的f值即St[top].tag==0) 由棧頂元素的f值計算出次棧頂元素的f值并退棧;/*求值過程:顯然棧頂元素由次棧頂元素通過(2)式分解得到的,回過來*/if(棧中只有一個已求出f值的元素)退出循環(huán);}St[0].f即為所求的fun2(n)值;第30頁，課件共41頁，創(chuàng)作于2023年2月intfun2(intn){top++;

St[top].n=n;St[top].tag=1;/*初值進棧*/while(top>-1)/*棧不空時循環(huán)*/{ if(St[top].tag==1) /*未計算出棧頂元素的f值*/ {if(St[top].n==1) /*(1)式*/ {St[top].f=1; St[top].tag=0; } else /*(2)式分解過程*/ {top++;St[top].n=St[top-1].n-1; St[top].tag=1; } } elseif(St[top].tag==0) /*已計算出f值*/ {St[top-1].f=St[top-1].n*St[top].f;/*(2)式求值過程*/ St[top-1].tag=0;top--; }第31頁，課件共41頁，創(chuàng)作于2023年2月 if(top==0&&St[top].tag==0)/*棧中只有一個已求出f的元素時退出循環(huán)*/ break;}return(St[top].f);}第32頁，課件共41頁，創(chuàng)作于2023年2月Ackerman函數(shù)的定義如下：akm(m,n)=n+1 m=0akm(m-1,1) m≠0,n=0akm(m-1,akm(m,n-1) m≠0,n≠0設(shè)計對應(yīng)的非遞歸算法。第33頁，課件共41頁，創(chuàng)作于2023年2月計算akm(2,1)的遞歸調(diào)用過程樹第34頁，課件共41頁，創(chuàng)作于2023年2月2．等價關(guān)系等價關(guān)系是指“大問題”的求解過程轉(zhuǎn)化為“小問題”求解而得到的，它們之間不是值的相等關(guān)系，而是解的等價關(guān)系。例如，求梵塔問題對應(yīng)的遞歸模型就是等價關(guān)系，也就是說，Hanoi(n,x,y,z)與Hanoi(n-1,x,z,y)、move(n,x,z)和Hanoi(n-1,y,x,z)是等價的。該問題完整的遞歸模型如下：

Hanoi(n,x,y,z)直接將x上的盤片從x移動到z上當(dāng)n=1時 （1）Hanoi(n,x,y,z)Hanoi(n-1,x,z,y)； 將第n個圓盤從x移動到z上；Hanoi(n-1,y,x,z) 當(dāng)n>1時 （2）第35頁，課件共41頁，創(chuàng)作于2023年2月對應(yīng)的非遞歸求解過程如下：

定義一個棧;將初始問題進棧;while(棧不空){if(棧頂元素的tag==1)/*不能直接操作*/{將棧中元素出棧; 將Hanoi(n-1,y,x,z)進棧; 將“將第n個圓盤從x移動到z上”操作進棧; 將Hanoi(n-1,x,z,y)進棧;}if(棧頂元素滿足遞歸出口條件)直接操作并置tag=0;}注意：上述過程中進棧的次序與(2)中三步的求解次序正好相反，這是由于Hanoi問題和棧的特點決定的。

第36頁，課件共41頁，創(chuàng)作于2023年2月非遞歸算法Hanoi()如下：voidHanoi1(intn,charx,chary,charz){intn1,x1,y1,z1;if(n<=0){ printf("參數(shù)錯誤\n"); return;}elseif(n==1){printf("將%c上的1個盤片直接移動到%c\n",x,z); return;}top++;St[top].n=n;/*初值進棧*/St[top].x=x;St[top].y=y;St[top].z=z;St[top].tag=1;第37頁，課件共41頁，創(chuàng)作于2023年2月

while(top>-1) /*棧不空循環(huán)*/{ if(St[top].tag==1&&St[top].n>1)/*不能直接操作*/