Reverse a stack using recursion
Difficulty: Easy
Asked in: Yahoo, Amazon, Adobe
Understanding The Problem
Problem Description
Given a stack of integers
st
, write a program to
reverse the stack using recursion
.
Problem Note

You are not allowed to use loop constructs like while, for, etc, Return
st
after reversing it using recursion. It is mandatory to reversest
using recursion.
Example 1
Input: st = [1, 5, 3, 2, 4]
Output:[4, 2, 3, 5, 1]
Explanation: After reversing the stack [1, 5, 3, 2, 4] becomes [4, 2, 3, 5, 1].
Example 2
Input: st = [5, 17, 100, 11]
Output: [11, 100, 17, 5]
Explanation: After reversing the stack [5, 17, 100, 11] becomes [11, 100, 17, 5]
Solution
The problem name itself addresses the solution to be a recursive solution. To understand what is a recursive solution, please refer here .
You must have known that a stack usually comprises two operations, i.e.
push
and
pop
operations on the top of the stack. So, If we have to reverse a stack, then we have to pop the elements of the stack and push it to another auxiliary stack one by one. In this way, the auxiliary stack will be the same stack in reverse order.
But we are not looking to use an auxiliary stack, but we can use recursion. And a recursive function behaves like a stack. So, What we are going to do that is we can create a recursive function and pop all stack items and stores the popped item in the function call stack. And when the input stack becomes empty, we push the new item stored in the call stack at the bottom of the input stack.
You can practice this problem here.
In short, we will take out the top element of the input stack and store it in the recursion stack until the stack becomes empty and while returning to the previous state of recursion, we push the stored element in each recursion stack at the bottom of the input stack.
Look at the below example:
Solution Steps

Create a recursive function
recur
to reverse the stack.  Pop the top element in each stack of recursion and hold the element in function call Stack until we reach the end of the stack
 While moving back in the recursion tree, push the held element of each recursion call stack at the bottom of the stack.
Pseudo Code
int insert_at_bottom(int x, stack st) {
if(st is empty) {
st.push(x)
}
else {
int a = st.top()
st.pop()
insert_at_bottom(x)
st.push(a)
}
}
void reverse(stack st) {
if(st is not empty) {
int st = st.top()
st.pop()
reverse(st)
insert_at_bottom(x, st)
}
}
// driver function
int[] reverseStack(int[] st) {
reverse(st)
return st
}
Complexity Analysis
Time Complexity: O(n²)
Space Complexity: O(n)
Critical Ideas To Think
 Why is the time complexity is O(n²)? Answer : For each element on top of the stack we are popping the whole stack out placing that top element at the bottom which takes O(n) operations. And this O(n) operations are performed for every value of the stack leaving a quadratic time complexity.
 How we are inserting the top element at the bottom of the stack? Answer : We pop each top element of the stack and store it in the call stack frame until the stack becomes empty. As soon as the stack becomes empty, we put the top element on the empty stack and then we push all the elements stored in the call stack frame while returning down the recursion tree.
 Take an example yourself and follow the above steps to test how the solution is working.
 Can you reverse a stack without recursion in linear time complexity? If yes, then what data structure will you use for the solution?
Suggested Problems To Solve
 Sort a stack using recursion
 Reverse a Doubly linked list using recursion
 Sort a stack using a temporary stack
 Infix to Postfix using different Precedence Values for InStack and OutStack
 Reverse a number using stack
 Reverse a stack without using extra space in linear time.
Please comment down below if you have a better insight in the above approach.
Happy Coding, Enjoy Algorithms!