递归（五）—— 初识暴力递归之“如何利用递归实现栈逆序”

题目：要求不使用额外的数据结构，仅利用递归函数实现栈的逆序。

题目分析：

利用实例来理解题意，栈内元素从栈底到栈顶一次是3，2，1 ，要求经过处理后，栈底到栈顶依次是1，2，3。

思路：

因为是用递归的逻辑去实现题目的要求，而递归之所以能够实现是因为利用了系统栈，在每一次递归函数的调用前都将“现场“保存在了系统栈中。

而我们实现题目要求，自然而然想到的逻辑就是在每次循环时都去拿栈底元素，直到栈为空时，结束从栈中取全素的操作，然后将取出的元素依次在放入栈中。例如，设：我们要操作的栈名为static_1，第一次拿到static_1的栈底元素是3 ，将它保存在系统栈中；

第二次拿到的static_1的栈底元素是2，将它保存在系统栈中；

第三次拿到的static_1的栈底元素是1，将它保存在系统栈中；

第四次，栈static_1已经空了，结束取元素操作，接下来将系统栈的元素存入栈中。

系统栈的栈顶是1，存入栈static_1中；

系统栈的栈顶是2，存入栈static_1中；

系统栈的栈顶是3，存入栈static_1中；

根据这个思路，我们写出代码：

//代码段1
#include <stack>
using std::stack;//将栈stack_1中元素逆序反转；
void reverse(stack<int>& stack_1){if(stack_1.empty()){ //如果栈为空，退出return;}else{int last= getLast(stack_1); //获取static_1中的栈底元素reverse(stack_1);stack_1.push(last)}
}

我们将系统栈画出，体会递归过程：

注：函数getLast 是用来实现获得栈底函数。

第一步：当首次调用reverse函数:

因为 stack_1.empty() == false，所以程序继续运行到 12行，为遇到函数调用，保存现场到系统栈：

第二步：第二次进入reverse(2), 因为 stack_1.empty() == false，程序运行到11行，得到last = 2，运行到12行时遇到递归函数调用，保存现场到系统栈。程序再次进入reverse(stack_1)

第三步：第三次进入reverse(3), 因为 stack_1.empty() == flase，程序运行到11行，得到last = 1，运行到12行时遇到递归函数调用，保存现场到系统栈。程序再次进入reverse(stack_1)

第四步：第四次进入reverse(4), 因为 stack_1.empty() == true，直接退出函数reverse(4)。

第五步，程序检查当前系统栈的情况，进入reverse(3),继续执行第13行代码 stack_1.push(last)，将last = 1写入stack_1,退出 reverse(3);

第六步：程序检查当前系统栈，进入reverse(2), 继续执行第13行代码，将last = 2写入stack_1;退出reverse(2);

第七步：程序检查当前系统栈，进入reverse(1),继续执行第13行代码，将last = 1写入stack_1, 退出reverse(1); 此时系统栈为空，程序执行完毕。

关键问题解决：

问题分析到这里，我们对如何利于系统栈实现给定栈结构stack_1中的元素逆序存储已经有了明确的实现思路，但是还有一个关键函数没有实现，即如何获得栈底元素，函数getLast 的函数体。

对于这个函数，规定的已知条件依然是不借助其他数据结构。在reverse函数中，getLast 函数是被看作一个黑盒函数来使用的，即每次调用都是返回的栈底元素，下面我们来分析它的内部逻辑。

因为最终的实现效果是：每执行一次getLast，栈底元素被取出（函数返回），栈内其它元素依次盖下来。如图：

代码实现

int getLast(stack<int>& stack_1){int last = stack_1.top();if(stack_1.empty()){return last;}else{int result = getLast(stack_1);stack_1.push(result);return result;}
}

代码分析 :

利用系统栈分析递归调用过程。

第一步：result= stack_1.top() == 1;

stack_1.empty() == false; 所以代码执行到第7行；保存现场到系统栈;

第二步：程序进入getLast(stack_1{2,3});

result = stack_1.top() == 2;

stack_1.empty() == false; 所以代码执行到第7行；保存现场到系统栈；

第三步：程序进入getLast(stack_2{3});

result = stack_1.top() == 3;

stack_1.empty() == true; 程序返回 3;

第四步：程序检查系统栈，进入getLast(stack_1{3}), 将返回值赋给last，即last = 3;

继续线下执行到8行，将result == 2 写入stack_1；程序执行到第9行，即返回值为3.

销毁函数getLast(stack_1{3})的调用过程:

第五步：程序检查系统栈，进入getLast(stack_1{2,3}), 将返回值赋给last，使last = 3，程序继续执行到第8行，将result= 1 写入stack_1, 执行第9行，函数返回last值，并且销毁getLast(stack_1{2,3})的调用过程。

此时：stack_1为：

函数返回值为3。

运行结果：

将代码补充完整，并验证。

#include <stack>
#include <iostream>void print(string str, stack<int> stack) {std::cout << str;while (stack.size()) {std::cout << stack.top() << " ";stack.pop();}std::cout << std::endl;
}//给你一个栈，请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数，如何实现
//栈底元素移除掉，上面的元素盖下来，返回移除的元素int getLast(stack<int>& s) {int result = s.top();s.pop();if (s.empty()) {return result;}else {int last = getLast(s);s.push(result);return last;}
}//如何利用递归实现栈逆序？
void reverse(stack<int>& stack) {if (stack.empty()) {return;}int i = getLast(stack);reverse(stack);stack.push(i);
}int main() {stack<int> stack_1;stack<int> stack_2;stack_1.push(3);stack_1.push(2);stack_1.push(1);stack_2.push(3);stack_2.push(2);stack_2.push(1);print("栈内原始值：", stack_2);auto fun = [](stack<int >& stack_1) {if (stack_1.size() == 0) return;reverse(stack_1);};fun(stack_1);print("执行了逆序后：", stack_1);return 0;
}

运行结果：