之前遇到的一道題，突然想起來，發(fā)現(xiàn)不會(huì)做了，想了好久，終于又想出來了，記錄一下。

分析：遞歸的一個(gè)很厲害的作用就是能夠把大事化小，小事化了。就是一個(gè)金字塔，也能化成一個(gè)小三角。從這個(gè)方向出發(fā)去思考的話，事情就比較簡(jiǎn)單了，含n個(gè)元素的?？梢钥醋魇呛琻-1個(gè)元素的棧再push一個(gè)元素的結(jié)果。很容易想到把含n個(gè)元素的棧化為處理含n-1個(gè)元素的棧，最后再push第n個(gè)元素。依次遞歸，可以將?；癁榘?個(gè)元素的棧。此時(shí)，遞歸結(jié)束。再來分析第n個(gè)元素，這個(gè)元素最后要push到棧中，因此，這個(gè)元素必須得是棧底的元素。按照這個(gè)思路，必須有個(gè)函數(shù)取得棧底元素并刪除棧底元素，然后遞歸調(diào)用自己，將n-1個(gè)元素的棧逆序，最后再push之前獲得的棧底元素。最后，再實(shí)現(xiàn)這個(gè)取得棧底元素的函數(shù)，也需要用遞歸的方式。分析這個(gè)遞歸函數(shù)的參數(shù)：棧底元素可以通過返回值或者引用傳出來，另一個(gè)參數(shù)就是這個(gè)棧。函數(shù)實(shí)現(xiàn)就容易了：取得棧底元素的時(shí)候，只需要取得棧頂元素，pop棧頂元素，遞歸調(diào)用自己獲得棧底元素，push之前的棧頂元素。這個(gè)方法也是遞歸的經(jīng)典用法。取個(gè)名字吧，就叫做：縮小規(guī)模法。c++代碼如下：

縮小規(guī)模法：

int GetBottomValue(stack<int>& dataStack) { int bottomValue = 0; int topValue = 0; int size = dataStack.size(); topValue = dataStack.top(); dataStack.pop(); if (size == 1) { return topValue; } bottomValue = GetBottomValue(dataStack); dataStack.push(topValue); return bottomValue; } void ReverseStack(stack<int>& dataStack) { int bottomValue = GetBottomValue(dataStack); if (dataStack.size() != 0) { ReverseStack(dataStack); } dataStack.push(bottomValue); } void SinkTop(int depth, stack<int>& dataStack) { depth--; if (dataStack.size() < 2) { return; } int top = dataStack.top(); dataStack.pop(); int second = dataStack.top(); dataStack.pop(); dataStack.push(top); if (depth > 0) { SinkTop(depth, dataStack); } dataStack.push(second); } int main() { stack<int> dataStack; dataStack.push(1); dataStack.push(2); dataStack.push(3); dataStack.push(4); dataStack.push(5); //ReverseStack(dataStack); int size = dataStack.size(); for (int i = 1; i < size; i++) { SinkTop(size - i, dataStack); } for (int i = 0; i < size; i++) { cout << dataStack.top() << endl; dataStack.pop(); } system("pause"); }

還有一種方法：這種方法沒有站在遞歸的角度，只是站在解決問題的角度，只不過最后實(shí)現(xiàn)需要用遞歸而已。分析要逆序一個(gè)棧，肯定就需要把棧頂?shù)脑胤诺綏５?，做完這步之后，發(fā)現(xiàn)除了棧底元素之外，這個(gè)棧很像一個(gè)更小規(guī)模的需要逆序的棧，可以再對(duì)它進(jìn)行同樣的移動(dòng)棧頂元素到棧底的操作。依次遞歸，最后，就完成了棧的逆序，有點(diǎn)像冒泡排序，但是這里是棧頂元素下沉。并且不是下沉到棧底，而是下沉到指定的位置。下沉操作的實(shí)現(xiàn)也不難：可以用三個(gè)參數(shù)，一的個(gè)表示要下沉的棧頂元素值，一個(gè)表示下沉位置，一個(gè)表示棧本身。每次按照下沉位置，將棧頂元素push后，再把之前遞歸pop的元素出棧，依次遞歸就好了。也可以用兩個(gè)參數(shù)實(shí)現(xiàn)遞歸函數(shù)，一個(gè)表示下沉深度，一個(gè)表示棧本身。遞歸交換棧頂?shù)膬蓚€(gè)元素，直到遞歸深度為0，每次遞歸下沉一個(gè)元素，總共需要n-1此遞歸。

用兩個(gè)參數(shù)的c++實(shí)現(xiàn)如下：

void SinkTop(int depth, stack<int>& dataStack)

{

depth--;

if (dataStack.size() < 2)

{

return;

}

int top = dataStack.top();

dataStack.pop();

int second = dataStack.top();

dataStack.pop();

dataStack.push(top);

if (depth > 0)

{

SinkTop(depth, dataStack);

}

dataStack.push(second);

}

int main()

{

stack<int> dataStack;

dataStack.push(1);

dataStack.push(2);

dataStack.push(3);

dataStack.push(4);

dataStack.push(5);

int size = dataStack.size();

for (int i = 1; i < size; i++)

{

SinkTop(size - i, dataStack);

}

for (int i = 0; i < size; i++)

{

cout << dataStack.top() << endl;

dataStack.pop();

}

system("pause");

}