1、定義定義:若一個對象部分地包含它自己若一個對象部分地包含它自己, 或用或用它自己給自己定義它自己給自己定義, 則稱這個對象是遞歸的；則稱這個對象是遞歸的； 若一個過程直接地或間接地調用自己若一個過程直接地或間接地調用自己, 則稱這個過程是遞歸的過程則稱這個過程是遞歸的過程。三種遞歸情況三種遞歸情況定義是遞歸的定義是遞歸的 數據結構是遞歸的數據結構是遞歸的 問題的解法是遞歸的問題的解法是遞歸的求解階乘函數的遞歸算法求解階乘函數的遞歸算法long Factorial ( long n ) if ( n = 0 ) return 1; else return n * Factorial (n- -1

2、);例如，階乘函數例如，階乘函數時時當當時時當當 1 ,)!1( 0 , 1!nnnnn求解階乘求解階乘 n! 的過程的過程 main : fact(4)參數參數 4 計算計算 4*fact(3) 返回返回 24參數參數 3 計算計算 3*fact(2) 返回返回 6參數參數 2 計算計算 2*fact(1) 返回返回 2參數參數 1 計算計算 1*fact(0) 返回返回 1參數參數 0 直接定值直接定值 = 1 返回返回 1參參數數傳傳遞遞結結果果返返回回有若干結點的單鏈表有若干結點的單鏈表例如，單鏈表結構例如，單鏈表結構f f 只有一個結點的單鏈表只有一個結點的單鏈表例例1.1.搜索鏈表

3、最后一個結點并打印其數值搜索鏈表最后一個結點并打印其數值void Search ( ListNode *f ) if ( f -next = NULL ) printf (“%dn”, f -data ); else Search ( f -next );f f f f f a0a1a2a3a4遞歸找鏈尾例例2.在鏈表中尋找等于給定值的結點在鏈表中尋找等于給定值的結點,并打印其數值并打印其數值void Search ( ListNode * f, ListData x ) if ( f ! = NULL ) if ( f - data = x ) printf (“%dn”, f -data

4、); else Search ( f - next, x );遞歸找含x值的結點f f f f x例如，漢諾塔例如，漢諾塔(Tower of Hanoi)問題的解法：問題的解法： 如果如果 n = 1，則將這一個盤子直接從，則將這一個盤子直接從 X 柱柱移到移到 Z柱上。否則，執行以下三步：柱上。否則，執行以下三步： 用用 Z 柱做過渡，將柱做過渡，將 X 柱上的柱上的 (n- -1) 個盤子移個盤子移到到 Y 柱上：柱上： 將將 X 柱上最后一個盤子直接移到柱上最后一個盤子直接移到 Z 柱上；柱上； 用用 X 柱做過渡，將柱做過渡，將 Y 柱上的柱上的 (n- -1) 個盤子移個盤子移到到

5、Z 柱上。柱上。算法算法void hanoi (int n, char X, char Y, char Z) /解決漢諾塔問題的算法 if ( n = 1 ) printf ( move %s,X, to %s”,Z); else Hanoi ( n-1, X, Z, Y ); printf ( move %s,X, to %s”,Z); Hanoi ( n-1, Y, X, Z ); n遞歸方法是設計非數值計算程序的重要方法，它使得程序的結構清晰，形式簡潔，易于閱讀，正確性容易證明。n一般地講，一個問題采用遞歸算法求解時，須具備3個條件。 (1)能將一個問題轉變成一個新問題，而新問題與原問題

6、的解法相同或類同，所不同的僅是所處理的對象，且這些處理對象的變化是有規律的。 (2)可以通過上述轉化使問題逐步簡單化。 (3)必須有一個明確的遞歸出口(遞歸的邊界)。n遞歸過程在實現時，需要自己調用自己。遞歸過程在實現時，需要自己調用自己。n層層向下遞歸，退出時的次序正好相反：層層向下遞歸，退出時的次序正好相反： 遞歸調用遞歸調用 n! (n-1)! (n-2)! 1! 0!=1 返回次序返回次序n遞歸函數運行的遞歸函數運行的“層次層次”n函數嵌套調用時的函數嵌套調用時的“后調用先返回后調用先返回”原則原則n遞歸函數調用也是一種嵌套調用；每一次遞歸調用時，遞歸函數調用也是一種嵌套調用；每一次遞

7、歸調用時，也需要分配存儲空間（工作區）來存儲參數、局部變也需要分配存儲空間（工作區）來存儲參數、局部變量、返回地址等信息。量、返回地址等信息。n每層遞歸調用需分配的空間形成每層遞歸調用需分配的空間形成遞歸工作記錄遞歸工作記錄，按后，按后進先出進先出(LIFO)的棧組織。的棧組織。 局部變量局部變量返回地址返回地址參參 數數活動活動記錄記錄框架框架遞歸遞歸工作記錄工作記錄.Function() .調用塊函數塊n遞歸過程簡潔、易編、易懂遞歸過程簡潔、易編、易懂n遞歸過程效率低，重復計算多遞歸過程效率低，重復計算多n改為非遞歸過程的目的是提高效率改為非遞歸過程的目的是提高效率n單向遞歸和尾遞歸可直接

8、用迭代實現其單向遞歸和尾遞歸可直接用迭代實現其非遞歸過程非遞歸過程n其他情形必須借助棧實現非遞歸過程其他情形必須借助棧實現非遞歸過程計算斐波那契數列的函數計算斐波那契數列的函數Fib(n)的定義的定義求解斐波那契數列的遞歸算法求解斐波那契數列的遞歸算法 long Fib ( long n ) if ( n = 1 ) return n; else return Fib (n- -1) + Fib (n- -2); 1n2),Fib(n1)Fib(n0,1nn,)Fib(n如如 F0 = 0, F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5 Fib(1)Fib(0)

9、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)n tagtag = 1, 向左遞歸向左遞歸；tag = 2, 向右遞歸向右遞歸Long FibIter(long n) if (n =1) return n; long twoback=0,oneback=1,current; for (int I=2;Idata = e; p-next = NULL; Q.rear-next =

10、p; /入隊 Q.rear =p; return OK;出隊出隊int DeQueue ( LinkQueue &Q, QElemType &e) /刪去隊頭結點，并返回隊頭元素的值 if ( Q.front=Q.rear ) return ERROR; /判隊空 p = Q.front -next; e = p-data;/保存隊頭的值 Q.front-next = p-next; /新隊頭 if (Q.rear = p) Q.rear = Q.front ; free (p); return OK;循環隊列循環隊列 (Circular Queue)順序隊列順序隊列隊列的順序

11、存儲表示隊列的順序存儲表示 插入新的隊尾元素，尾指針增插入新的隊尾元素，尾指針增1，rear = rear + 1，刪除隊頭元素，頭指針增刪除隊頭元素，頭指針增1， front = front + 1，因此，在非空隊列中，頭指針始終指向隊列頭因此，在非空隊列中，頭指針始終指向隊列頭元素，而尾指針始終指向隊列尾元素的下一個元素，而尾指針始終指向隊列尾元素的下一個位置。位置。 隊滿時再進隊將溢出隊滿時再進隊將溢出 假溢出（圖假溢出（圖3.12) 解決辦法：將順序隊列解決辦法：將順序隊列臆造臆造為一個環狀的空間，為一個環狀的空間，形成循環形成循環(環形環形)隊列隊列隊列的進隊和出隊隊列的進隊和出隊f

