思路

使用递归的方法去逆序一个栈，主要分为两步：

1. 使用递归的方法找到栈 栈底 的元素，并返回

2. 使用递归的方式，将元素进行逆置操作，涉及到逆序：要先递归，再操作

1. 递归寻找栈底的元素

• 递归函数有返回值，因此函数可以逐层返回需要的值return getAndRemoveLastElem(stack)

• 递归的结束条件： 当栈为空的时候，结束递归，并返回上一个值，此时的处理是：先将值取出，在判断栈的情况

• 递归的操作顺序，由于是找 栈底 的元素，因此是递归先序的方式; 递归结束之后，再将原来的元素放回

code:

public static <E> E getAndRemoveLastElem(Stack<E> stack){
  // 查找最后一个元素
  E elem = stack.pop();
  // 最后一个，返回结果
  if (stack.empty()) {
    return elem;
  } else {
    // 如果不是最后一个，则继续寻找，并把刚刚取出的元素放回
    E last = getAndRemoveLastElem(stack);
    stack.push(elem);
    return last;
  }
}

2. 递归向栈中加入元素

• 首先查找元素，找到元素之后再看递归的操作

• 递归函数的返回值： 由于只是对栈进行操作，无返回值

• 递归函数的结束条件： 这个结束的条件比较难想，由于是向栈中添加元素，栈满了才结束，但是这个不是递归结束的条件；如何确定呢？在栈中添加元素之前，是将栈低的元素取出来，取完了就该向栈中添元素了，此时为栈递归的结束条件

• 递归的操作顺序，只有本地的栈空了才能向其中添加元素，所以先递归的查找栈低的元素，之后再向栈中添加元素，形成一个 对称的U型结构

code:

    public static <E> void reverseStack(Stack<E> stack) {
        // 递归结束的条件
        if (stack.empty()) {
            return ;
        } else {
            // 先找到最后的元素，递归再去寻找， 最后找不到了， 从最后开始push到stack中
            E last = getAndRemoveLastElem(stack);
            // 倒序插入的时候， 先递归，再操作
            reverseStack(stack);
            stack.push(last);
        }

    }