How to Reverse a Stack using Recursion

Last Updated : 27 Dec, 2023

Write a program to reverse a stack using recursion, without using any loop.

Example:

Input: elements present in stack from top to bottom 1 2 3 4
Output: 4 3 2 1

Input: elements present in stack from top to bottom 1 2 3
Output: 3 2 1

Reverse a stack using Recursion

The idea of the solution is to hold all values in Function Call Stack until the stack becomes empty. When the stack becomes empty, insert all held items one by one at the bottom of the stack.

Illustration:

Below is the illustration of the above approach

Let given stack be

1

2

3

4



After all calls of reverse, 1 will be passed to function insert at bottom, after that 1 will pushed to the stack when stack is empty



1

Then 2 will be passed to function insert at bottom , it will check if the stack is empty or not if not then pop all the elements back and insert 2 and then push other elements back.

2

1

Then 3 will be passed to function insert at bottom , it will check if the stack is empty or not if not then pop all the elements back and insert 3 and then push other elements back.

3

2

1

Then 4 will be passed to function insert at bottom , it will check if the stack is empty or not if not then pop all the elements back and insert 4and then push other elements back.

4

3

2

1

Follow the steps mentioned below to implement the idea:

Create a stack and push all the elements in it.
Call reverse(), which will pop all the elements from the stack and pass the popped element to function insert_at_bottom()
Whenever insert_at_bottom() is called it will insert the passed element at the bottom of the stack.
Print the stack

Below is the implementation of the above approach:

C++

// C++ code to reverse a
// stack using recursion
#include <bits/stdc++.h>
using namespace std;
 
// Below is a recursive function
// that inserts an element
// at the bottom of a stack.
void insert_at_bottom(stack<int>& st, int x)
{
 
    if (st.size() == 0) {
        st.push(x);
    }
    else {
 
        // All items are held in Function Call
        // Stack until we reach end of the stack
        // When the stack becomes empty, the
        // st.size() becomes 0, the above if
        // part is executed and the item is
        // inserted at the bottom
 
        int a = st.top();
        st.pop();
        insert_at_bottom(st, x);
 
        // push allthe items held in
        // Function Call Stack
        // once the item is inserted
        // at the bottom
        st.push(a);
    }
}
 
// Below is the function that
// reverses the given stack using
// insert_at_bottom()
void reverse(stack<int>& st)
{
    if (st.size() > 0) {
 
        // Hold all items in Function
        // Call Stack until we
        // reach end of the stack
        int x = st.top();
        st.pop();
        reverse(st);
 
        // Insert all the items held
        // in Function Call Stack
        // one by one from the bottom
        // to top. Every item is
        // inserted at the bottom
        insert_at_bottom(st, x);
    }
    return;
}
 
// Driver Code
int main()
{
    stack<int> st, st2;
    // push elements into
    // the stack
    for (int i = 1; i <= 4; i++) {
        st.push(i);
    }
 
    st2 = st;
 
    cout << "Original Stack" << endl;
    // printing the stack after reversal
    while (!st2.empty()) {
        cout << st2.top() << " ";
        st2.pop();
    }
    cout<<endl;
   
    // function to reverse
    // the stack
    reverse(st);
    cout << "Reversed Stack" << endl;
    // printing the stack after reversal
    while (!st.empty()) {
        cout << st.top() << " ";
        st.pop();
    }
    return 0;
}

C

// C program to reverse a
// stack using recursion
#include <stdio.h>
#include <stdlib.h>
#define bool int
 
// structure of a stack node
struct sNode {
    char data;
    struct sNode* next;
};
 
// Function Prototypes
void push(struct sNode** top_ref, int new_data);
int pop(struct sNode** top_ref);
bool isEmpty(struct sNode* top);
void print(struct sNode* top);
 
// Below is a recursive function
// that inserts an element
// at the bottom of a stack.
void insertAtBottom(struct sNode** top_ref, int item)
{
    if (isEmpty(*top_ref))
        push(top_ref, item);
    else {
 
        // Hold all items in Function Call
        // Stack until we reach end of the
        // stack. When the stack becomes
        // empty, the isEmpty(*top_ref)becomes
        // true, the above if part is executed
        // and the item is inserted at the bottom
        int temp = pop(top_ref);
        insertAtBottom(top_ref, item);
 
        // Once the item is inserted
        // at the bottom, push all
        // the items held in Function
        // Call Stack
        push(top_ref, temp);
    }
}
 
