同濟(jì)大學(xué)計(jì)算機(jī)編程課件：Cds05.ppt

遞歸的概念 遞歸過程與遞歸工作棧 遞歸與回溯 廣義表,第五章 遞歸與廣義表,遞歸的概念,遞歸的定義 若一個(gè)對象部分地包含它自己, 或用它自己給自己定義, 則稱這個(gè)對象是遞歸的；若一個(gè)過程直接地或間接地調(diào)用自己, 則稱這個(gè)過程是遞歸的過程。 以下三種情況常常用到遞歸方法。 定義是遞歸的 數(shù)據(jù)結(jié)構(gòu)是遞歸的 問題的解法是遞歸的,定義是遞歸的,求解階乘函數(shù)的遞歸算法 long Factorial ( long n ) if ( n = 0 ) return 1; else return n * Factorial (n-1); ,例如，階乘函數(shù),求解階乘 n! 的過程,主程序 main : fact(4),參數(shù) 4 計(jì)算 4*fact(3) 返回 24,參數(shù) 3 計(jì)算 3*fact(2) 返回 6,參數(shù) 2 計(jì)算 2*fact(1) 返回 2,參數(shù) 1 計(jì)算 1*fact(0) 返回 1,參數(shù) 0 直接定值 = 1 返回 1,參數(shù)傳遞,結(jié)果返回,遞歸調(diào)用,回歸求值,數(shù)據(jù)結(jié)構(gòu)是遞歸的,一個(gè)結(jié)點(diǎn)，它的指針域?yàn)镹ULL，是一個(gè)單鏈表; 一個(gè)結(jié)點(diǎn)，它的指針域指向單鏈表，仍是一個(gè)單鏈表。,例如，單鏈表結(jié)構(gòu),f,f,搜索鏈表最后一個(gè)結(jié)點(diǎn)并打印其數(shù)值 template void Print ( ListNode *f ) if ( f -link = NULL ) cout data link ); ,f,f,f,f,f,a0,a1,a2,a3,a4,遞歸找鏈尾,在鏈表中尋找等于給定值的結(jié)點(diǎn)并打印其數(shù)值 template void Print ( ListNode *f, Type ,f,f,f,f,遞歸找含x值的結(jié)點(diǎn),x,問題的解法是遞歸的 例如，漢諾塔(Tower of Hanoi)問題的解法： 如果 n = 1，則將這一個(gè)盤子直接從 A 柱移到 C 柱上。否則，執(zhí)行以下三步： 用 C 柱做過渡，將 A 柱上的 (n-1) 個(gè)盤子移到 B 柱上： 將 A 柱上最后一個(gè)盤子直接移到 C 柱上； 用 A 柱做過渡，將 B 柱上的 (n-1) 個(gè)盤子移到 C 柱上。,#include #include “strclass.h” void Hanoi (int n, String A, String B, String C) /解決漢諾塔問題的算法 if ( n = 1 ) cout “ move “ A “ to “ C endl; else Hanoi ( n-1, A, C, B ); cout “ move “ A “ to “ C endl; Hanoi ( n-1, B, A, C ); ,(3,A,B,C),(2,A,C,B),A-C,A,B,C,(1,A,C,B),A,B,C,A-C,A-C,(1,B,A,C),A,B,C,A-C,A-B,A-B A-C,B-C C-B,A-C,(2,B,A,C),A,B,C,(1,A,C,B),A,B,C,A-C,A-C,(1,B,A,C),A,B,C,A-C,B-C,A-B B-A,B-C A-C,自頂向下、逐步分解的策略,子問題應(yīng)與原問題做同樣的事情，且更為簡單； 解決遞歸問題的策略是把一個(gè)規(guī)模比較大的問題分解為一個(gè)或若干規(guī)模比較小的問題，分別對這些比較小的問題求解，再綜合它們的結(jié)果，從而得到原問題的解。 分而治之策略（分治法） 這些比較小的問題的求解方法與原來問題的求解方法一樣。,構(gòu)成遞歸的條件,不能無限制地調(diào)用本身，必須有一個(gè)出口，化簡為非遞歸狀況直接處理。 Procedure ( ) if ( ) return ( initial value ); else return ( ( parameter exchange ); ,遞歸過程與遞歸工作棧,遞歸過程在實(shí)現(xiàn)時(shí)，需要自己調(diào)用自己。 層層向下遞歸，退出時(shí)的次序正好相反： 遞歸調(diào)用 n! (n-1)! (n-2)! 1! 0!=1 返回次序 主程序第一次調(diào)用遞歸過程為外部調(diào)用； 遞歸過程每次遞歸調(diào)用自己為內(nèi)部調(diào)用。 它們返回調(diào)用它的過程的地址不同。,遞歸工作棧,每一次遞歸調(diào)用時(shí)，需要為過程中使用的參數(shù)、局部變量等另外分配存儲空間。 每層遞歸調(diào)用需分配的空間形成遞歸工作記錄，按后進(jìn)先出的棧組織。,局部變量 返回地址 參 數(shù),活動(dòng)記錄框架,遞歸 工作記錄,函數(shù)遞歸時(shí)的活動(dòng)記錄,. ,Function() . ,調(diào)用塊,函數(shù)塊,返回地址(下一條指令) 局部變量 參數(shù),long Factorial ( long n ) int temp; if ( n = 0 ) return 1; else temp = n * Factorial (n-1); RetLoc2 return temp; ,void main ( ) int n; n = Factorial (4); RetLoc1 ,計(jì)算Fact時(shí)活動(dòng)記錄的內(nèi)容,遞歸調(diào)用序列,0 1 RetLoc2,1 1 RetLoc2,2 2 RetLoc2,3 6 RetLoc2,4 24 RetLoc1,參數(shù) 返回值 返回地址 返回時(shí)的指令,return 4*6 /返回 24,return 3*2 /返回 6,return 1 /返回 1,return 1*1 /返回 1,return 2*1 /返回 2,遞歸過程改為非遞歸過程,遞歸過程簡潔、易編、易懂 遞歸過程效率低，重復(fù)計(jì)算多 改為非遞歸過程的目的是提高效率 單向遞歸和尾遞歸可直接用迭代實(shí)現(xiàn)其非遞歸過程 其他情形必須借助棧實(shí)現(xiàn)非遞歸過程,計(jì)算斐波那契數(shù)列的函數(shù)Fib(n)的定義,求解斐波那契數(shù)列的遞歸算法 long Fib ( long n ) if ( n = 1 ) return n; else return Fib (n-1) + Fib (n-2); ,如 F0 = 0, F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5,調(diào)用次數(shù) NumCall(k) = 2*Fib(k+1) - 1。,斐波那契數(shù)列的遞歸調(diào)用樹,Fib(1),Fib(0),Fib(1),Fib(2),Fib(3),Fib(4),Fib(1),Fib(0),Fib(2),Fib(1),Fib(0),Fib(1),Fib(2),Fib(3),Fib(5),Fib(1),Fib(0),Fib(2),Fib(1),Fib(0),Fib(2),Fib(1),Fib(3),Fib(4),棧結(jié)點(diǎn),n tag,tag = 1, 向左遞歸；tag = 2, 向右遞歸,Fib(1),Fib(0),Fib(2),Fib(1),Fib(0),Fib(2),Fib(1),Fib(3),Fib(4),2 1 3 1 4 1,n=1 sum=0+1,2 2 3 1 4 1,n=2-2,3 1 4 1,n=0 sum=1+0,3 2 4 1,n=3-2,4 1,n=1 sum=1+1,4 2,n=4-2,Fib(1),Fib(0),Fib(2),Fib(1),Fib(0),Fib(2),Fib(1),Fib(3),Fib(4),2 1 4 2,n=1 sum=2+1,2 2 4 2,n=2-2,4 2,n=0 sum=3+0,long Fibnacci ( long n ) Stack S; Node w; long sum = 0; /反復(fù)執(zhí)行直到所有終端結(jié)點(diǎn)數(shù)據(jù)累加完 do while ( n 1 ) w.n = n; w.tag = 1; S.push ( w ); n-; /向左遞歸到底, 邊走邊進(jìn)棧 sum = sum + n; /執(zhí)行求和,while ( !S.IsEmpty( ) ) w = S.getTop( ); S.Pop( ); if ( w.tag = 1 ) /改為向右遞歸 w.tag = 2; S.push ( w ); n = w.n 2; /F(n)右側(cè)為F(n-2) break; while ( !S.IsEmpty( ) ); return sum; ,單向遞歸用迭代法實(shí)現(xiàn),long FibIter ( long n ) if ( n = 1 ) return n; long twoback = 0, oneback = 1, Current; for ( int i = 2; i = n; i+ ) Current = twoback + oneback; twoback = oneback; oneback = Current; return Current; ,void recfunc ( int A , int n ) if ( n = 0 ) cout An “ ”; n-; recfunc ( A, n ); ,25 36 72 18 99 49 54 63,尾遞歸用迭代法實(shí)現(xiàn),void sterfunc ( int A , int n ) /消除了尾遞歸的非遞歸函數(shù) while ( n = 0 ) cout “value “ An endl; n-; ,遞歸與回溯 常用于搜索過程,對一個(gè)包含有許多結(jié)點(diǎn)，且每個(gè)結(jié)點(diǎn)有多個(gè)分支的問題，可以先選擇一個(gè)分支進(jìn)行搜索。當(dāng)搜索到某一結(jié)點(diǎn)，發(fā)現(xiàn)無法再繼續(xù)搜索下去時(shí)，可以沿搜索路徑回退到前一結(jié)點(diǎn)，沿另一分支繼續(xù)搜索。 如果回退之后沒有其他選擇，再沿搜索路徑回退到更前結(jié)點(diǎn)，。依次執(zhí)行，直到搜索到問題的解，或搜索完全部可搜索的分支沒有解存在為止。 回溯法與分治法本質(zhì)相同，可用遞歸算法求解。,n皇后問題 在 n 行 n 列的國際象棋棋盤上，若兩個(gè)皇后位于同一行、同一列、同一對角線上，則稱為它們?yōu)榛ハ喙?。n皇后問題是指找到這 n 個(gè)皇后的互不攻擊的布局。,1#主對角線 3#主對角線 5#主對角線,0#次對角線 2#次對角線 4#次對角線 6#次對角線,1#次對角線 3#次對角線 5#次對角線,0#主對角線 2#主對角線 4#主對角線 6#主對角線,0 1 2 3,0 1 2 3,k = i+j,k = n+i-j-1,解題思路,安放第 i 行皇后時(shí)，需要在列的方向從 0 到 n-1 試探 ( j = 0, , n-1 ) 在第 j 列安放一個(gè)皇后： 如果在列、主對角線、次對角線方向有其它皇后，則出現(xiàn)攻擊，撤消在第 j 列安放的皇后。 如果沒有出現(xiàn)攻擊，在第 j 列安放的皇后不動(dòng)，遞歸安放第 i+1行皇后。,設(shè)置 4 個(gè)數(shù)組 col n ：coli 標(biāo)識第 i 列是否安放了皇后 md2n-1 : mdk 標(biāo)識第 k 條主對角線是否安放了皇后 sd2n-1 : sdk 標(biāo)識第 k 條次對角線是否安放了皇后 qn : qi 記錄第 i 行皇后在第幾列,void Queen( int i ) for ( int j = 0; j n; j+ ) if ( 第 i 行第 j 列沒有攻擊 ) 在第 i 行第 j 列安放皇后； if ( i = n-1 ) 輸出一個(gè)布局； else Queen ( i+1 ); 撤消第 i 行第 j 列的皇后； ,算法求精 void Queen( int i ) for ( int j = 0; j n; j+ ) if ( !colj /*在第 i 行第 j 列安放皇后*/,if ( i = n-1 ) /*輸出一個(gè)布局*/ for ( k = 0; k n; k+ ) cout qk ,; cout endl; else Queen ( i+1 ); colj = mdn+i-j-1 = sdi+j = 0; qi = 0; /*撤消第 i 行第 j 列的皇后*/ ,迷宮問題,小型迷宮,路口 動(dòng)作 結(jié)果 1 (入口) 正向走 進(jìn)到 2 2 左拐彎 進(jìn)到 3 3 右拐彎 進(jìn)到 4 4 (堵死) 回溯 退到 3 3 (堵死) 回溯 退到 2 2 正向走 進(jìn)到 5 5 (堵死) 回溯 退到 2 2 右拐彎 進(jìn)到 6 6 左拐彎 進(jìn)到 7 (出口),4 3,5 2 1,7 6,6 左 0 直 2 右 0 行 3 行 5 行 6 0 0 4 0 0 0 0 0 0 7 0 0 7,小型迷宮的數(shù)據(jù),迷宮的類定義 #include #include #include class Maze private: int MazeSize; int EXIT; Intersection *intsec; public: Maze ( char *filename ); int TraverseMaze ( int CurrentPos ); ,交通路口結(jié)構(gòu)定義 struct Intersection int left; int forward; int right; ,Maze : Maze ( char *filename ) /構(gòu)造函數(shù)：從文件 filename 中讀取各路口 /和出口的數(shù)據(jù) ifstream fin; fin.open ( filename, ios:in | ios:nocreate ); /為輸入打開文件,文件不存在則打開失敗 if ( !fin ) cerr MazeSize; /輸入迷宮路口數(shù),intsec = new IntersectionMazeSize+1; /創(chuàng)建迷宮路口數(shù)組 for ( int i = 1; i intseci.left intseci.forward intseci.right; fin EXIT; /輸入迷宮出口 fin.close ( ); 迷宮漫游與求解算法 int Maze:TraverseMaze ( int CurrentPos ) if ( CurrentPos 0 ) /路口從 1 開始,if ( CurrentPos = EXIT ) /出口處理 cout CurrentPos “ “; return 1; else /遞歸向左搜尋可行 if (TraverseMaze(intsecCurrentPos.left ) cout CurrentPos “ ”; return 1; else /遞歸向前搜尋可行 if (TraverseMaze(intsecCurrentPos.forward) cout CurrentPos “ ”; return 1; else /遞歸向右搜尋可行 if (TraverseMaze(intsecCurrentPos.right) cout CurrentPos “ “; return 1; return 0; ,廣義表 (General Lists ),廣義表的概念 n ( 0 )個(gè)表元素組成的有 限序列，記作 LS (a0, a1, a2, , an-1) LS是表名，ai是表元素，它可以是表 (稱 為子表)，可以是數(shù)據(jù)元素(稱為原子)。 n為表的長度。n = 0 的廣義表為空表。 n 0時(shí)，表的第一個(gè)表元素稱為廣義表 的表頭(head)，除此之外，其它表元素組 成的表稱為廣義表的表尾(tail)。,廣義表的特性,有次序性 有長度,有深度 可共享,可遞歸,A( ) B( 6, 2 ) head(B) = 6, tail(B) =(2) C( a, ( 5, 3, x ) ) D( B, C, A ) head(C) =a E( B, D ) tail(C) = (5,3,x) F( 4, F ) head( (5,3,x) ) = (5,3,x) tail( (5,3,x) ) = ( ),廣義表的表示,只包括整數(shù)和字符型數(shù)據(jù)的廣義表鏈表表示,表中套表情形下的廣義表鏈表表示,5,2,3,2,4,3,6,10,3,9,14,list2,5,list1,12,47,a,s,廣義表結(jié)點(diǎn)定義,結(jié)點(diǎn)類型 utype = 0, 表頭；= 1, 整型原子；= 2, 字符型原子；= 3, 子表 值value utype=0時(shí), 存放引用計(jì)數(shù)(ref)；utype=1時(shí), 存放整數(shù)值(intinfo)；utype=2時(shí), 存放字符型數(shù)據(jù)(charinfo)；utype=3時(shí), 存放指向子表表頭的指針(hlink) 尾指針tlink utype=0時(shí), 指向該表第一個(gè)結(jié)點(diǎn)；utype0時(shí), 指向同一層下一個(gè)結(jié)點(diǎn),utype value tlink,廣義表的存儲表示,E,B,F,0 1,1 4,3,0 0,3,3,D,0 1,1 5,1 3,2 x,0 1,2 a,3,C,0 1,3,3,3,0 2,1 6,D,B,B,C,A,1 2,0 1,A,廣義表的類定義,class GenList; /GenList類的前視聲明 class GenListNode ; /廣義表結(jié)點(diǎn)類的前視聲明 struct Items /僅有結(jié)點(diǎn)信息的項(xiàng) friend class GenlistNode; friend class Genlist; int utype; /0 / 1 / 2 / 3 union /聯(lián)合,int ref; /utype=0, 存放引用計(jì)數(shù) int intinfo; /utype=1, 存放整數(shù)值 char charinfo; /utype =2, 存放字符 GenListNode *hlink; /utype =3, 存放指向子表的指針 value; class GenListNode /廣義表結(jié)點(diǎn)類定義 friend class Genlist; private: int utype; /0 / 1 / 2 / 3,GenListNode * tlink; /下一結(jié)點(diǎn)指針 union /聯(lián)合 int ref; /utype=0, 存放引用計(jì)數(shù) int intinfo; /utype=1, 存放整數(shù)值 char charinfo; /utype=2, 存放字符 GenListNode *hlink; /utype =3, 存放指向子表的指針 value; public: GenListNode ( ) : utype (0), tlink (NULL), ref (0) /構(gòu)造函數(shù), 建表頭結(jié)點(diǎn),GenListNode ( int t, GenListNode *next = NULL ) /構(gòu)造函數(shù)：建表結(jié)點(diǎn) Items Info ( ); /返回當(dāng)前表元素的值 int nodetype ( ) return utype; /返回當(dāng)前表元素的數(shù)據(jù)類型 void setInfo ( Items,class GenList /廣義表類定義 private: GenListNode *first; /廣義表頭指針 GenListNode *Copy ( GenListNode *ls ); /復(fù)制一個(gè) ls 指示的無共享非遞歸表 int depth ( GenListNode *ls ); /計(jì)算由 ls 指示的非遞歸表的深度 int equal (GenListNode *s, GenListNode *t); /比較以s和t為表頭的兩個(gè)表是否相等 void Remove (GenListNode *ls ); /釋放以 ls 為表頭結(jié)點(diǎn)的廣義表,public: Genlist ( ); /構(gòu)造函數(shù) GenList ( ); /析構(gòu)函數(shù) Items Head ( ); /返回表頭元素 GenList Tail ( ); /返回表尾 GenListNode *First ( ); /返回第一個(gè)元素 GenListNode * Next ( GenListNode *elem ); /返回表元素elem的直接后繼元素 GenList Addon ( GenList /將表結(jié)點(diǎn) x 加到表的最前端,void setNext ( GenListNode *elem1, GenListNode *elem2 ); /將elem2插到表中元素elem1后 void Copy ( const GenList /從廣義表的字符串描述 s 出發(fā), /建立一個(gè)帶表頭結(jié)點(diǎn)的廣義表結(jié)構(gòu) ,廣義表的訪問算法,廣義表結(jié)點(diǎn)類的存取成員函數(shù) Items GenListNode : Info ( ) /返回表元素的值 Items pitem; pitem.utype = utype; pitem.value = value; return pitem; ,void GenListNode : setInfo ( Items ,Items GenList : Head ( ) /若廣義表非空，則返回其第一個(gè)元素的值， /否則函數(shù)沒有定義。 if ( first-tlink = NULL ) return NULL; else /非空表 Items temp; temp.utype = frist-tlink-utype; temp.value = frist-tlink-value; return temp; /返回類型及值 ,GenList GenList : Tail ( ) /若廣義表非空，則返回廣義表除第一個(gè)元 /素外其它元素組成的表, 否則函數(shù)沒有定義 if ( frist-tlink = NULL ) return NULL; GenList temp; temp.first = new GenListNode; temp.first-utype = 0; temp.first-value.ref = 0; temp.first-tlink = Copy ( first-tlink-tlink); return temp; ,GenListNode * GenList : First ( ) if ( first-tlink = NULL ) return NULL; else return first-tlink; GenListNode * GenList : Next ( GenListNode *elem ) if ( elem-tlink = NULL ) return NULL; else return elem-tlink; ,GenList ,void GenList : Push ( GenListNode ,廣義表的遞歸算法,廣義表的復(fù)制算法 void GenList : Copy ( const GenList,switch ( ls-utype ) case 0: q-value.ref = ls-value.ref; break; case 1: grinfo = grinfo; break; case 2: q-value.charinfo = ls-value.charinfo; break; case 3: q-value.hlink = Copy (ls-value.hlink); ,q-tlink = Copy (ls-tlink); return q; ,求廣義表的深度,例如，對于廣義表 E (B (a, b), D (B (a, b), C (u, (x, y, z), A ( ) ) ),1,1,1,1,2,3,4,int GenList : depth ( GenListNode *ls ) if ( ls-tlink = NULL ) return 1; /空表 GenListNode * temp = ls-tlink; int m = 0; while ( temp != NULL ) /在表頂層橫掃 if ( temp-utype = 3 ) /結(jié)點(diǎn)為表結(jié)點(diǎn) int n = depth ( temp-value.hlink ); if ( m tlink; return m+1; ,int GenList : depth ( ) return depth ( first ); ,廣義表的刪除算法,0 1,1 5,3,3,1 2,0 1,2 x,0 1,0 1,2 y,ls,3,2 x,掃描子鏈表 若結(jié)點(diǎn)數(shù)據(jù)為x, 刪除?？赡茏鲅h(huán)連續(xù)刪。 若結(jié)點(diǎn)數(shù)據(jù)不為x，不執(zhí)行刪除。 若結(jié)點(diǎn)為子表，遞歸在子表執(zhí)行刪除。,掃描子鏈表 若結(jié)點(diǎn)數(shù)據(jù)為x, 刪除?？赡茏鲅h(huán)連續(xù)刪。 若結(jié)點(diǎn)數(shù)據(jù)不為x，不執(zhí)行刪除。 若結(jié)點(diǎn)為子表，遞歸在子表執(zhí)行刪除。,void delvalue(GenListNode * ls, const value x) /在廣義表中刪除所有含 x 的結(jié)點(diǎn) if ( ls-tlink != NULL ) /非空表 GenListNode * p = ls-tlink;,while ( p != NULL ,delvalue ( p, x ); /在后續(xù)鏈表中刪除 GenList : GenList ( ) /析構(gòu)函數(shù) Remove ( first ); delete