Reverse a stack using recursion

Problem Statement

Reverse a stack using recursion. You are not allowed to use any additional data structure (like another stack, array, etc.). You can only use the stack itself and recursion.

Example:

Approach: Using Two Recursive Functions

Intuition

We need two recursive operations:

1. Main recursion: Pop each element, reverse remaining stack, insert popped element at bottom
2. Helper function: Insert an element at the bottom of the stack

The key insight is that reversing = moving each element from top to bottom in reverse order.

Algorithm

1. Pop the top element
2. Recursively reverse the remaining stack
3. Insert the popped element at the bottom
4. Base case: stack with 0 or 1 element is already reversed

import java.util.*;

public class ReverseStack {
    // Helper function to insert element at bottom
    public static void insertAtBottom(Stack<Integer> stack, int x) {
        if (stack.isEmpty()) {
            stack.push(x);
            return;
        }
        
        int top = stack.pop();
        insertAtBottom(stack, x);
        stack.push(top);
    }
    
    // Main function to reverse stack
    public static void reverseStack(Stack<Integer> stack) {
        // Base case: empty or single element stack
        if (stack.isEmpty()) {
            return;
        }
        
        // Pop the top element
        int top = stack.pop();
        
        // Reverse the remaining stack
        reverseStack(stack);
        
        // Insert the popped element at bottom
        insertAtBottom(stack, top);
    }
    
    public static void printStack(Stack<Integer> stack) {
        System.out.println("Stack (bottom to top): " + stack);
    }
    
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        
        System.out.println("Before reversal:");
        printStack(stack);
        
        reverseStack(stack);
        
        System.out.println("After reversal:");
        printStack(stack);
    }
}

Complexity Analysis

• Time Complexity: O(n^2)
  • reverseStack is called n times
  • Each call to insertAtBottom takes O(n) time
  • Total: O(n) * O(n) = O(n^2)
• Space Complexity: O(n) - recursion stack depth

Detailed Trace

Let's trace through: Stack = [1, 2, 3] (3 is top)

Alternative: Using Single Recursive Function

We can combine both operations, but it's less readable:

Note: This violates the "no additional data structure" constraint. The two-function approach is the correct solution.

Key Takeaways

1. Two recursive functions work together:
   • reverseStack: coordinates the reversal
   • insertAtBottom: places elements in correct position
2. Each element gets moved from top to bottom
3. Time complexity is O(n^2) due to nested recursion
4. The call stack acts as the implicit storage
5. This pattern (pop all → process → push all) appears in many stack problems
6. Understanding the recursion tree helps visualize the solution