一个栈依次压入1、2、3、4、5，那么从栈顶到栈底分别是5、4、3、2、1。要求只用递归，不借助其他数据结构，实现栈的逆序，即从栈顶到栈底变为1、2、3、4、5。

解题思路

对于递归操作，通常都是由极端情况推广到一般情况。

• 如果没有元素，或者只有一个元素，那么直接返回即可。
• 如果栈内有多个元素，则考虑可以先获取并移除栈底元素，然后把其余元素逆序，再把栈底元素push到栈顶，即实现了整个栈的逆序。

对于"获取并移除栈底元素"，我们同样用以递归来实现：

• 如果栈内只有一个元素，那么直接执行pop操作接口。
• 如果栈内有两个元素，假设入栈顺序为1、2，那么我们需要先把栈顶的2弹出来，再把1弹出来，然后再把2压入。
• 推广到一般情况，如果栈内有多个元素，我们可以先把栈顶元素弹出，然后从栈中"获取并移除栈底元素"，然后再把栈顶元素压入。（从整个操作来看，除了栈底元素没有被重新压入外，其余元素在更深层次的递归返回后都重新做了压入操作）

实现代码

public class ReverseStack {
    public static void reverse(Stack<Integer> stack) {
        if (stack.empty()) {
            return;
        }

        int bottom = getAndRemoveBottomElement(stack);
        reverse(stack);
        stack.push(bottom);
    }

    public static int getAndRemoveBottomElement(Stack<Integer> stack) {
        int result = stack.pop();
        if (stack.empty()) {
            return result;
        } else {
            int bottom = getAndRemoveBottomElement(stack);
            stack.push(result);
            return bottom;
        }
    }
}