DSA interview question

Reverse a Stack Using Recursion

Medium · Data structures · Topics: recursion, stack

The problem

A document editor keeps its undo history in a stack, and a new "replay from the start" feature needs the same stack reversed, so the oldest action is on top. The rule is: no loops and no extra container, only push, pop, top and recursion. The trick uses two recursions. The first pops every element; as the calls unwind, each popped element is inserted at the bottom by a second recursion that pops everything above, pushes the element, and pushes everything back.

Example (bottom → top): [3, 2, 1, 7, 6] → [6, 7, 1, 2, 3].

Function signature

void reverseStack(stack<int>& s);

Test cases

Input (bottom → top)	Output (bottom → top)	Explanation
`[3, 2, 1, 7, 6]`	`[6, 7, 1, 2, 3]`
`[4, 3, 9, 6]`	`[6, 9, 3, 4]`
`[1, 2]`	`[2, 1]`
`[1]`	`[1]`
`[]`	`[]`

(Confirm: only stack operations and recursion are allowed; no loops, no second stack, no array.)

How interviewers phrase it

"Reverse a stack using recursion, without loops or any other data structure" (GeeksforGeeks).

Clarifying questions to ask

Are loops forbidden entirely? (Usually yes, which is the point.)
Is the recursion stack acceptable as hidden storage? (Yes.)
What's the maximum size? (The recursion depth is O(n).)

Follow-ups to expect

"What does insertAtBottom do?"
"Why does inserting at the bottom reverse the stack?"
"Complexity?"
"How does this relate to sorting a stack?"
"With a second stack allowed?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview