LIFO & the Call Stack

The discipline, not the structure

A stack is barely a data structure — it's a discipline imposed on one: you may only add (push) and remove (pop) at the same end (the top). Last in, first out. That's the whole definition, and Module 4 already explained why it's free: the end of a dynamic array is the one place where adding and removing never shifts anyone.

stack = []           # a Python list IS a stack
stack.append(3)      # push        O(1) amortized
stack.append(7)
top = stack[-1]      # peek        O(1)
x = stack.pop()      # pop -> 7    O(1)
empty = not stack

No implementation lesson is needed — append/pop and push/pop on the structure you built in Module 4 are the implementation. What deserves the lesson is what the discipline is for.

Why LIFO is ever useful

The restriction seems like pure loss until you notice what it models: interrupted work. When task A pauses to do task B, and B pauses for C — completions must come back C, B, A. Most-recently-interrupted resumes first. Think of a stack of physical paperwork on a desk: pull a new document on top of the one you're working on, and you can't touch the original again until the new one is cleared off — the desk enforces LIFO whether you intend it to or not. Any process with that shape is a stack, whether you allocate one or not:

• a function calls a function calls a function — returns unwind in reverse;
• an editor's undo history — the next undo is the most recent action;
• your browser's back button;
• parsing anything nested — the innermost open thing closes first.

The call stack, made explicit

The Big O space lesson showed recursion costs O(depth) memory in frames. Now the connection sharpens: the runtime's call stack is a stack of frames, push on call, pop on return. Which means recursion is never necessary — any recursive traversal can trade the hidden stack for one you allocate:

import sys

def count_down_rec(n: int) -> None:
    if n == 0:
        return
    count_down_rec(n - 1)        # ~1000-frame limit in CPython

def count_down_iter(n: int) -> None:
    work = [n]                   # explicit stack of pending work
    while work:
        k = work.pop()
        if k > 0:
            work.append(k - 1)   # heap memory: millions are fine

The trade: recursion gets you the compiler's bookkeeping for free but inherits the runtime's depth limit; an explicit stack costs a few lines and moves the memory to the heap where it can grow. The depth limit is a direct consequence of where each one lives: the call stack is a small, fixed-size memory region the OS reserves per thread at startup — run out and you crash (RecursionError / "Maximum call stack size exceeded"), no matter how much RAM is free. The heap has no such reservation; it's a dynamic pool bounded only by whatever memory the system actually has. Trace count_down(3) both ways to see the same four frames living in two different places:

• Implicit (recursive): call count_down_rec(3) — frame n=3 pushed. It calls count_down_rec(2) — frame n=2 pushed on top. That calls count_down_rec(1) — frame n=1 pushed. That calls count_down_rec(0), the base case — frame n=0 pushed, then immediately returns and pops. The other three frames unwind in reverse: n=1 pops, n=2 pops, n=3 pops. Four pushes, four pops, entirely managed by the runtime.
• Explicit (iterative): work = [3]. Pop 3 (work = []); since 3 > 0, push 2 (work = [2]). Pop 2 (work = []); push 1 (work = [1]). Pop 1 (work = []); push 0 (work = [0]). Pop 0 (work = []); 0 > 0 is false, nothing pushes. Loop ends on the empty list. Same four pushes, four pops — just on a list you control instead of frames the runtime controls.

In Stage 3, DFS will be presented both ways — and they are the same algorithm, differing only in who owns the stack.