棧的應(yīng)用-遞歸
上一節(jié)我們講到了棧這種數(shù)據(jù)結(jié)構(gòu)滴肿，那么在實(shí)際編程中有哪些應(yīng)用呢？這篇文章我們來(lái)研究一下棧的一種應(yīng)用-遞歸
遞歸的基本思想
遞歸的基本思想佃迄，是把規(guī)模較大的一個(gè)問(wèn)題泼差，分解成規(guī)模較小的多個(gè)子問(wèn)題去解決，而每一個(gè)子問(wèn)題又可以繼續(xù)拆分成多個(gè)更小的子問(wèn)題呵俏。
最重要的一點(diǎn)就是假設(shè)子問(wèn)題已經(jīng)解決了堆缘，現(xiàn)在要基于已經(jīng)解決的子問(wèn)題來(lái)解決當(dāng)前問(wèn)題；或者說(shuō)柴信，必須先解決子問(wèn)題套啤，再基于子問(wèn)題來(lái)解決當(dāng)前問(wèn)題。
總的來(lái)說(shuō)随常，使用遞歸來(lái)解決問(wèn)題就是將復(fù)雜的問(wèn)題簡(jiǎn)單化潜沦。但是有些時(shí)候并不能使用遞歸解決問(wèn)題，那么在什么情況下我們才能去使用遞歸呢绪氛？有以下三種情況：
- 定義是遞歸的
比如很多數(shù)學(xué)定義本身就是遞歸定義唆鸡；例如大家非常熟悉的階乘：
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);
}
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);
}
對(duì)于類似于這種復(fù)雜的問(wèn)題，能夠分解成幾個(gè)簡(jiǎn)單且解法相同或類似的子問(wèn)題來(lái)求解枣察，便成為遞歸求解争占。
例如在求解4乔妈！時(shí)先求解3湿硝！，然后再進(jìn)一步分解進(jìn)行求解囊骤，這種求解方法也叫做“分治法”猿涨。
采用“分治法”進(jìn)行遞歸求解的問(wèn)題需滿足三個(gè)條件：
-能夠?qū)⒁粋€(gè)問(wèn)題轉(zhuǎn)變?yōu)橐粋€(gè)小問(wèn)題握童，而新問(wèn)題和原問(wèn)題的解法相同或類似。不同的僅僅是處理的對(duì)象叛赚，并且處理更小且變化時(shí)有規(guī)律的
-可以通過(guò)上述轉(zhuǎn)換而使得問(wèn)題更加簡(jiǎn)化
-必須要有一個(gè)明確的遞歸出口澡绩，或成為遞歸邊界
- 數(shù)據(jù)結(jié)構(gòu)是遞歸的
其數(shù)據(jù)結(jié)構(gòu)本身具有遞歸的特性。
例如俺附，對(duì)于鏈表Node的定義由數(shù)據(jù)域和指針域next組成肥卡，而指針域next是一種指向Node類型的指針，即Node的定義中又用到了其自身事镣。所以鏈表也是一種遞歸的數(shù)據(jù)結(jié)構(gòu)步鉴。
void TraverseList(LinkList p){
//遞歸終止
if(p == NULL)
return;
else{
// 輸出當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)域
printf("%d",p->data);
//p 指向后繼節(jié)點(diǎn)繼續(xù)遞歸
TraverseList(p->next);
}
}
- 問(wèn)題的解法是遞歸的
有一類問(wèn)題，雖然問(wèn)題本身并沒(méi)有明顯的遞歸結(jié)構(gòu)，但是采用遞歸求解比迭代求解更簡(jiǎn)單唠叛，比如Hanoi塔問(wèn)題只嚣，八皇后問(wèn)題，迷宮問(wèn)題
遞歸過(guò)程與遞歸工作棧
一個(gè)遞歸函數(shù)艺沼，在函數(shù)的執(zhí)行過(guò)程中，需要進(jìn)行多次自我調(diào)用蕴掏。那么思考一下障般，一個(gè)遞歸函數(shù)是如何執(zhí)行的？
在了解遞歸函數(shù)是如何執(zhí)行之前盛杰，先來(lái)了解一下任何的兩個(gè)函數(shù)之間是如何進(jìn)行調(diào)用的挽荡；
在高級(jí)語(yǔ)言的程序中，調(diào)用函數(shù)和被調(diào)用函數(shù)之間的鏈接與信息交換都是通過(guò)棧來(lái)進(jìn)行的即供。
通常定拟，當(dāng)在一個(gè)函數(shù)的運(yùn)行期間調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)行被調(diào)用函數(shù)之前逗嫡，系統(tǒng)需要完成三件事情：
-將所有的實(shí)參青自，返回地址等信息調(diào)用傳遞給被調(diào)用函數(shù)保存；
-為被調(diào)用函數(shù)的局部變量分配存儲(chǔ)空間
-將控制轉(zhuǎn)移到被調(diào)用函數(shù)入口
而從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前驱证，系統(tǒng)同樣需要完成三件事：
-保存被調(diào)用函數(shù)的計(jì)算結(jié)果延窜；
-釋放被調(diào)用函數(shù)的數(shù)據(jù)區(qū)
-依照被調(diào)用函數(shù)保存的返回地址將控制移動(dòng)到調(diào)用函數(shù)抹锄。
當(dāng)多個(gè)函數(shù)構(gòu)成嵌套調(diào)用時(shí)，按照“先調(diào)用后返回”原則获高，上述函數(shù)之間的信息傳遞和控制轉(zhuǎn)移必須通過(guò)“椖钛恚”來(lái)實(shí)現(xiàn)扫沼，即系統(tǒng)將整個(gè)程序運(yùn)行時(shí)所需要的數(shù)據(jù)空間都安排在一個(gè)棧中缎除，每當(dāng)調(diào)用一個(gè)函數(shù)時(shí)器罐，就在它的棧頂分配一個(gè)存儲(chǔ)區(qū)。每當(dāng)這個(gè)函數(shù)退出時(shí)铸董，就釋放它的存儲(chǔ)區(qū)粟害。則當(dāng)前運(yùn)行時(shí)的函數(shù)的數(shù)據(jù)區(qū)比在棧頂
一個(gè)遞歸函數(shù)的運(yùn)行過(guò)程類似多個(gè)函數(shù)嵌套調(diào)用悲幅；只是調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個(gè)函數(shù).因此，和每次調(diào)用相關(guān)的一個(gè)重要概念是遞歸函數(shù)運(yùn)行的“層次”汰具，假設(shè)調(diào)用該遞歸函數(shù)的主函數(shù)為第0層留荔，則從主函數(shù)調(diào)用遞歸函數(shù)進(jìn)入第1層，從第1層遞歸調(diào)用本函數(shù)為進(jìn)入下一層.即第i+1層.反正退出第1層遞歸應(yīng)返回上一層即第i-1層
為了保證遞歸函數(shù)正確執(zhí)行聚蝶，系統(tǒng)需要設(shè)立一個(gè)“遞歸工作椉燃裕“作為整個(gè)遞歸函數(shù)運(yùn)行期間使用的數(shù)據(jù)存儲(chǔ)區(qū).每一層遞歸所需信息構(gòu)成一個(gè)工作記錄，其中包括所有的實(shí)參句各，所有的局部變量以及上一層的返回地址晴叨。每進(jìn)入一層遞歸兼蕊，就產(chǎn)生一個(gè)新的工作記錄壓入棧頂.每退出一個(gè)遞歸孙技，就從棧頂彈出一個(gè)工作記錄牵啦，則當(dāng)前執(zhí)行層的工作記錄必須是遞歸工作棧棧頂?shù)墓ぷ饔涗浌Q為“活動(dòng)記錄”
