一、函數(shù)棧
函數(shù)的調(diào)用過程其實就是一個壓棧的過程，在函數(shù)棧中，每個函數(shù)所占空間成為一個 棧幀。棧幀中保存著函數(shù)的形參，返回地址，局部變量，EBP等信息。一個棧幀可以理解為棧的一個元素，函數(shù)調(diào)用過程是壓棧的過程，函數(shù)返回則可以簡單理解為彈棧的過程。
二、函數(shù)棧與遞歸
棧是一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，函數(shù)棧同理。不同的是，棧里面存儲的是相同類型的數(shù)據(jù)，且數(shù)據(jù)之間相互獨立，函數(shù)棧每一個棧幀空間內(nèi)可以存儲不同類型的數(shù)據(jù)，數(shù)據(jù)之間可以關(guān)聯(lián)。遞歸的過程就是將相同的函數(shù)不斷壓棧的過程，它們一般操作這同一個數(shù)據(jù)結(jié)構(gòu)，到達(dá)某一特定條件后返回（系統(tǒng)?？臻g由操作系統(tǒng)分配，不可能無限大，所以遞歸調(diào)用容易造成棧溢出）。
三、遞歸實現(xiàn)棧反轉(zhuǎn)
申請額外的數(shù)據(jù)結(jié)構(gòu)可以很輕松地實現(xiàn)棧反轉(zhuǎn)，但是函數(shù)棧本身也是一個棧，也可以當(dāng)做一個數(shù)據(jù)結(jié)構(gòu)來使用。
給定一個棧，要求不申請其他數(shù)據(jù)結(jié)構(gòu)，實現(xiàn)棧的反轉(zhuǎn)。
如給定棧[1, 2, 3] （棧頂?shù)綏５祝?/p>
返回[3, 2, 1]
這個問題需要兩個函數(shù)輔助完成，第一個函數(shù)得到棧底元素并返回：
int get(stack<int> &s)
{
int result = s.top();
s.pop();
if (s.empty()) {
return result;
} else {
int last = get(s);
s.push(result);
return last;
}
}
以棧 [1, 2, 3] 為例分析此函數(shù)遞歸過程：
- 遞歸第一層， 得到棧頂元素
1并保存在result中。 - 遞歸第二層，得到棧頂元素
2并保存在result中。 - 遞歸第三層，得到棧頂元素
3并保存到result中。此時棧s為空，函數(shù)將result返回。 - 函數(shù)返回第二層，將第三層返回的
result保存到last中，并將第二層的result（值為2）壓回棧s中，返回last 。 - 函數(shù)返回第一層，將第二層返回的
last保存到第一層的last中，并將第一層的result（值為1）壓棧，最后返回last。
第二個函數(shù)將get()函數(shù)的返回值壓棧，最后取出的值最先壓棧，按照get()函數(shù)的規(guī)則，最后取出的值為1，所以1最先壓棧，3最后壓棧。
void reserve(stack<int> &s)
{
if (s.empty()) return;
int i = get(s);
reserve(s);
s.push(i);
}
以棧 [1, 2, 3] 為例分析此函數(shù)遞歸過程：
- 遞歸第一層，調(diào)用get函數(shù)得到棧底元素
3，保存到i中。 - 遞歸第二層，調(diào)用get函數(shù)得到棧底元素
2，保存到i中。 - 遞歸第三層，調(diào)用get函數(shù)得到棧底元素
1，保存到i中。 - 遞歸第四層，棧
s為空，直接返回。 - 函數(shù)返回第三層，將元素
1壓棧。 - 函數(shù)返回第二層，將元素
2壓棧。 - 函數(shù)返回第一層，將元素
3壓棧。
由遞歸過程看出，棧[1, 2, 3] （棧頂?shù)綏５祝┮呀?jīng)被反轉(zhuǎn)為[3, 2, 1] （棧頂?shù)綏５祝?/p>
這個方法的巧妙之處在于，利用函數(shù)棧來存儲棧s中彈出的數(shù)據(jù)，從而避免了申請額外的數(shù)據(jù)結(jié)構(gòu)。函數(shù)棧本身也是一種可利用的“數(shù)據(jù)結(jié)構(gòu)”。這就好理解為什么可以用遞歸解決的問題都可以用迭代來解決了。
盡管如此，還是應(yīng)該盡量少用遞歸解決問題，因為每一次函數(shù)調(diào)用都需要申請額外的棧幀空間，這會造成不小的系統(tǒng)開銷。雖然函數(shù)棧也是可利用的數(shù)據(jù)結(jié)構(gòu)，但是棧幀里面畢竟存儲了太多函數(shù)執(zhí)行過程中需要的信息，如返回地址，EBP等。對空間也是一種浪費。