// Below is the function that
// reverses the given stack using
// insertAtBottom()
void reverse(struct sNode** top_ref)
{
    if (!isEmpty(*top_ref)) {
        // Hold all items in Function
        // Call Stack until we
        // reach end of the stack
        int temp = pop(top_ref);
        reverse(top_ref);
 
        // Insert all the items (held in
        // Function Call Stack)
        // one by one from the bottom
        // to top. Every item is
        // inserted at the bottom
        insertAtBottom(top_ref, temp);
    }
}
 
// Driver Code
int main()
{
    struct sNode* s = NULL;
    push(&s, 4);
    push(&s, 3);
    push(&s, 2);
    push(&s, 1);
 
    printf("\n Original Stack ");
    print(s);
    reverse(&s);
    printf("\n Reversed Stack ");
    print(s);
    return 0;
}
 
// Function to check if
// the stack is empty
bool isEmpty(struct sNode* top)
{
    return (top == NULL) ? 1 : 0;
}
 
// Function to push an item to stack
void push(struct sNode** top_ref, int new_data)
{
 
    // allocate node
    struct sNode* new_node
        = (struct sNode*)malloc(sizeof(struct sNode));
 
    if (new_node == NULL) {
        printf("Stack overflow \n");
        exit(0);
    }
 
    // put in the data
    new_node->data = new_data;
 
    // link the old list
    // off the new node
    new_node->next = (*top_ref);
 
    // move the head to
    // point to the new node
    (*top_ref) = new_node;
}
 
// Function to pop an item from stack
int pop(struct sNode** top_ref)
{
    char res;
    struct sNode* top;
 
    // If stack is empty then error
    if (*top_ref == NULL) {
        printf("Stack overflow \n");
        exit(0);
    }
    else {
        top = *top_ref;
        res = top->data;
        *top_ref = top->next;
        free(top);
        return res;
    }
}
 
// Function to print a
// linked list
void print(struct sNode* top)
{
    printf("\n");
    while (top != NULL) {
        printf(" %d ", top->data);
        top = top->next;
    }
}

Java

// Java code to reverse a
// stack using recursion
import java.util.Stack;
 
class Test {
 
    // using Stack class for
    // stack implementation
    static Stack<Character> st = new Stack<>();
 
    // Below is a recursive function
    // that inserts an element
    // at the bottom of a stack.
    static void insert_at_bottom(char x)
    {
 
        if (st.isEmpty())
            st.push(x);
 
        else {
 
            // All items are held in Function
            // Call Stack until we reach end
            // of the stack. When the stack becomes
            // empty, the st.size() becomes 0, the
            // above if part is executed and
            // the item is inserted at the bottom
            char a = st.peek();
            st.pop();
            insert_at_bottom(x);
 
            // push allthe items held
            // in Function Call Stack
            // once the item is inserted
            // at the bottom
            st.push(a);
        }
    }
 
    // Below is the function that
    // reverses the given stack using
    // insert_at_bottom()
    static void reverse()
    {
        if (st.size() > 0) {
 
            // Hold all items in Function
            // Call Stack until we
            // reach end of the stack
            char x = st.peek();
            st.pop();
            reverse();
 
            // Insert all the items held
            // in Function Call Stack
            // one by one from the bottom
            // to top. Every item is
            // inserted at the bottom
            insert_at_bottom(x);
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        // push elements into
        // the stack
        st.push('1');
        st.push('2');
        st.push('3');
        st.push('4');
 
        System.out.println("Original Stack");
 
        System.out.println(st);
 
        // function to reverse
        // the stack
        reverse();
 
        System.out.println("Reversed Stack");
 
        System.out.println(st);
    }
}

Python3

# Python program to reverse a
# stack using recursion
 
# Below is a recursive function
# that inserts an element
# at the bottom of a stack.
 
 
def insertAtBottom(stack, item):
    if isEmpty(stack):
        push(stack, item)
    else:
        temp = pop(stack)
        insertAtBottom(stack, item)
        push(stack, temp)
 
# Below is the function that
# reverses the given stack
# using insertAtBottom()
 
 
def reverse(stack):
    if not isEmpty(stack):
        temp = pop(stack)
        reverse(stack)
        insertAtBottom(stack, temp)
 
# Below is a complete running
# program for testing above
# functions.
 
# Function to create a stack.
# It initializes size of stack
# as 0
 
 
def createStack():
    stack = []
    return stack
 
# Function to check if
# the stack is empty
 
 
def isEmpty(stack):
    return len(stack) == 0
 
# Function to push an
# item to stack
 
 
def push(stack, item):
    stack.append(item)
 
# Function to pop an
# item from stack
 
 
def pop(stack):
 
