Reverse Stack Using Recursion

We will be using two recursive methods:

1. To Reverse the Stack: We will use recursion to iterate through the stack. For each top element, we will pop it and use recursion to reverse the remaining stack. After getting the stack reversed by recursion we can simply push the popped element to the bottom of the stack. The procedure to push the element at the bottom of stack is explained in following paragraph.
2. To Push an element to the Bottom of Stack: For this, we will be using recursion. Now to push a given element to the bottom of the stack, we will iterate through the stack recursively. For each top element, we will pop it and call recursion to insert a given element at the bottom of the remaining stack. After recursive function does its work and adds the given element to the bottom of stack, then we can simply push the popped element to the top of the stack.

Algorithm: 

1. ReverseStack(stack)
   1. If the stack is empty, then return
   2. Pop the top element from the stack as top
   3. Reverse the remaining elements in the stack, call reverseStack(stack) method
   4. Insert the top element to the bottom of the stack, call InsertAtBottom(stack, top) method
2. InsertAtBottom(stack, ele)
   1. If the stack is empty, push ele to stack, return
   2. Pop the top element from the stack as top
   3. Insert the ele to the bottom of the stack, call InsertAtBottom(stack, ele) method
   4. Push top to the stack.