Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Thinking Recursively

Editorial

A stack with nowhere to put things

Reverse a stack. You may push, pop, look at the top and ask whether it's empty, and that's all: no second stack, no array to copy into, no loop that walks it. With a spare stack it's three lines. Without one it looks impossible.

But you do have a spare stack. Every call puts a frame on the call stack, and a frame can hold a value while the rest of the work happens. Pop a value, keep it in the frame, let a call deal with the rest, and the value is still there when that call returns. This lesson is about using that on purpose: say what a function returns, trust it on a smaller input, and do one step yourself.

Three dashed zones. Before: the values 1 to 4 as shaded tiles stacked bottom to top, each its own colour. Frames waiting: four call frames stacked, each card reading reverse, holds, with one value in its tile: 4 in the bottom frame, labelled first call, then 3, 2 and 1 on top. After: the same tiles stacked 4, 3, 2, 1 from the bottom. An arrow under a pill reading pop leads into the frames, and one under push leads out. Focal line: each frame holds one value while the rest is handled. Title: the call stack is the second stack.

Trust the smaller call

Say what the function does for any stack: insert_at_bottom(stack, x) puts x under everything already in it. Now write it as if it already worked on smaller stacks:

  • If the stack is empty, x is its bottom: push it.
  • Otherwise pop the top and hold it, insert x at the bottom of what's left, and push the top back.

What's left is a smaller stack, so you trust the call on it and don't follow it. Three checks make that safe:

  1. The base case answers right. An empty stack gets x, and x is its bottom.
  2. Every call gets closer to a base case. Each call works on a stack one value shorter, and a size can't shrink forever.
  3. The step is right if the smaller call is. If x went under the rest, pushing the top back puts everything else above it, in its old order.

That's an induction proof: it's right for the empty stack, and right for n values whenever it's right for n − 1. Recursion Basics showed what the frames do; the three checks are why you can stop following them. Reversing has the same shape: pop the top, trust the call to reverse the rest, and put the old top where it belongs now, at the bottom:

void insertAtBottom(stack<int>& s, int x) {
    if (s.empty()) {                       // empty: x is the bottom now
        s.push(x);
        return;
    }
    int top = s.top();
    s.pop();
    insertAtBottom(s, x);                  // trust it: x goes under everything that's left
    s.push(top);                           // then the top goes back where it was
}

void reverseStack(stack<int>& s) {
    if (s.empty()) return;                 // nothing to reverse
    int top = s.top();
    s.pop();
    reverseStack(s);                       // trust it: the rest comes back reversed
    insertAtBottom(s, top);                // and the old top belongs at the bottom
}

def insert_at_bottom(stack, x):
    if not stack:                      # empty: x is the bottom now
        stack.append(x)
        return
    top = stack.pop()
    insert_at_bottom(stack, x)         # trust it: x goes under everything that's left
    stack.append(top)                  # then the top goes back where it was


def reverse_stack(stack):
    if not stack:                      # nothing to reverse
        return
    top = stack.pop()
    reverse_stack(stack)               # trust it: the rest comes back reversed
    insert_at_bottom(stack, top)       # and the old top belongs at the bottom

static void insertAtBottom(Deque<Integer> stack, int x) {
    if (stack.isEmpty()) {                 // empty: x is the bottom now
        stack.push(x);
        return;
    }
    int top = stack.pop();
    insertAtBottom(stack, x);              // trust it: x goes under everything that's left
    stack.push(top);                       // then the top goes back where it was
}

static void reverseStack(Deque<Integer> stack) {
    if (stack.isEmpty()) return;           // nothing to reverse
    int top = stack.pop();
    reverseStack(stack);                   // trust it: the rest comes back reversed
    insertAtBottom(stack, top);            // and the old top belongs at the bottom
}

function insertAtBottom(stack, x) {
    if (stack.length === 0) {              // empty: x is the bottom now
        stack.push(x);
        return;
    }
    const top = stack.pop();
    insertAtBottom(stack, x);              // trust it: x goes under everything that's left
    stack.push(top);                       // then the top goes back where it was
}

function reverseStack(stack) {
    if (stack.length === 0) return;        // nothing to reverse
    const top = stack.pop();
    reverseStack(stack);                   // trust it: the rest comes back reversed
    insertAtBottom(stack, top);            // and the old top belongs at the bottom
}

Each printed [0, 1, 2, 3], with 0 inserted under [1, 2, 3], and [4, 3, 2, 1]. Here are the frames on [1, 2, 3]: each popped value waits in a frame while the rest is handled, and goes back as the calls return:

Reversing [1, 2, 3] with only push and pop — Left, the stack, bottom to top. Right, the frames waiting, newest on top, each holding the value it popped. Indigo marks each stack's top: on the right, the call running now.

Below, you write the step. The smaller call is sealed: you're told what it hands back and asked what this call does with its popped value. Then run the real recursion with your steps and watch whether the stack comes out reversed.

Trust the Call: you write the step, then run it

What it costs

Every value is popped once by the reverse and inserted once at the bottom, but inserting under k values pops all k and pushes them back. The inserts land on stacks of 0, 1, …, n − 1 values, so reversing n values makes n(n + 1)/2 insert calls: O(n²) time. Counted in Python:

ValuesReverse callsInsert callsDeepest point, in frames
10115511
1001015,050101
1,0001,001500,5001,001
A dashed zone titled each insert, bottom first, with five rows of shaded tiles, one per value in the order its insert happens: insert 1, then 2, 3, 4 and 5. Each row is the stack the value ends up under, its own tile first in colour and the values it passed pale, so the rows grow from 1 to 5 tiles like a staircase, each ending in its count of calls, 1 call to 5 calls. A pill under the longest row reads passes every value above it. A card beside the zone reads 15 insert calls for 5 values, 1 + 2 + 3 + 4 + 5, n(n + 1) / 2, O(n²). Focal line: each insert passes every value before it, so the work is n². Title: every value travels to the bottom.

In C++, reversing 5,000, 10,000 and 20,000 values took 137.7, 555.0 and 2,246.6 ms: twice the values, about four times the time.

The space is the depth. The deepest moment is the outermost frame inserting its value under the other n − 1: n + 1 frames, O(n) space, and every language caps the depth. The largest stack this code reversed on our judge, each language at its defaults:

LanguageLargest stack reversedWhat stopped it
Python997 valuesRecursionError: a limit of 1,000 calls
Java7,300 to 7,689 values over 3 runsStackOverflowError: the thread's stack is full
JavaScript9,635 valuesRangeError: Maximum call stack size exceeded
C++no limit of its owntime first: 20,000 values took 2,247 ms

With sys.setrecursionlimit(10_000) the same Python code reversed 4,000 values. Java's number moves between runs because the JVM compiles a busy method part-way through, and compiled calls take less stack. C++ ran ten million nested calls on the judge without complaint, so there the O(n²) time runs out long before the stack. Introduction to Binary Trees hit the same walls on a chain of tree nodes. Sort a Stack Recursively allows up to 1,000 values, and sorting 1,000 this way raised RecursionError in Python too.

Sort a stack with the same move

Sort a stack so the smallest value is at the bottom, again with only push and pop. Pop the top, trust the call to sort the rest, then put the old top into its place: insert_sorted pops everything bigger than it, pushes it, and puts the bigger ones back:

void insertSorted(stack<int>& s, int x) {
    if (s.empty() || s.top() <= x) {       // the top is at most x, so x can sit on it
        s.push(x);
        return;
    }
    int top = s.top();
    s.pop();
    insertSorted(s, x);                    // trust it: x lands in its place among the rest
    s.push(top);                           // the bigger top goes back above it
}

void sortStack(stack<int>& s) {
    if (s.empty()) return;
    int top = s.top();
    s.pop();
    sortStack(s);                          // trust it: the rest comes back sorted, smallest at the bottom
    insertSorted(s, top);                  // and the old top goes into its place
}

def insert_sorted(stack, x):
    if not stack or stack[-1] <= x:    # the top is at most x, so x can sit on it
        stack.append(x)
        return
    top = stack.pop()
    insert_sorted(stack, x)            # trust it: x lands in its place among the rest
    stack.append(top)                  # the bigger top goes back above it


def sort_stack(stack):
    if not stack:
        return
    top = stack.pop()
    sort_stack(stack)                  # trust it: the rest comes back sorted, smallest at the bottom
    insert_sorted(stack, top)          # and the old top goes into its place

static void insertSorted(Deque<Integer> stack, int x) {
    if (stack.isEmpty() || stack.peek() <= x) {   // the top is at most x, so x can sit on it
        stack.push(x);
        return;
    }
    int top = stack.pop();
    insertSorted(stack, x);                // trust it: x lands in its place among the rest
    stack.push(top);                       // the bigger top goes back above it
}

static void sortStack(Deque<Integer> stack) {
    if (stack.isEmpty()) return;
    int top = stack.pop();
    sortStack(stack);                      // trust it: the rest comes back sorted, smallest at the bottom
    insertSorted(stack, top);              // and the old top goes into its place
}

function insertSorted(stack, x) {
    if (stack.length === 0 || stack[stack.length - 1] <= x) {   // the top is at most x, so x can sit on it
        stack.push(x);
        return;
    }
    const top = stack.pop();
    insertSorted(stack, x);                // trust it: x lands in its place among the rest
    stack.push(top);                       // the bigger top goes back above it
}

function sortStack(stack) {
    if (stack.length === 0) return;
    const top = stack.pop();
    sortStack(stack);                      // trust it: the rest comes back sorted, smallest at the bottom
    insertSorted(stack, top);              // and the old top goes into its place
}

Each printed [1, 3, 5] and [2, 3, 11, 32, 41]. The proof is the same three checks: an empty stack is sorted; each call sorts one value fewer; and if the rest is sorted, inserting the top into its place keeps it sorted. It's insertion sort with the call stack as the hand that holds the cards: O(n²) comparisons in the worst case, n + 1 frames deep.

When the input is nested

Decode String turns 3[a2[c]] into accaccacc: a count before brackets repeats what's inside them, and brackets can sit inside brackets. A single loop has to keep its own stack of unfinished counts and texts to know how deep it is. Recursion keeps that stack for you: one call decodes everything up to its closing ]. When it meets a [, it trusts a new call with the inside, repeats what comes back, and carries on. The calls nest exactly as the brackets do:

The string 3[a2[c]] as a row of shaded character tiles: the 3 in blue, the outer brackets and what they hold in orange, the inner pair and its c in teal, each pair framed by a dashed zone in its colour, the inner zone inside the outer one. Below, three call zones in the same colours: call 1 reads 3[a2[c]] and returns accaccacc; call 2 reads a2[c] and returns acc; call 3 reads c and returns c. Between them, dashed arrows under pills reading at [ lead from each call to the next, and solid arrows lead back over pills reading c and acc. Under the calls, a pill reads decode_string("3[a2[c]]") gives "accaccacc". Focal line: one call per bracket pair, each returning the text inside it. Title: the calls follow the brackets.
string decode(const string& s, int& i) {          // from s[i] up to the matching ']' or the end
    string out;
    int count = 0;
    while (i < (int)s.size() && s[i] != ']') {
        char ch = s[i];
        if (isdigit(ch)) {
            count = count * 10 + (ch - '0');      // a count can have several digits
            i++;
        } else if (ch == '[') {
            i++;
            string inner = decode(s, i);          // trust it: decodes up to the matching ']'
            i++;                                  // step past that ']'
            for (int k = 0; k < count; k++) out += inner;
            count = 0;
        } else {
            out += ch;
            i++;
        }
    }
    return out;
}

string decodeString(const string& s) {
    int i = 0;                                    // one position, shared by every call
    return decode(s, i);
}

def decode_string(s):
    i = 0                                       # one position, shared by every call

    def decode():                               # from s[i] up to the matching ']' or the end
        nonlocal i
        out, count = [], 0
        while i < len(s) and s[i] != "]":
            ch = s[i]
            if ch.isdigit():
                count = count * 10 + int(ch)    # a count can have several digits
                i += 1
            elif ch == "[":
                i += 1
                inner = decode()                # trust it: decodes up to the matching ']'
                i += 1                          # step past that ']'
                out.append(inner * count)
                count = 0
            else:
                out.append(ch)
                i += 1
        return "".join(out)

    return decode()

static String decodeString(String s) {
    return decode(s, new int[]{0});               // one position, shared by every call
}

static String decode(String s, int[] at) {        // from s[at[0]] up to the matching ']' or the end
    StringBuilder out = new StringBuilder();
    int count = 0;
    while (at[0] < s.length() && s.charAt(at[0]) != ']') {
        char ch = s.charAt(at[0]);
        if (Character.isDigit(ch)) {
            count = count * 10 + (ch - '0');      // a count can have several digits
            at[0]++;
        } else if (ch == '[') {
            at[0]++;
            String inner = decode(s, at);         // trust it: decodes up to the matching ']'
            at[0]++;                              // step past that ']'
            out.append(inner.repeat(count));
            count = 0;
        } else {
            out.append(ch);
            at[0]++;
        }
    }
    return out.toString();
}

function decodeString(s) {
    let i = 0;                                    // one position, shared by every call
    function decode() {                           // from s[i] up to the matching ']' or the end
        let out = "", count = 0;
        while (i < s.length && s[i] !== "]") {
            const ch = s[i];
            if (ch >= "0" && ch <= "9") {
                count = count * 10 + Number(ch);  // a count can have several digits
                i++;
            } else if (ch === "[") {
                i++;
                const inner = decode();           // trust it: decodes up to the matching ']'
                i++;                              // step past that ']'
                out += inner.repeat(count);
                count = 0;
            } else {
                out += ch;
                i++;
            }
        }
        return out;
    }
    return decode();
}

Each printed aaabcbc, accaccacc and abcabccdcdcdef, twelve a's for 12[a], since a count can have more than one digit, and abbbabbb for 2[a3[b]]. All the calls share one position, so each character is read once, and the time is the length of the output, which can be far longer than the input. The depth is the deepest nesting of brackets.

Split, solve, combine

Sometimes the smaller inputs are pieces of the big one. Split it into parts of the same kind, solve each with a trusted call, and combine the answers: that's divide and conquer. Splitting in half keeps it shallow, since n values halved again and again run out after log₂ n levels.

  • Merge Sort splits an array in two, sorts both halves and merges them: T(n) = 2T(n/2) + O(n), which is O(n log n), log₂ n frames deep.
  • Fast power gets xⁿ from x^(n/2), squared, with one more x when n is odd: one call per halving, O(log n) multiplications (Modular Arithmetic, Fast Power and Counting).
  • Construct Quad Tree splits a square grid into four quadrants, builds each one's tree, and merges four leaves with the same value into one: T(n) = 4T(n/2) + O(1), every cell read once, O(n²) for an n × n grid, and log₂ n levels deep.

The three checks still apply: the smallest piece answers directly, every piece is smaller than its parent, and the combine is right if the pieces are.

Spotting it, and when it breaks

The clues. The input holds smaller copies of itself: brackets inside brackets, a tree, a grid made of quadrants, a list whose tail is a list. Or the rules take away the tools you'd reach for: "without loops", "using only push and pop". Or the answer for n is easy once you have it for something smaller.

The near-misses. A flat list with nothing nested: a loop is simpler and has no depth limit. The same smaller input reached again and again, as in a naive Fibonacci: remember each answer (Introduction to Dynamic Programming). Choices to try and take back: backtracking, the next lesson (Backtracking: Subsets and Combinations).

When it breaks. Depth: a chain of n calls needs n frames, and the limits above are low. Replace the call stack with a stack of your own, or, in Python, raise the limit when the depth is known and modest. And recursion makes nothing faster by itself: reversing a stack this way is still O(n²).

Bugs that cost a submission

Putting the value back where it came from.

def reverse_stack(stack):
    if not stack:
        return
    top = stack.pop()
    reverse_stack(stack)
    stack.append(top)                  # back on top, where it came from

On [1, 2, 3, 4] it returned [1, 2, 3, 4]. Each call puts back exactly what it took, so nothing moves. The step has to be something other than undoing the pop: the old top belongs at the bottom, under the reversed rest.

Forgetting the empty stack.

def insert_sorted(stack, x):
    if stack[-1] <= x:                 # but the stack can be empty
        stack.append(x)
        return
    top = stack.pop()
    insert_sorted(stack, x)
    stack.append(top)

Sorting [5, 1, 3] crashed with IndexError: list index out of range: the first insert lands on an empty stack, and stack[-1] has nothing to read. The base case has to come first, if not stack or stack[-1] <= x.

Going too deep in Python.

s = list(range(1, 1001))
reverse_stack(s)       # the correct reverse from above

It raised RecursionError: 1,000 values need about 1,001 frames, past the default limit of 1,000 calls. Call sys.setrecursionlimit with room for your depth, or use an explicit stack.

Reading a count one digit at a time.

if ch.isdigit():
    count = int(ch)                 # only the last digit survives
    i += 1

decode_string("12[a]") returned aa instead of twelve a's: the 2 replaced the 1. Build the number as you read it, count * 10 + digit.

Check yourself

Quiz

1 / 6

Multiple choice

reverse_stack has popped 4 off [1, 2, 3, 4], and you trust the call to turn what's left into [3, 2, 1]. What finishes the job?

Practice problems

In this order:

  1. Reverse a Stack Recursively: the leap of faith, with a helper that inserts at the bottom.
  2. Sort a Stack Recursively: the same move, inserting into order.
  3. Decode String: one call per pair of brackets, one position shared by all.
  4. Construct Quad Tree: split into four, merge four equal leaves.
  5. Special Binary String: split into special pieces, trust the call on each one's inside, then sort the pieces.

Next, Backtracking: Subsets and Combinations: choose, explore, and take the choice back.