12、rontrear空隊列空隊列frontrearA,B,C, D進隊進隊A B C DfrontrearA,B出隊出隊C DfrontrearE,F,G進隊進隊C D E F GC D E F GfrontrearH進隊進隊,溢出溢出循環隊列循環隊列 (Circular Queue)隊頭、隊尾指針加隊頭、隊尾指針加1，可用取模，可用取模(余數余數)運算實現。運算實現。隊頭指針進隊頭指針進1: front = (front+1) %maxsize;隊尾指針進隊尾指針進1: rear = (rear+1) % maxsize;隊列初始化隊列初始化：front = rear = 0;隊空條件隊空條件：

13、front = rear;隊滿條件：隊滿條件：(rear+1) % maxsize = front;01234567循環隊列循環隊列frontrearMaxsize-101234567frontBCDrear一般情況一般情況A01234567rear空隊列空隊列front隊滿條件：隊滿條件：(rear+1) % maxsize = frontC01234567frontrearDEFGABC隊滿隊滿C01234567frontrearDEFGABCH#define MAXSIZE 100Typedef structQElemType *base;int front;int rear; SqQu

14、eue;循環隊列的類型定義循環隊列的類型定義初始化隊列初始化隊列Status InitQueue ( SqQueue &Q ) /構造空隊列 Q.base=(QElemType *) malloc (MAXSIZE*sizeof(QElemType); if (! Q.base) exit(OVERFLOW); Q.rear = Q.front = 0; return OK;入隊入隊Status EnQueue ( SqQueue &Q, QElemType e ) if ( (Q.rear+1) % MAXSIZE =Q.front) return ERROR; /隊滿 Q.baseQ.rear = e; Q.rear = ( Q.rear+1) % MAXSIZE; return OK;出隊出隊Status DeQueue ( SqQueue &Q, QElemType &e ) if ( Q.front = Q.rear ) return ERROR; /隊空 e = Q.baseQ.front; Q.front = ( Q.front+1) % MAXSIZE;return OK;n銀行業務模擬程序 模擬銀行業務活動并計算一天中客戶在銀行平均逗留時間n事件驅動模擬按事件（客