Stack • Recursion

Reverse a Stack

Reverse a stack using ONLY recursion. You are not allowed to use any loops or auxiliary data structures (like another stack or queue).

Try Interactive Simulator

The Call Stack

Since we can't use an external array or stack, we use the System Call Stack! We recursively pop elements until the stack is empty, storing the popped values in local variables (`temp`) at each recursive level.

Reverse()

The `reverse()` function empties the entire stack. On its way back up (as the recursion unwinds), it takes the element it popped and asks `insertAtBottom` to put it at the very bottom.

InsertAtBottom()

Because the top is blocked by other elements, this function recursively pops everything out of the way, pushes the desired element at the absolute bottom, and then puts everything back on top.

Data Stack

1

2

3

Call Stack

Code Tracker

:::

1function reverse(stack) {

2 if (stack.length === 0) return;

3 let temp = stack.pop();

4 reverse(stack);

5 insertAtBottom(stack, temp);

6}

7function insertAtBottom(stack, val) {

8 if (stack.length === 0) {

9 stack.push(val); return;

10 }

11 let temp = stack.pop();

12 insertAtBottom(stack, val);

13 stack.push(temp);

14}

Reverse Stack

Reverse Stack

Reverse a Stack

The Call Stack

Reverse()

InsertAtBottom()

Reverse a Stack

The Call Stack

Reverse()

InsertAtBottom()