數據結構棧與遞歸含分治與回溯第一頁，共十七頁，編輯于2023年，星期三1、什么是遞歸main函數{……

調用函數f……}f函數{……

調用函數g……}g函數{………………}f函數{……

調用函數f……}遞歸調用函數調用遞歸指函數直接或間接調用自己第二頁，共十七頁，編輯于2023年，星期三intf(intn){intr;if(n==1)r=1;elser=n*f(n-1);returnr;}voidmain(){intx;x=f(5);printf(“%d”,x);}2、為何用遞歸與遞歸執行過程很多問題能夠用遞歸的方式描述，此時采用遞歸算法求解直觀容易，如求階乘：F(1)=1;F(n)=n*F(n-1)3+4*3+3*3+2*6+5*3+11←

6←

2← 1←

24←

120返址nr5671234利用遞歸可方便地解決很多普通方法無法求解的問題第三頁，共十七頁，編輯于2023年，星期三顯式遞歸問題，如求Fibnacci數列F(n)=F(n-1)+F(n-2)遞歸公式；F(1)=1,F(2)=1邊界條件intf(intn){if(n==1||n==2)r=1;//寫f(n)=1錯elser=f(n-1)+f(n-2);//注意returnr;}3、如何用遞歸遞歸求解的關鍵是找邊界條件和遞歸關系編寫遞歸函數，根據邊界條件和遞歸關系是否明顯可將問題分為顯示遞歸和隱式遞歸兩類，前者可直接寫出遞歸函數，后者要通過認真分析找到邊界條件，并通過降階+分治+回溯找遞歸關系邊界條件遞歸公式第四頁，共十七頁，編輯于2023年，星期三隱式遞歸—降階EdouardLucas

1842-1891,FrenchABC每次只移一個盤大盤不能壓小盤類似數學歸納法，假設f(n-1)已知，在此基礎上考慮f(n)的求法,如Hannoi塔問題第五頁，共十七頁，編輯于2023年，星期三XYZ邊界條件: if(n==1)printf(“%c→%c”,x,z);第六頁，共十七頁，編輯于2023年，星期三XYZ降階:假設能把n-1個盤從一個位置移動到另一個位置則...hanoi(n,x,y,z);降階：分三步hanoi(n-1,x,z,y);printf(“%c→%c”,x,z);hanoi(n-1,y,x,z);第七頁，共十七頁，編輯于2023年，星期三遞歸函數：hanoi(intn,charx,chary,charz)基始條件: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);xyz第八頁，共十七頁，編輯于2023年，星期三ABCvoidhanoi(intn,charx,chary,charz){if(n==1)printf(“%c→%c\n”,x,z);else{hanoi(n-1,x,z,y);printf(“%c→%c\n”,x,z);hanoi(n-1,y,x,z);}}voidmain(){hanoi(3,’A’,’B’,’C’);}A→

CA→

BC→

BA→

CB→

AB→

CA→

C第九頁，共十七頁，編輯于2023年，星期三遞歸函數中要有使遞歸趨于結束的邊界條件對于Fibnacci數列中F(n)=F(n-1)+F(n-2)形式的遞歸公式，分析求f(5)的過程可知f(1)被多次重復調用，因此原因，求F(40)在Core2T5500CPU上約費20秒時間，故此類問題要避免遞歸，需用非遞歸算法改寫遞歸—參考書參考”關于遞歸教學的探討.doc”注意事項：第十頁，共十七頁，編輯于2023年，星期三隱式遞歸—分治--樹的相關操作intTreeDepth(TreeT){//求二叉樹深 if(T==NULL)d=0; else{

d1=TreeDepth(T->lchild1);

d2=TreeDepth(T->rchild);if(d1>d2)

d=d1+1; else d=d2+1; } returnd;}一棵樹由根結點、左子樹及右子樹組成，對樹的操作可分成對根、左子樹和右子樹的操作來完成！6/5-43-12*+第十一頁，共十七頁，編輯于2023年，星期三隱式遞歸—回溯--8皇后問題終態易判定,遞歸過程記錄完整解,回溯輸出.Go-Verifyint

Go(intarr[N][N],inti)//逐行處理，當前處理編號為i的行{

intj;

for(j=0;j<N;++j)

{

arr[i][j]=1;//嘗試在第i行的第j列擺下一個棋子;intsuccessFlag=Verify(arr,i);

if(successFlag==0){arr[i][j]=0;continue;}

elseif(successFlag==1&&i<N-1){//驗證合法則前進到下一行

//僅當從當前布局前進得不到結果時重布局if(Go(arr,i+1)==1)return1;else{arr[i][j]=0;continue;}

}

else{//驗證合法且（到達結束i=N-1）則輸出解，所有解！

PrintChessBoard(arr);return1;

}

}if(j==N)return-1;}voidmain(){ inta[N][N]={0}; Go(a,0);}第十二頁，共十七頁，編輯于2023年，星期三voidPrintChessBoard(inta[N][N]){ inti,j; for(i=0;i<N;i++) { for(j=0;j<N;j++) { printf("%3d",a[i][j]); } printf("\n"); } printf("\n\n");}intVerify(inta[N][N],inti){ intsum,j,k; for(j=0;j<N;j++)//逐列檢查 { sum=0; for(k=0;k<=i;k++)//看當前列前i行中是否沖突 { sum+=a[k][j]; } if(sum>1)return0; } return1;}第十三頁，共十七頁，編輯于2023年，星期三隱式遞歸—回溯（全部解）voidGo(intarr[N][N],inti)//逐行處理，當前處理編號為i的行{

for(intj=0;j<N;++j)

{

arr[i][j]=1;//嘗試在第i行的第j列擺下一個棋子;successFlag=Verify(arr,i);

if(successFlag==0){arr[i][j]=0;continue;}

elseif(successFlag==1&&i<N-1){//驗證合法則前進到下一行

Go(arr,i+1);arr[i][j]=0;continue;

//不管成功與否都重置

}

else{//驗證合法且到終態（i=N-1）則輸出解。輸出所有解！

PrintChessBoard(arr);arr[i][j]=0;continue;

}

}}voidmain(){ inta[N][N]={0}; Go(a,0);}第十四頁，共十七頁，編輯于2023年，星期三4、遞歸原理與實現—棧系統在函數調用前完成的工作：將返回地址等信息入棧，并保存本層局部變量值為被調函數的局部變量分配存儲區將控制轉移到被調函數代碼區的入口系統在被調函數返回之前完成的工作：保存被調函數的計算結果釋放被調函數的數據區出棧并根據返回地址將控制轉移到調用函數,恢復執行遞歸作為函數調用特例過程同上，允許遞歸的語言中系統自動維護一個遞歸工作棧,不支持遞歸時用戶可仿照系統自行設立遞歸工作棧第十五頁，共十七頁，編輯于2023年，星期三intf(intn){1intr;2if(n==1)r=1;3elser=n*f(n-1);4returnr;}voidmain(){5intx;6x=f(5);7print(x);}3+4*3+3*3+2*6+5*3+11←

6←

2← 1←

24120返址nr利用棧將遞歸化為非遞歸舉例：intf(intn){

SElemTypee,temp;

SqStackS; InitStack(S); while(n>1){//遞歸前進，入棧 e.n=n; Push(S,e); n--; } e.n=1;e.r=1;Push(S,e);//邊界條件 while(!StackEmpty(S)){//