概念
什么是遞歸锦担？一個方法在方法內(nèi)部直接或間接調(diào)用自身方法俭识。
應(yīng)用場景
下面3中情況，我們通常使用遞歸解決問題
1.定義是遞歸的
例如斐波拉契數(shù)列
long Fib(Long n){
if(n == 1 || n == 2) return 1;
else return Fib(n-1)+Fib(n-2);
}
對于類似這種復(fù)雜問題洞渔，若能夠分解成幾個簡單揭發(fā)相同或類似的子問題來求解套媚，便成為遞歸求解
采取分治法進行遞歸求解的問題需要滿足以下三個條件：
- 能講一個問題轉(zhuǎn)換成一個小問題。而新問題和原問題揭發(fā)相同或雷同磁椒。不同的僅僅是處理的對象堤瘤，并且這些處理更小且變化有規(guī)律的
- 可以通過上述轉(zhuǎn)換而使得問題簡化
- 必須有一個明確的遞歸出口，或成為二遞歸邊界
2.數(shù)據(jù)結(jié)構(gòu)是遞歸的
其數(shù)據(jù)結(jié)構(gòu)本身具有遞歸的特性
例如浆熔，對于鏈表本辐，其結(jié)點LNode的定義由數(shù)據(jù)域data和指針域next組成，而指針域next是一種指向LNode類型的指針蘸拔，即LNode的定義中又用到了其自身师郑，所以鏈表是一種遞歸的數(shù)據(jù)結(jié)構(gòu)
void TraverseList(LinkList p){
//
if(p == NULL) return; else{
// printf("%d",p->data); //p TraverseList(p->next);
}
10 11 }
3环葵、問題的解法是遞歸的
有一類問題调窍，雖然問題本身并沒有明顯的遞歸結(jié)構(gòu)，但是采用遞歸求解比迭代求解更簡單张遭，如Hanoi塔問題邓萨，八皇后問題，迷宮問題
遞歸過程與遞歸工作棧
一個遞歸函數(shù)菊卷，在函數(shù)的執(zhí)行過程中缔恳，需要多次進行自我調(diào)用。遞歸函數(shù)是如何執(zhí)行的洁闰？
在高級語言的程序中歉甚，調(diào)用函數(shù)和被調(diào)用的函數(shù)之間的鏈接與信息交換都是通過棧來進行的
通常，當(dāng)在一個函數(shù)的運行期間調(diào)用另一個函數(shù)時扑眉，在運行被調(diào)用函數(shù)之前纸泄，系統(tǒng)需要先完成3件事情：
- 將所有的實參赖钞、返回地址等信息傳遞給被調(diào)用函數(shù)保存
- 為被調(diào)用函數(shù)的局部變量分配存儲空間
- 將控制轉(zhuǎn)移到被調(diào)用函數(shù)入口
而從被調(diào)用函數(shù)返回到調(diào)用函數(shù)之前，系統(tǒng)同樣需要完成3件事 - 不存被調(diào)用函數(shù)的計算結(jié)果
- 釋放被調(diào)用函數(shù)的數(shù)據(jù)區(qū)
- 依照被調(diào)用函數(shù)保存的返回地址將控制器移動到調(diào)用函數(shù)
當(dāng)多個函數(shù)構(gòu)成嵌套調(diào)用時聘裁，按照“先調(diào)用后返回”的原則雪营，上述函數(shù)之間的信息傳遞和控制轉(zhuǎn)移必須通過“棧”來實現(xiàn)衡便。即系統(tǒng)將整個程序運行時的所需要的數(shù)據(jù)空間都安排在一個棧中献起，每當(dāng)調(diào)用一個函數(shù)時，就在他的棧頂分配一個存儲區(qū)镣陕。每當(dāng)整個函數(shù)退出時谴餐，就釋放它的存儲區(qū)。則當(dāng)前運行時的函數(shù)的數(shù)據(jù)區(qū)必在棧頂
一個遞歸函數(shù)的運行過程類似多個函數(shù)嵌套調(diào)用茁彭，只是調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個函數(shù)总寒。因此，和每次調(diào)用相關(guān)的一個重要概念是遞歸函數(shù)運行的層次理肺。假設(shè)調(diào)用該遞歸函數(shù)的主函數(shù)是第0層摄闸，則從主函數(shù)調(diào)用遞歸函數(shù)進入第一層，從第i層遞歸調(diào)用本函數(shù)為下一層妹萨。即第i+1層年枕。反正退出第i層遞歸應(yīng)返回上一層，即第i-1層乎完。
為了保證遞歸函數(shù)正確執(zhí)行熏兄，系統(tǒng)需要設(shè)立一個“遞歸工作棧”作為整個遞歸函數(shù)運行期間使用的數(shù)據(jù)存儲區(qū)树姨，每一層遞歸所需信息構(gòu)成一個工作記錄摩桶，其中包括所有的實參，所有的局部變量以及上一層的返回地址帽揪。每進入一層遞歸硝清，就產(chǎn)生一個新的工作記錄壓入棧頂。每退出一個遞歸转晰，就從棧頂彈出一個工作記錄芦拿，則當(dāng)前執(zhí)行層的工作記錄必須是遞歸工作棧頂?shù)墓ぷ饔涗洠Q為活動記錄
