棧與遞歸--含分治與回溯.ppt

1、3.3 棧與遞歸,什么是遞歸？ 為何用遞歸？ 如何用遞歸？ 遞歸實(shí)現(xiàn)原理-棧,1、什么是遞歸,main函數(shù) 調(diào)用函數(shù)f ,f 函數(shù) 調(diào)用函數(shù)g ,g 函數(shù) ,f 函數(shù) 調(diào)用函數(shù)f ,遞歸調(diào)用,函數(shù)調(diào)用,遞歸指函數(shù)直接或間接調(diào)用自己,2、遞歸原理與實(shí)現(xiàn)棧,系統(tǒng)在函數(shù)調(diào)用前完成的工作： 將返回地址等信息入棧，并保存本層局部變量值 為被調(diào)函數(shù)的局部變量分配存儲(chǔ)區(qū) 將控制轉(zhuǎn)移到被調(diào)函數(shù)代碼區(qū)的入口 系統(tǒng)在被調(diào)函數(shù)返回之前完成的工作： 保存被調(diào)函數(shù)的計(jì)算結(jié)果 釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū) 出棧并根據(jù)返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù),恢復(fù)執(zhí)行 遞歸作為函數(shù)調(diào)用特例過程同上，允許遞歸的語言中系統(tǒng)自動(dòng)維護(hù)一個(gè)遞歸工作棧,

2、不支持遞歸時(shí)用戶可仿照系統(tǒng)自行設(shè)立遞歸工作棧,int f ( int n ) 1 int r; 2 if(n= =1) r=1; 3 else r=n*f (n-1); 4 return r; ,void main( ) 5 int x; 6 x=f(5); 7 print(x); ,3+ 4 *,3+ 3 *,3+ 2 *,6+ 5 *,3+ 1 1, 6, 2, 1, 24,120,返址 n r,利用棧將遞歸化為非遞歸舉例：,int f(int n ) SElemType e,temp; SqStack S; InitStack(S); while(n1) /遞歸前進(jìn)，入棧 e.n=n;P

3、ush(S,e); n-; e.n=1;e.r=1; /邊界條件 while(!StackEmpty(S) /遞歸后退，出棧 Pop(S,temp); temp.r=temp.n*e.r; e=temp; /遞歸結(jié)束 return e.r;/返回結(jié)果 /更多可參考相關(guān)論文,int f ( int n ) int r; if(n= =1) r=1; else r=n*f (n-1); return r; ,void main( ) int x; x=f(5); printf(“%d”,x); ,3 、為何用遞歸與遞歸執(zhí)行過程,很多問題能夠用遞歸的方式描述，此時(shí)采用遞歸算法求解直觀容易，如求階乘：

4、F(1)=1; F(n)=n*F(n-1),3+ 4 *,3+ 3 *,3+ 2 *,6+ 5 *,3+ 1 1, 6, 2, 1, 24, 120,返址 n r,5 6 7,1 2 3 4,利用遞歸可方便地解決很多普通方法無法求解的問題,顯式遞歸問題，如求Fibnacci數(shù)列 F(n)=F(n-1)+F(n-2)遞歸公式；F(1)=1,F(2)=1邊界條件,int f ( int n ) if(n= =1|n= =2) r=1; /寫f(n)=1錯(cuò) else r=f (n-1)+f (n-2);/注意 return r; ,4、如何用遞歸,遞歸求解的關(guān)鍵是找邊界條件和遞歸關(guān)系編寫遞歸函數(shù)，根

5、據(jù)邊界條件和遞歸關(guān)系是否明顯可將問題分為顯示遞歸和隱式遞歸兩類，前者可直接寫出遞歸函數(shù)，后者要通過認(rèn)真分析找到邊界條件，并通過降階+分治+回溯找遞歸關(guān)系,邊界條件,遞歸公式,隱式遞歸降階,Edouard Lucas 1842-1891,French,A,B,C,每次只移一個(gè)盤 大盤不能壓小盤,類似數(shù)學(xué)歸納法，假設(shè)f(n-1)已知，在此基礎(chǔ)上考慮f(n)的求法,如Hannoi塔問題,X,Y,Z,邊界條件: if(n= =1) printf(“%c%c”,x,z);,X,Y,Z,降階:假設(shè)能把n-1個(gè)盤從一個(gè)位置移動(dòng)到另一個(gè)位置則.,hanoi(n, x, y, z); 降階：分三步 hanoi(

6、n-1, x, z, y); printf(“%c%c”,x,z); hanoi(n-1, y, x, z);,遞歸函數(shù)：,hanoi(int n, char x,char y, char z) 基始條件: if(n= =1) printf(“%c%c”,x,z); 降階：分三步 hanoi(n-1, x, z, y); printf(“%c%c”,x,z); hanoi(n-1, y, x, z);,x,y,z,A,B,C,void hanoi(int n, char x, char y, char z) if(n= =1) printf(“%c%cn”,x,z); else hanoi(n

7、-1, x, z, y); printf(“%c%cn”,x,z); hanoi(n-1, y, x, z); void main( ) hanoi(3,A,B,C); ,A C A B C B A C B A B C A C,遞歸函數(shù)中要有使遞歸趨于結(jié)束的邊界條件 對(duì)于Fibnacci數(shù)列中F(n)=F(n-1)+F(n-2)形式的遞歸公式，分析求f(5)的過程可知f(1)被多次重復(fù)調(diào)用，因此原因，求F(40)在Core2 T5500CPU上約費(fèi)20秒時(shí)間，故此類問題要避免遞歸，需用非遞歸算法改寫遞歸參考書 參考”關(guān)于遞歸教學(xué)的探討.doc”,注意事項(xiàng)：,隱式遞歸分治,-樹的相關(guān)操作,int

8、 TreeDepth(Tree T)/求二叉樹深 if(T=NULL)d=0; else d1=TreeDepth(T-lchild1); d2=TreeDepth(T-rchild); if(d1d2) d=d1+1; else d=d2+1; return d; ,一棵樹由根結(jié)點(diǎn)、左子樹及右子樹組成，對(duì)樹的操作可分成對(duì)根、左子樹和右子樹的操作來完成！,隱式遞歸回溯,-8皇后問題,終態(tài)易判定,遞歸過程記錄完整解,回溯輸出.Go-Verify,int Go(int arrNN,int i) /逐行處理，當(dāng)前處理編號(hào)為i的行 int j; for (j = 0; jN; +j) arrij = 1;/嘗試在第i行的第j列擺下一個(gè)棋子; int successFlag=Verify(arr,i); if (successFlag=0) arrij=0; continue; else if(successFlag=1,void PrintChessBoard(int aNN) int i,j; for(i=0;i1)return 0; return 1; ,隱式遞歸回溯（全部解）,void Go(int arrNN,int i) /逐行處理，當(dāng)前處理編號(hào)為i的行 for (int j = 0; jN; +j) arrij = 1;/嘗試在第i行的第j列