Reverse Stack Using Recursion
Reverse a given stack of integers using recursion.

Note:

You are not allowed to use any extra space other than the internal stack space used due to recursion. You are not allowed to use the loop constructs of any sort available as handy. For example: for, for-each, while, etc. The only inbuilt stack methods allowed are: push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element.

Input Format :

The first line of input contains an integer value N, denoting the size of the input Stack. The second line contains N single space-separated integers, denoting the stack elements, where the last (Nth) element is the TOP most element of Stack.

Constraints :

0

Question

Reverse Stack Using Recursion

Reverse a given stack of integers using recursion.

Note:

You are not allowed to use any extra space other than the internal stack space used due to recursion.
You are not allowed to use the loop constructs of any sort available as handy. For example: for, for-each, while, etc. 
The only inbuilt stack methods allowed are:
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.

Input Format :

The first line of input contains an integer value N, denoting the size of the input Stack.

The second line contains N single space-separated integers, denoting the stack elements, where the last (Nth) element is the TOP most element of Stack.

Constraints :

0 <= N <= 10^3

Where 'N' is the number of elements in the given stack.

Time Limit: 1 sec

Output Format :

N single space-separated integers in a single line, where the first integer denotes the TOP element of the reversed stack.

Sample Input 1 :

3
2 1 3

Sample Output 1 :

2 1 3

Explanation to Sample Input 1 :

First-line contains an integer 3 denotes the size of the input stack i.e N = 3.
Second-line contains 3 single space-separated integers i.e the elements of the stack.

alt text

Printing the reverse stack starting from the top element: 2 1 3.

Sample Input 2 :

2
3 2

Sample Output 2 :

3 2

Accepted Answer

Recursive Approach

We will be using two recursive methods:

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.
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:

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
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.

Space Complexity: O(n)Explanation:

O(N), where N is the total number of elements in the given stack.

In the worst case, the depth of recursion can extend up to O(N). So, extra space will be required for the recursion stack.

Time Complexity: O(n^2)Explanation:

O(N^2), where N is the total number of elements in the given stack.

In the worst case, reverseStack method will be called for each element in the stack( requires O(N)) time, and for each call of the reverse stack, we call InsertAtBottom which also takes O(N) time.