專業(yè)課課件-數(shù)據(jù)結(jié)構(gòu)第6講遞歸

二、遞歸函數(shù)設(shè)計(jì)方法

一、遞歸應(yīng)用分類三、遞歸注意事項(xiàng)遞歸

一、遞歸類型函數(shù)遞歸:若一個(gè)函數(shù)含直接或間接調(diào)用本函數(shù)的語句;定義遞歸:若一個(gè)對(duì)象部分地包含它自己,或用它自己給自己定義;過程遞歸:若一個(gè)過程直接地或間接地調(diào)用自己;1.函數(shù)遞歸階乘函數(shù)定義:n!={1當(dāng)n=0時(shí)n(n-1)!當(dāng)n>0時(shí)intFactorial(intn){if(n==0)return1; //終止條件

elsereturnn*Factorial(n-1);//遞歸步驟}斐波那契數(shù)列函數(shù)定義:

Fib(n)={1當(dāng)n=0,1時(shí)

Fib(n-1)+Fib(n-2)當(dāng)n>1時(shí)longFib(longn){if(n<=1)return1; //終止條件

elsereturnFib(n-1)+Fib(n-2);//遞歸步驟}2.定義遞歸樹的定義:

設(shè)D為數(shù)據(jù)對(duì)象集合,若n=0,則稱為空樹；否則:(1)當(dāng)n＝1時(shí)，存在只有樹根root的樹；

(2)當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,…,Tm,其中每一棵子集本身又是一棵符合本定義的子樹.二叉樹的定義:1.或?yàn)榭斩鏄洌?.或是由一個(gè)根結(jié)點(diǎn)構(gòu)成的二叉樹;3.或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為

左子樹和右子樹的、互不交的二叉樹

組成;

TypedefstructLNode{ElemTypedata;//數(shù)據(jù)域

structLnode*next;//指針域

}LNode,*LinkList;單鏈表結(jié)點(diǎn)的定義3.過程遞歸（解決方案遞歸）

漢諾塔問題123XYZ1、分治法(又稱分割求解法)二、遞歸函數(shù)設(shè)計(jì)方法2、后置遞歸法3、回溯法對(duì)于一個(gè)輸入規(guī)模為n的函數(shù)或問題，用某種方法把輸入分割成k(1<k≤n)個(gè)子集，從而產(chǎn)生k個(gè)相似的子問題；分別求解這k個(gè)子問題，得出

k個(gè)問題的子解;再用某種方法把它們組合成原來問題的解；若子問題還相當(dāng)大，則可以反復(fù)使用分治法，直至最后所分得的子問題足夠小，以至可以直接求解為止。1.分治法

設(shè)計(jì)思想:斐波那契列函數(shù)定義:

Fib(n)={1當(dāng)n=0,1時(shí)

Fib(n-1)+Fib(n-2)當(dāng)n>1時(shí)longFib(longn){if(n<=1)return1; //終止條件

elsereturnFib(n-1)+Fib(n-2);//遞歸步驟}intFib(intn){if(n<=1)return1; //終止條件

elsereturnFib(n-1)+Fib(n-2);//遞歸步驟}F5F4F3F3F2F2F1F1F0F1F0。。。n=5遞歸樹1、分治法(又稱分割求解法)二、遞歸函數(shù)設(shè)計(jì)方法2、后置遞歸法3、回溯法2.后置遞歸設(shè)計(jì)思想假如某個(gè)問題的求解過程可以分成若干步進(jìn)行，并且當(dāng)前這一步的解可以直接求得，則先求出當(dāng)前這一步的解，對(duì)于余下的問題，若問題的性質(zhì)和原問題類似，則又可遞歸求解。單鏈表是一種順序結(jié)構(gòu)，必須從第一個(gè)結(jié)點(diǎn)起，逐個(gè)檢查每個(gè)結(jié)點(diǎn)的數(shù)據(jù)元素;分析:2)從另一角度看，鏈表又是一個(gè)遞歸結(jié)構(gòu)，若L是帶頭結(jié)點(diǎn)線性鏈表(a1,a2,,an)

的頭指針，則L->next是線性鏈表

(a2,,an)的頭指針。后置遞歸算法的典型舉例:

刪除單鏈表中所有值為x的數(shù)據(jù)元素

a1

a2

a3

an

L…例如:

a2

a3

an

…

a1

L已知下列鏈表1)“a1=x”,則L

仍為刪除x后的鏈表頭指針2)“a1≠x”,則余下問題是考慮以L->next為頭指針的鏈表L=L->nextL->next=L->next->next

a1

a2

a3

an

…Lvoid

delete(LinkList&L,ElemTypex)

{

//刪除以L為頭指針的帶頭結(jié)點(diǎn)的單鏈表中

//所有值為x的數(shù)據(jù)元素

if(L->next){

if(L->next->data==x){

p=L->next;L->next=p->next;free(p);

delete(L,x);

}else

delete(L->next,x);

}}//delete后置遞歸1.分治法(又稱分割求解法)三、遞歸函數(shù)設(shè)計(jì)方法2.后置遞歸法3.回溯法

皇后問題設(shè)四皇后問題的解為(x1,x2,x3,x4),

其中:

xi(i=1,2,3,4)的約束條件為:其中任意兩個(gè)xi

和xj不能位于棋盤的同行、同列及同對(duì)角線。

1234X1X2X3X43.回溯法

是一種“窮舉搜索”方法。其基本思想為:假設(shè)問題的解為n元組(x1,x2,…,xn)；如果n元組的部分解為(x1,x2,…,xi)(i<n),且應(yīng)滿足一定的約束條件；對(duì)于已求得的部分解(x1,x2,…,xi)，若在添加xi+1

之后仍然滿足約束條件，則得到一個(gè)新的部分解(x1,x2,…,xi+1)；之后繼續(xù)添加xi+2并檢查之；若找不到一個(gè)xi+1滿足約束條件，則從當(dāng)前部分解中刪去xi,回溯到前一個(gè)部分解(x1,x2,

,xi-1),重新添加那些尚未考察過的xi，并檢查之；5.如此反復(fù)進(jìn)行，直至求得滿足約束條件的問題的解，或者證明問題無解；皇后問題設(shè)四皇后問題的解為(x1,x2,x3,x4),

其中:

xi(i=1,2,3,4)，約束條件為:其中任意兩個(gè)xi

和xj不能位于棋盤的同行、同列及同對(duì)角線.

1234X1X2X3X4x1=1x2=3x1=2x2=4x3=1x4=3皇后問題回溯算法關(guān)鍵:搜索策略:深度優(yōu)先，依次取xi=1,2,3,4;約束條件:xi和xj不位于棋盤的同行、同列及同對(duì)角線上；終止條件:找到滿足條件的x1,x2x3,x4；

即:i=n回溯條件:

在當(dāng)前初始條件下無解；無解:回溯到了起始狀態(tài),i=0；void

Trial(inti,intn)

{//進(jìn)入本函數(shù)時(shí)，在n×n棋盤前i-1行已放置了互不攻

//擊的i-1個(gè)棋子?，F(xiàn)從第i行起繼續(xù)為后續(xù)棋子選擇

//滿足約束條件的位置。當(dāng)求得(i>n)的一個(gè)合法布局

//時(shí)，輸出之。i的初始值為1。

if(i=0)無解；

if(i>n)輸出棋盤的當(dāng)前布局;//終止

elsefor(j=1;j<=n;++j){//試探策略

在第i行第j列放置一個(gè)棋子;

if(當(dāng)前布局合法)Trial(i+1,n);//約束-遞歸

移去第i行第j列的棋子;//回溯

} }//Trial

先寫出問題求解的遞歸定義,包括兩項(xiàng)內(nèi)容:

基本項(xiàng):描述一個(gè)或幾個(gè)遞歸過程的終結(jié)狀態(tài)；歸納項(xiàng):

描述如何從當(dāng)前狀態(tài)到下一狀態(tài)的轉(zhuǎn)換；四、遞歸注意事項(xiàng)2寫遞歸函數(shù)時(shí)注意:

嚴(yán)格定義函數(shù)的功能和接口;

將每一個(gè)遞歸看成一個(gè)簡(jiǎn)單的操作;

切忌想得太深太遠(yuǎn)！遞歸樹的深度即為遞歸函數(shù)的遞歸深度遞歸樹上的結(jié)點(diǎn)數(shù)目恰為函數(shù)中的主要操作重復(fù)進(jìn)行的次數(shù)；若遞歸樹蛻化為單支樹或者遞歸樹中含有很多相同的結(jié)點(diǎn)，則表明該遞歸函數(shù)不適用。3.

分析遞歸算法的工具是遞歸樹，從遞歸樹上可以得到遞歸函數(shù)的各種相關(guān)信息。如:求n!的遞歸函數(shù)的遞歸樹已退化為一個(gè)單枝樹;nn-110。。。intFactorial(intn){if(n==0)return1;

elsereturnn*Factorial(n-1);

}intFactorial(intn){i＝1;k=1;while