    # If stack is empty
    # then error
    if(isEmpty(stack)):
        print("Stack Underflow ")
        exit(1)
 
    return stack.pop()
 
# Function to print the stack
 
 
def prints(stack):
    for i in range(len(stack)-1, -1, -1):
        print(stack[i], end=' ')
    print()
 
# Driver Code
 
 
stack = createStack()
push(stack, str(4))
push(stack, str(3))
push(stack, str(2))
push(stack, str(1))
print("Original Stack ")
prints(stack)
 
reverse(stack)
 
print("Reversed Stack ")
prints(stack)
 
# This code is contributed by Sunny Karira

C#

// C# code to reverse a
// stack using recursion
using System;
using System.Collections;
 
public class GFG {
 
    // using Stack class for
    // stack implementation
    static Stack st = new Stack();
 
    // Below is a recursive function
    // that inserts an element
    // at the bottom of a stack.
    static void insert_at_bottom(char x)
    {
 
        if (st.Count == 0)
            st.Push(x);
 
        else {
 
            // All items are held in Function
            // Call Stack until we reach end
            // of the stack. When the stack becomes
            // empty, the st.size() becomes 0, the
            // above if part is executed and
            // the item is inserted at the bottom
            char a = (char)st.Peek();
            st.Pop();
            insert_at_bottom(x);
 
            // push all the items held
            // in Function Call Stack
            // once the item is inserted
            // at the bottom
            st.Push(a);
        }
    }
 
