DSA sheet · Recursion · Recursion on a stack

Reverse a Stack Using Recursion

After linear, non-linear and divide-and-conquer recursion, the teacher uses recursion to change a data structure in place. The task: reverse a stack without using a second stack. The trick is that recursion already has a hidden stack, the call stack, and we can park our elements there. It needs two recursive functions working together: one to empty the stack, one to insert an element at the bottom. She says getting comfortable with this "do something, recurse, undo on the way back" shape makes backtracking and DP much easier later. (Reversing a linked list with recursion belongs to the same topic, but she leaves it for the linked-list section.)

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Recursion and stacks from scratch
• Part A · The two iterative ways (and why they're not allowed)
• Part B · Reverse a stack with recursion
• Part C · Revision page

Part 0 · Recursion and stacks from scratch

What is a stack?

A stack is a pile: you can only add on top (push) and remove from the top (pop). The last thing pushed is the first thing popped (LIFO: Last In, First Out). The opposite end is the bottom. You can't reach the bottom directly.

In Python we use a list as a stack: st.append(x) pushes, st.pop() pops the top, st[-1] peeks at the top, and not st means "empty". The list is written bottom → top, left to right. That's also how the problem gives the input: [1, 2, 3, 4] means 1 at the bottom and 4 on top.

  [1, 2, 3, 4]       top →  | 4 |
                            | 3 |
                            | 2 |
                   bottom → | 1 |
                            +---+

A function that calls itself

Recursion = a function solves a problem by calling itself on a smaller version of it. Here, "smaller" means a stack with one element fewer.

Base case: why it must exist

The base case is the input where we stop calling: here, an empty stack. If we kept popping and calling without checking, we'd eventually call pop() on an empty list (IndexError). In other problems a missing base case means endless calls, which Python stops after about 1000 waiting calls with RecursionError.

Recursive case and the leap of faith

The recursive case handles one element and lets the recursive call handle the rest. Trust that the call on the smaller stack does its job completely (the "leap of faith"), then do your small piece of work.

The call stack: push on call, pop on return

Every call gets a frame holding its own local variables. A call pushes its frame onto Python's call stack. A return pops it, and control goes back to the frame below, which continues from where it paused. Each frame keeps its own copy of local variables like top or temp. That's the "hidden storage" this whole problem relies on.

Work on the way down vs. on the way back up

• Code before the recursive call runs on the way down: here, popping elements off.
• Code after the recursive call runs on the way back up: here, putting elements back (in a new order).

Python note: the stack is shared, not copied

When we pass st to a function, Python passes a reference to the same list, not a copy. So when one function pops or pushes, every other frame sees the change. The teacher stresses this: a later frame looks at "the stack" and finds it already changed by an inner call. That's what we want.

Python note: recursion depth

This solution keeps up to about n + 1 frames waiting at once (some reverse frames plus some insert_at_bottom frames, see the dry run). Python's default limit is about 1000, so for stacks with more than a few hundred elements, raise it first to be safe: import sys; sys.setrecursionlimit(10**5).

Part A · The two iterative ways (and why they're not allowed)

1The question in simple words

You're given a stack. Reverse it, so the element at the bottom ends up on top and the top ends up at the bottom.

  before (bottom→top): [1, 2, 3, 4]      after: [4, 3, 2, 1]

2What the constraints tell us

• The teacher doesn't discuss number limits in this video. The real constraint is the rule: use only this one stack, no second stack, and no reaching into the middle like an array.
• The empty stack and a one-element stack are already "reversed". Our code must handle them without crashing.

3Intuition: what you'd do without the rule

She first lists the two easy ways, to show why recursion is needed.

4Way 1: left and right pointers (treat it as an array)

Put one pointer on the first element and one on the last. Swap them, move both pointers inward, and repeat until they meet. For [1,2,3,4]: swap 1↔4 → [4,2,3,1], then 2↔3 → [4,3,2,1].

def reverse_two_pointers(st):
    left, right = 0, len(st) - 1
    while left < right:
        st[left], st[right] = st[right], st[left]   # swap the ends
        left += 1
        right -= 1

5Way 2: a second stack

Pop every element of st and push it onto a new stack st1. Popping gives 4, 3, 2, 1, so st1 becomes [4, 3, 2, 1]: reversed. It works, but it uses an extra stack, and the question forbids that.

def reverse_extra_stack(st):
    st1 = []
    while st:
        st1.append(st.pop())   # 4, then 3, then 2, then 1
    st[:] = st1                # make the original list hold the reversed order

st[:] = st1 copies st1's contents into the same list object, so the caller sees the change. It's a Python list trick, just to make the function's result match the others.

6The real question

"Can we reverse it using the same single stack?" Yes, with recursion, because recursion brings its own internal stack (the call stack) where we can keep elements for free.

Part B · Reverse a stack with recursion

GFG: Reverse a Stack

1The question in simple words

Write reverse(st) that changes the given list in place so that, read bottom → top, it's in the opposite order. You may only use push, pop, "is empty", and recursion.

2What the constraints tell us

• No second stack → the only other storage we may use is the call stack (one local variable per frame).
• Recursion depth grows with n (up to about n + 1 frames) → raise Python's recursion limit for large n (see Part 0).

3Intuition: empty it into the call stack, then rebuild it upside down

Step 1, empty it. Pop the top into a local variable top and call reverse again on the rest. Each frame holds one element: frame 1 holds 4, frame 2 holds 3, frame 3 holds 2, frame 4 holds 1. Now the real stack is empty, and all the elements are waiting inside the frames.

Step 2, put them back, but each one at the BOTTOM. Frames return in reverse order: the frame holding 1 finishes first, then 2, then 3, then 4.

• If each frame simply pushed its element on top, the order would be 1, then 2, then 3, then 4 → [1,2,3,4], the same stack, not reversed.
• If each frame inserts its element at the bottom: 1 → [1]; 2 under it → [2,1]; 3 under → [3,2,1]; 4 under → [4,3,2,1] reversed ✓.

So we need a second helper: insert_at_bottom(st, x).

4Building the logic

Function 1: reverse(st)

• Base case: stack empty → return. (Without it we'd pop from an empty list.)
• Way down: top = st.pop(), then reverse(st). Leap of faith: this reverses the remaining stack.
• Way back up: insert_at_bottom(st, top).

Function 2: insert_at_bottom(st, x): the same trick again

We can only push on top. So how do we get x to the bottom?

• Base case: if the stack is empty, the top is the bottom → st.append(x) and return.
• Otherwise: it's not safe to push x yet. Pop the top into temp (stored in this frame) and call insert_at_bottom(st, x) again on the smaller stack. Keep doing this until the stack is empty, then x gets pushed.
• Way back up: after the call returns, x is already at the bottom. Push temp back on top. Each frame puts back what it removed, in the original order.

5Approach steps

1. reverse(st): if empty → return.
2. top = pop.
3. reverse(st) (empties the rest, then rebuilds it reversed).
4. insert_at_bottom(st, top).
5. insert_at_bottom(st, x): if empty → push x, return.
6. temp = pop.
7. insert_at_bottom(st, x).
8. push temp.

6Code (Python)

class Solution:
    def reverse(self, st):
        if not st:                        # base case: nothing left to reverse
            return
        top = st.pop()                    # way down: park the top in this frame
        self.reverse(st)                  # reverse everything below it
        self.insert_at_bottom(st, top)    # way up: put it UNDER the reversed rest

    def insert_at_bottom(self, st, x):
        if not st:                        # base case: empty, so top == bottom
            st.append(x)
            return
        temp = st.pop()                   # way down: move the top out of the way
        self.insert_at_bottom(st, x)      # x goes to the bottom of the smaller stack
        st.append(temp)                   # way up: put temp back on top

7Code line by line

On screen the teacher's first run failed because a function name didn't match where it was called. Keep the helper's name identical in the definition and in every call.

8Dry run: st = [1, 2, 3, 4] (bottom → top)

The call tree. R = reverse, I = insert_at_bottom. Each line shows the stack when the call starts → when it returns.

R [1,2,3,4]  top=4                               → [4,3,2,1]
├─ R [1,2,3]  top=3                              → [3,2,1]
│  ├─ R [1,2]  top=2                             → [2,1]
│  │  ├─ R [1]  top=1                            → [1]
│  │  │  ├─ R []   base case                     → []
│  │  │  └─ I x=1 on []  push 1                  → [1]
│  │  └─ I x=2 on [1]  temp=1                    → [2,1]
│  │     └─ I x=2 on []  push 2                  → [2]
│  └─ I x=3 on [2,1]  temp=1                     → [3,2,1]
│     └─ I x=3 on [2]  temp=2                    → [3,2]
│        └─ I x=3 on []  push 3                  → [3]
└─ I x=4 on [3,2,1]  temp=1                      → [4,3,2,1]
   └─ I x=4 on [3,2]  temp=2                     → [4,3,2]
      └─ I x=4 on [3]  temp=3                    → [4,3]
         └─ I x=4 on []  push 4                  → [4]

The story, every call and every return (st is written bottom → top):

1. R1 called with [1,2,3,4]. Pops 4 into top. st = [1,2,3]. Calls R2.
2. R2: pops 3. st = [1,2]. Calls R3.
3. R3: pops 2. st = [1]. Calls R4.
4. R4: pops 1. st = []. Calls R5.
5. R5: st is empty → returns (base case). st = []. All 4 elements now live in the frames R1–R4.
6. Back in R4 (top = 1): calls I(x=1) on []. Empty → push 1 → returns. st = [1]. R4 returns.
7. Back in R3 (top = 2): calls I(x=2) on [1]. Not empty → temp = 1, st = []. Calls I(x=2) on [] → push 2 → returns, st = [2]. Back in the outer I: push temp 1 → st = [2,1]. Returns. R3 returns.
8. Back in R2 (top = 3): I(x=3) on [2,1]: temp = 1 → st = [2]. I(x=3) on [2]: temp = 2 → st = []. I(x=3) on []: push 3 → [3], returns. Push temp 2 → [3,2], returns. Push temp 1 → [3,2,1], returns. R2 returns.
9. Back in R1 (top = 4): I(x=4) on [3,2,1]: temp = 1 → [3,2]; temp = 2 → [3]; temp = 3 → []; push 4 → [4]. Coming back up: push 3 → [4,3]; push 2 → [4,3,2]; push 1 → [4,3,2,1]. R1 returns.
10. The call stack is empty. Read bottom → top: 4, 3, 2, 1. Reversed ✓

The call stack at key moments (each frame shows what it's holding; the box on the right is the real stack st):

In the frame pictures the newest call is on top (red). In the st pictures the bottom of the box is the bottom of the stack.

9Complexity & remember

Counting the work. reverse pops each element once: n pops, n + 1 reverse calls. The cost is in the inserts. Inserting the 1st element pops nothing, the 2nd pops 1, the 3rd pops 2, …, the n-th pops n − 1. The teacher puts it as "1 one time, 2 two times, 3 three times…".

• Time O(n²): 0 + 1 + 2 + … + (n−1) = n(n−1)/2 pops, plus the same number of pushes back.
• Space O(n): the teacher counts it as 2n: the inner stack of reverse (up to n frames) plus the inner stack of insert_at_bottom (up to n frames). That's a safe upper bound. If you count exactly, the peak is n + 1: while element k is being inserted, only n − k + 1 reverse frames are still waiting, and the insert chain is k frames deep. The pictures above show 5 frames for n = 4. Either way it's O(n), and it's all the call stack's internal space. We don't create any stack ourselves.
• The iterative ways are O(n) time, but Way 1 breaks the stack rules and Way 2 needs a second stack. The point of this problem is to learn the recursive shape, not to be fastest.

Part C · Revision page

import sys
sys.setrecursionlimit(10**5)

s = Solution()
for st in ([1, 2, 3, 4], [], [7], [5, 9], [3, 1, 2, 1]):
    s.reverse(st)
    print(st)        # [4, 3, 2, 1]  []  [7]  [9, 5]  [1, 2, 1, 3]

Based on this video: Reverse a Stack Using Recursion