272. Reverse a Stack Using Recursion

Given a stack of n integers (given as space-separated values from bottom to top), reverse the entire stack using only recursive stack operations (push/pop/peek/isEmpty, no other data structure - not even an explicit loop-based auxiliary stack). Print the resulting reversed stack's values from bottom to top.

Input: The input is a single line of space-separated integers, the stack's values listed from bottom to top. Output: Print the reversed stack's values, space-separated, from bottom to top, on one line.

1 <= n <= 10^4

This problem directly builds on 'Insert an Element at the Bottom of a Stack' as a necessary sub-routine - recognizing and reusing that exact helper function is the key to solving this one cleanly.

Reverse an entire stack's order, using only recursive stack operations - no explicit second stack or array allowed. Brute force: Copy the stack's elements into an array, reverse the array, and rebuild the stack - this works but uses an explicit array, which the problem specifically disallows. Optimised: Combining TWO recursive techniques - 'pop everything, recurse, then reinsert' for the overall reversal, and 'insert at bottom' as the helper for placing each popped element correctly - achieves the full reversal using only the call stack as implicit extra storage, with no explicit auxiliary structure.

Use two mutually recursive functions that touch nothing but the original stack and the call stack: reverseStack(S) pops the top element, recursively reverses whatever remains of S, then calls insertAtBottom to slide the popped element all the way down to the new bottom; insertAtBottom works by popping S's top, recursively inserting the target element at the bottom of what remains, then pushing the popped element back on top. Because both functions use only push/pop/peek/isEmpty plus recursion (the call stack standing in for any "extra" storage), this satisfies the problem's constraint, at the cost of insertAtBottom re-walking up to n elements for each of the n elements reversed. Time: O(n^2) Space: O(n)

Instead of an array, pop every element off the original stack directly onto a second explicit stack. Because the element popped last from the original (its bottom) is pushed last onto the auxiliary stack (ending up on top), the auxiliary stack's top-to-bottom order already equals the original's bottom-to-top order reversed, so no separate reversal pass is needed - though this still relies on an extra stack, which the strict "recursion only, no other data structure" rule of this problem disallows. Time: O(n) Space: O(n)

Pop every element off the original stack into a plain array, which naturally records them from top to bottom, then push the array's elements back onto the stack in that same order. The first value pushed back (the original top) ends up at the new bottom, and the last value pushed back (the original bottom) ends up at the new top, so the stack comes out fully reversed - but this relies on an explicit auxiliary array, which the problem's recursion-only constraint forbids. Time: O(n) Space: O(n)

1. Recursively pop the TOP element off, and recursively reverse whatever remains of the stack. 2. Once the REST of the stack is fully reversed, insert the originally-popped top element at the very BOTTOM of that now-reversed stack (using the 'insert at bottom' helper technique). 3. Unwinding this recursion fully reverses the entire original stack.

Time: O(n²) - reversing requires n total 'insert at bottom' operations, and each insert-at-bottom operation itself costs O(current stack size), summing to O(n²) overall. Space: O(n) for the recursion call stack at the deepest point.

n = 1 (a single-element stack, unchanged by reversal); n = 10^4, the upper bound, given that only recursive stack operations (no auxiliary stack) are allowed.

Be ready to explain the O(n²) time cost honestly - this is genuinely less efficient than a simple explicit-auxiliary-stack reversal (which would be O(n)), but the recursive-only constraint is exactly what makes this problem interesting and forces the tradeoff.