    // Below is the function that
    // reverses the given stack using
    // insert_at_bottom()
    static void reverse()
    {
        if (st.Count > 0) {
 
            // Hold all items in Function
            // Call Stack until we
            // reach end of the stack
            char x = (char)st.Peek();
            st.Pop();
            reverse();
 
            // Insert all the items held
            // in Function Call Stack
            // one by one from the bottom
            // to top. Every item is
            // inserted at the bottom
            insert_at_bottom(x);
        }
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
 
        // push elements into
        // the stack
        st.Push('1');
        st.Push('2');
        st.Push('3');
        st.Push('4');
 
        Console.WriteLine("Original Stack");
 
        foreach(char i in st) { Console.Write(i + ", "); }
 
        // function to reverse
        // the stack
        reverse();
 
        Console.WriteLine("\nReversed Stack");
        foreach(char i in st) { Console.Write(i + ", "); }
    }
}
 
// This code is Contributed by Arnab Kundu

Javascript

<script>
 
// JavaScript code to reverse a
// stack using recursion
 
// using Stack class for
// stack implementation
let st = [];
 
// Below is a recursive function
// that inserts an element
// at the bottom of a stack.
function insert_at_bottom(x)
{
    if(st.length==0)
        st.push(x);
    else
    {
        // All items are held in Function
            // Call Stack until we reach end
            // of the stack. When the stack becomes
            // empty, the st.size() becomes 0, the
            // above if part is executed and
            // the item is inserted at the bottom
            let a = st.pop();
            insert_at_bottom(x);
  
            // push allthe items held
            // in Function Call Stack
            // once the item is inserted
            // at the bottom
            st.push(a);
    }
     
     
}
 
// Below is the function that
    // reverses the given stack using
    // insert_at_bottom()
function reverse()
{
    if(st.length > 0)
        {
              
            // Hold all items in Function
            // Call Stack until we
            // reach end of the stack
            let x = st.pop();
            reverse();
              
            // Insert all the items held
            // in Function Call Stack
            // one by one from the bottom
            // to top. Every item is
            // inserted at the bottom
            insert_at_bottom(x);
        }
}
 
// Driver Code
 
// push elements into
// the stack
st.push('1');
st.push('2');
st.push('3');
st.push('4');
 
document.write("Original Stack<br>");
 
document.write(st.join(" ")+"<br>");
 
// function to reverse
// the stack
reverse();
 
document.write("Reversed Stack<br>");
 
document.write(st.join(" "));
 
 
// This code is contributed by avanitrachhadiya2155
 
</script>

Output

Original Stack
4 3 2 1 
Reversed Stack
1 2 3 4

Time Complexity: O(N²).
Auxiliary Space: O(N) use of Stack

GeeksforGeeks

Improve

Previous Article

Evaluation of Postfix Expression

Reverse individual words

Similar Reads

C Program to Reverse a Stack using Recursion

Write a program to reverse a stack using recursion, without using any loop. Example: Input: elements present in stack from top to bottom 1 2 3 4 Output: 4 3 2 1 Input: elements present in stack from top to bottom 1 2 3Output: 3 2 1 Recommended PracticeReverse a StackTry It!Reverse a stack using Recursion The idea of the solution is to hold all va

Why is Tail Recursion optimization faster than normal Recursion?

What is tail recursion? Tail recursion is defined as a recursive function in which the recursive call is the last statement that is executed by the function. So basically nothing is left to execute after the recursion call. What is non-tail recursion? Non-tail or head recursion is defined as a recursive function in which the recursive call is the f

Reverse a Doubly linked list using recursion

Given a doubly linked list. Reverse it using recursion. Original Doubly linked list Reversed Doubly linked list We have discussed Iterative solution to reverse a Doubly Linked List Algorithm: If list is empty, return Reverse head by swapping head->prev and head->next If prev = NULL it means that list is fully reversed. Else reverse(head->p

Print Fibonacci Series in reverse order using Recursion

Given an integer N, the task is to print the first N terms of the Fibonacci series in reverse order using Recursion. Examples: Input: N = 5Output: 3 2 1 1 0Explanation: First five terms are - 0 1 1 2 3. Input: N = 10Output: 34 21 13 8 5 3 2 1 1 0 Approach: The idea is to use recursion in a way that keeps calling the same function again till N is gr

C Program to reverse the digits of a number using recursion

Given an integer N, the task is to reverse the digits of given integer using recursion. Examples: Input: N = 123Output: 321Explanation:The reverse of the given number is 321. Input: N = 12532Output: 23521Explanation:The reverse of the given number is 23521. Approach: Follow the steps below to solve the problem: Recursively iterate every digit of N.

Print reverse of a string using recursion

Write a recursive function to print the reverse of a given string. Code: C/C++ Code // C++ program to reverse a string using recursion #include <bits/stdc++.h> using namespace std; /* Function to print reverse of the passed string */ void reverse(string str) { if(str.size() == 0) { return; } reverse(str.substr(1)); cout << str[0]; } /*

Reverse a linked list using recursion

Given pointer to the head node of a linked list, the task is to recursively reverse the linked list. We need to reverse the list by changing links between nodes. Examples: Input: Head: 1->2->3->4->NULLOutput: Reversed Linked list : 4->3->2->1->NULL Input: Head: 1->2->3->4->5->NULLOutput: Reversed Linked list

Find maximum and minimum element in binary tree without using recursion or stack or queue

Given a binary tree. The task is to find out the maximum and minimum element in a binary tree without using recursion or stack or queue i.e, space complexity should be O(1). Examples: Input : 12 / \ 13 10 / \ 14 15 / \ / \ 21 24 22 23 Output : Max element : 24 Min element : 10 Input : 12 / \ 19 82 / / \ 41 15 95 \ / / \ 2 21 7 16 Output : Max eleme

How to Sort a Stack using Recursion

Given a stack, the task is to sort it using recursion. Example: Input: elements present in stack from top to bottom -3 14 18 -5 30Output: 30 18 14 -3 -5Explanation: The given stack is sorted know 30 > 18 > 14 > -3 > -5 Input: elements present in stack from top to bottom 1 2 3Output: 3 2 1Explanation: The given stack is sorted know 3

Inorder Tree Traversal without recursion and without stack!

Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree. In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree. 1. Initialize current as root 2. While current

Article Tags :

Practice Tags :