Reverse a Stack Recursively Without Extra Data Structure

Problem Statement

Reverse a stack using only recursion. You cannot use any external data structure (no extra stack, array, or queue). You may only use the stack's push, pop, top, and isEmpty operations.

Constraints

• 1 <= stack size <= 10^4
• Only standard stack operations allowed
• No extra data structure
• O(n²) time is acceptable, O(n) auxiliary space via recursion stack is fine

Example

Input stack (top to bottom): [5, 4, 3, 2, 1]

Output stack (top to bottom): [1, 2, 3, 4, 5]

What the Interviewer Expects

1. Two recursive functions:
   • reverse(stack) — pops each element, recurses, then inserts at bottom
   • insertAtBottom(stack, item) — helper that pops all, places item at bottom, pushes all back
2. Understand the recursion tree — each element gets temporarily held in the call stack
3. Time complexity: O(n²) — for each of n elements, insertAtBottom does O(n) work
4. Space complexity: O(n) — recursion depth

Follow-ups

1. Can you sort a stack using only recursion and no extra data structure? (Similar pattern)
2. What's the maximum recursion depth? Could this cause a stack overflow for large inputs?
3. How would you do this iteratively if you're NOT allowed recursion?
4. What if you have access to a size() function — does that help optimize anything?