一:什么是遞歸?
若在一個函數(shù)(數(shù)據(jù)結(jié)構(gòu))里,直接或間接出現(xiàn)調(diào)用本身,則稱它們?yōu)檫f歸的;
二:什么時候使用遞歸?
(1) 數(shù)學(xué)定義是遞歸的
(2)數(shù)據(jù)結(jié)構(gòu)是遞歸的
(3)問題的解法是遞歸的
這是什么意思呢?
(1) 數(shù)學(xué)定義是遞歸的
比如很多的數(shù)學(xué)定義都是遞歸定義,比如
1.階乘
階乘:Fact(n)
(1) 若n=0, 則返回1;
(2) 若n > 1, 則返回n*Fact(n-1);
例子:
long Fact(Long n){
if(n=0) return -1;
else return n * Fact(n-1);
}
- 二階斐波拉契數(shù)列
斐波拉契數(shù)列:Fib(n)
(1) 若n=1或n=2, 則返回1;
(2) 若n > 2, 則返回Fib(n-1) + Fib(n-2);
例子:
long Fib(Long n){
if(n == 1 || n == 2) return 1;
else return Fib(n-1)+Fib(n-2);
}
對于類似這種的復(fù)雜問題,若能分解成幾個簡單且解法類似的子問題來求解,則稱為遞歸求解;
3.分治法
什么時候使用分治法?
(1)能將一個大問題轉(zhuǎn)變?yōu)橐粋€小問題,而新問題和原問題解法類似或相同,不同的僅僅是處理的對象,并且這些處理更小且變化是有規(guī)律的;(可拆解)
(2)可以通過上述轉(zhuǎn)化而使得問題簡單化;(簡化問題)
(3)必須有一個明確的遞歸出口(遞歸邊界);(終止遞歸的條件)
void p(參數(shù)表,形參 ){
if(遞歸結(jié)束的條件) Return 結(jié)果; //遞歸邊界
else p(參數(shù)); //遞歸的步棸
}
三:數(shù)據(jù)結(jié)構(gòu)是遞歸的
其數(shù)據(jù)結(jié)構(gòu)本身有遞歸的特性;
例如:對于鏈表,其節(jié)點LNode的定義有數(shù)據(jù)域data和指針域dext組成,而指針域next是一種指向LNode類型的指針,即LNode的定義中又用到了其自身,所以鏈表是一種遞歸的數(shù)據(jù)結(jié)構(gòu);
void TraverseList(LinkList p){
//遞歸的終止條件
if(p == NULL) return;
//遞歸步棸
else{
//輸出當(dāng)前節(jié)點的數(shù)據(jù)域
printf("%d",p->data);
//移動指針,輸出下一個節(jié)點的數(shù)據(jù)域
TraverseList(p->next);
}
}
總結(jié):在遞歸算法中,如果當(dāng)遞歸結(jié)束條件成立,只執(zhí)行Return操作時,分治法求解遞歸問題算法一般形式可以簡化為:
void p(參數(shù)表,形參 ){
if(遞歸結(jié)束的條件) Return 結(jié)果; //遞歸邊界
else p(參數(shù)); //遞歸的步棸
}
四:問題的解法是遞歸的?
有一類問題,雖然問題本身并沒有明顯的遞歸結(jié)果,但是采用遞歸求解比迭代求解更簡單,例如:Hanoi塔問題,八皇問題,迷宮問題等;
五:遞歸過程與遞歸工作棧
一個遞歸函數(shù),在函數(shù)的執(zhí)行過程中,需要多次進(jìn)行自我調(diào)用,那么思考一下,此時的遞歸函數(shù)是如何執(zhí)行的?
在了解遞歸函數(shù)是如何執(zhí)行之前,先了解一下任意兩個函數(shù)之間的調(diào)用是如何進(jìn)行的?
通常,當(dāng)在一個函數(shù)的運行期間調(diào)用另一個函數(shù)時,在運行被調(diào)用函數(shù)之前,系統(tǒng)要做三件事:
1.將所有的實參,返回地址等信息調(diào)用傳遞給被調(diào)用函數(shù)保存;
2.為被調(diào)用函數(shù)的局部變量分配存儲空間;
3.將控制權(quán)轉(zhuǎn)移到被調(diào)用函數(shù)入口;
而從被調(diào)用函數(shù)返回到調(diào)用函數(shù)之前,系統(tǒng)同樣要做三件事情:
1.保存被調(diào)用函數(shù)的計算結(jié)果;
2.釋放被調(diào)用函數(shù)的數(shù)據(jù)區(qū);
3.依照被調(diào)用函數(shù)保存的返回地址將控制權(quán)移動到調(diào)用函數(shù);
當(dāng)多個函數(shù)構(gòu)成嵌套調(diào)用時,按照"先調(diào)用后返回"的原則,上述函數(shù)之間的信息傳遞和控制傳遞都必須通過"棧"來實現(xiàn),即系統(tǒng)程序整個運行時的所需要的數(shù)據(jù)空間都安排在一個棧中,每當(dāng)調(diào)用一個函數(shù)時,就在它的棧頂分配一個存儲區(qū),每當(dāng)這個函數(shù)退出時,就釋放它的存儲區(qū),則當(dāng)前運行的函數(shù)的數(shù)據(jù)區(qū)必須在棧頂;
例如:
在主函數(shù)main中調(diào)用函數(shù)first函數(shù),而在first函數(shù)中又嵌套調(diào)用了second函數(shù),則當(dāng)我們執(zhí)行當(dāng)前函數(shù)first時,則first函數(shù)的數(shù)據(jù)區(qū)在棧頂;而當(dāng)我們執(zhí)行second函數(shù)時,second函數(shù)的數(shù)據(jù)區(qū)在棧頂;
總結(jié):
一個遞歸函數(shù)的運行過程類似多個函數(shù)的嵌套調(diào)用,只是調(diào)用函數(shù)和被調(diào)用函數(shù)都是同一個函數(shù),因此,每次調(diào)用本身時,就會產(chǎn)生一個調(diào)用相關(guān)的一個重要概念就是遞歸函數(shù)運行的"層次".假設(shè)調(diào)用改遞歸函數(shù)的主函數(shù)為第0層,則從主函數(shù)調(diào)用遞歸函數(shù)進(jìn)入到第一層,從第i層遞歸調(diào)用本函數(shù)進(jìn)入下一層為第i+1層,反之退出第i層遞歸函數(shù)返回上一層為第i-1層;
為了保證遞歸函數(shù)正確執(zhí)行,系統(tǒng)需要設(shè)立一個"遞歸工作棧"作為整個遞歸函數(shù)運行期間使用的數(shù)據(jù)存儲區(qū),每一層遞歸所需信息構(gòu)成一個工作記錄,其中包括所有實參,所有局部變量以及上一層的返回地址.每進(jìn)入一層遞歸,就產(chǎn)生一個新的工作記錄壓入棧頂,每退出一個遞歸,就從棧頂彈出一個工作記錄,則當(dāng)前執(zhí)行層的工作記錄必須是遞歸工作棧棧頂?shù)墓ぷ饔涗?此稱為"活動記錄";
