碎碎念

---

在大一學(xué)習(xí)C語言的時候，舉過一個用棧實現(xiàn)的括號匹配算法，當(dāng)時覺得很難，不過現(xiàn)在回顧起來，這個算法也算是比較簡單的一個關(guān)于棧的應(yīng)用了。而現(xiàn)在所常見的算法問題也都是什么中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式，雙棧找最小值之類的。難度比之括號匹配稍有提升，不過倒也算是必須要掌握的算法。

上述所說的表達(dá)式求值在程序設(shè)計語言中是一個最基本的問題，也是棧的實現(xiàn)的一個典型范例。

為什么說是最基本？ 我們知道，中綴表達(dá)式對于人來說是比較友好的，學(xué)過四則運算就可以對其求值，然而對于計算機(jī)來說，雖然也可以想辦法計算，但是卻算不上友好了；相反，后綴表達(dá)式雖然對人不友好，但是卻是計算機(jī)所喜歡的。

（話說，后綴表達(dá)式在編譯原理中的重要性也是能棲身前列的。）

棧

---

在C語言入門的時候，我們就會通過遞歸來求斐波那契數(shù)列，很簡單：

int fibonacci(int n) {if (n==0 || n==1) return 1;return fibonacci(n-1) + fibonacci(n-2); } 復(fù)制代碼

但是那時候還不懂原理，僅僅知道，遞歸就是函數(shù)調(diào)用其本身，但是接觸到數(shù)據(jù)結(jié)構(gòu)的時候，再一次提出了遞歸的概念。

什么是遞歸？遞歸就是函數(shù)調(diào)用其本身。

reverse(know) { // 1. go onif (you know) return you know; // 2. look 4else back to see the 1; // 3. go back to 1. } // 4. you know what is recurision now. 復(fù)制代碼

這時候，我們不僅知道遞歸真正的用法，同時也知道了一個事實，即遞歸程序的開銷通常很大，但與之相反的，其代碼量又是非常少的。

通常情況下，我們會選擇將遞歸程序改寫成非遞歸程序，即所謂消除遞歸，但是當(dāng)改寫后和改寫前的程序并不會有太大的性能提升，我們也沒有必要去改寫，比如：cout << fibonacci(5); ，為了這樣的調(diào)用去消除遞歸，有必要嗎？

可實際情況是，一個應(yīng)用所要處理的數(shù)據(jù)并不算小，消除遞歸是不可避免的。

遞歸的精髓在于能否將原始的問題轉(zhuǎn)換為屬性相同，但問題規(guī)模較小的問題，學(xué)過算法就知道，這同樣也是貪心策略和動態(tài)規(guī)劃的本質(zhì)。

優(yōu)化

對于遞歸程序的優(yōu)化，我們通常會選擇棧做輔助，為什么？我們知道，在操作系統(tǒng)中，有一種叫做**“函數(shù)調(diào)用堆棧”**的名詞，大概的解釋就是：當(dāng)在某一函數(shù)A中調(diào)用另一函數(shù)B時，我們將A中的內(nèi)容保存后，壓入系統(tǒng)堆棧（你可以說這是在創(chuàng)建還原點，也可以說這個是現(xiàn)場保護(hù)，開心就好。），然后執(zhí)行函數(shù)B的內(nèi)容，當(dāng)函數(shù)B執(zhí)行結(jié)束后，將A從系統(tǒng)堆棧中彈出，繼續(xù)從斷點處執(zhí)行，同時銷毀之前申請的棧空間。

同時，我們要知道，操作系統(tǒng)的主存是由空間上限的，不可能是無限的。系統(tǒng)堆棧的大小自然是受操作系統(tǒng)存儲空間大小的約束的，而且絕對小于系統(tǒng)存儲空間（不可能等于）。所以，當(dāng)遞歸程序不斷申請棧空間到達(dá)系統(tǒng)棧所能分配的上限時，就有了所謂的“系統(tǒng)堆棧溢出”，即我們通常所說的“爆棧”。

• 斐波那契函數(shù)n=6時，遞歸調(diào)用樹

• n=3時，棧的申請情況

• n=6時，棧的申請情況

java中，異常java.lang.StackOverflowError就是一種堆棧溢出錯誤，不過，可以通過修改JVM參數(shù)來增大虛擬機(jī)棧空間，如-vm args-Xss128k；但這也只是權(quán)宜之計，治標(biāo)不治本吶。

但是呢，一個遞歸程序并不一定非要用棧輔助改寫成非遞歸程序（即消除遞歸），有時候，一個循環(huán)就夠了。

int main() {int n, i=j=1, tmp=0;cin >> n;while (n--) {tmp = i+j;i = j;j = tmp;} } 復(fù)制代碼

暫時就說這么多，至于后面的，那就后面再說吧，畢竟這也只是（一）嘛。

總結(jié)

以上是生活随笔為你收集整理的数据结构碎碎念（一）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。