Visual walkthrough — Recursion — call stack visualization, base case, recursive case

Before anything else, three plain words we will lean on the whole page:

Our target, stated once so every symbol below is earned:

Step 1 — Spot the self-similar shape

WHAT. Look at the product and peel off the last number, $n$: $n!=\underset{\text{the biggest factor}}{\underbrace{n}}\cdot \underset{\text{this is just }(n-1)!}{\underbrace{(1\cdot 2\cdots (n-1))}}.$ So $n!=n\cdot (n-1)!$. The term $(n-1)!$ means "the same factorial question, but one size smaller".

WHY. Recursion only pays off when a big problem contains a smaller copy of itself. Here the copy is literally sitting inside: to know $n!$ you only need $n$ and the answer to $(n-1)!$. That embedded copy is the recursive case.

PICTURE. The nested boxes below: the outer box is $n!$; peeling the label $n$ off reveals an identical-shaped inner box $(n-1)!$, and so on inward.

Step 2 — Find the floor where shrinking stops

WHAT. Keep peeling: $n!\to (n-1)!\to (n-2)!\to \cdots \to 1!\to 0!$. And $0!$ we simply define to equal $1$ (the empty product — multiply nothing, get the "do-nothing" number $1$). $\text{fact}(0)=1\text{(no multiplication, no further call)}.$

WHY. A recursive machine that only shrinks would fall forever. We need one input whose answer is known outright, with zero further recursion. That is the base case. Choosing $0$ (not $1$) also handles the input $\text{fact}(0)$ correctly for free.

PICTURE. The descending staircase: each step drops the input by one; the base case $0!=1$ is the solid ground the staircase lands on.

Step 3 — Write the two-case rule

WHAT. Glue Steps 1 and 2 into one definition. The brace means "pick the line whose condition is true": $\text{fact}(n)=\{\begin{array}{ll}1& n=0(\text{base case})\\ \underset{\text{this call’s own }n}{\underbrace{n}}\cdot \underset{\text{smaller sub-problem}}{\underbrace{\text{fact}(n-1)}}& n>0(\text{recursive case})\end{array}$

WHY. Every recursive function needs exactly these two parts: a stop (base case) and a shrink-and-combine (recursive case). The $n-1$ guarantees progress toward the base; the $n\cdot$ is the "combine" that reassembles the answer.

PICTURE. A fork-in-the-road: the diamond tests n == 0; one branch returns $1$, the other multiplies and calls a smaller self.

def fact(n):
    if n == 0:            # base case  → the STOP
        return 1
    return n * fact(n-1)  # recursive case → shrink & combine

Step 4 — Winding: watch the frames pile up

WHAT. Call fact(3). It cannot finish, because it needs fact(2) first — so it pauses and a new frame is pushed. That one needs fact(1), pauses, pushes. And so on: $\text{fact}(3)=3\cdot \boxed{\text{fact}(2)},\text{fact}(2)=2\cdot \boxed{\text{fact}(1)},\text{fact}(1)=1\cdot \boxed{\text{fact}(0)}.$ Each boxed part is an unknown-so-far answer the paused call is waiting on.

WHY. A call can only return once its sub-call gives an answer. So the whole chain freezes going down — this descent is the winding phase. Crucially, each frame keeps its own private $n$ (frame for $n=3$ and frame for $n=2$ coexist — they are not shared).

PICTURE. Four sticky-notes stacked, top = most recent (fact(0)), each note showing its private $n$ and "waiting for ..." arrow to the note above.

Step 5 — The base case lands

WHAT. The top frame is fact(0). It matches n == 0, so it returns $1$ immediately — no new frame, no multiplication. $\text{fact}(0)⟶1.$

WHY. This is the only moment recursion produces a value out of thin air. Without this line the pile would keep growing past Python's depth limit (~1000) and crash with RecursionError. The base case is the hinge between winding and unwinding.

PICTURE. The top sticky-note flips over to reveal a green "1", the first concrete value in the whole pile.

Step 6 — Unwinding: multiply on the way back up

WHAT. Now peel notes off the top (LIFO) and let each finish its paused multiplication using the answer just handed up: $\text{fact}(1)=1\cdot \underset{\text{from fact(0)}}{\underbrace{1}}=1,\text{fact}(2)=2\cdot \underset{\text{from fact(1)}}{\underbrace{1}}=2,\text{fact}(3)=3\cdot \underset{\text{from fact(2)}}{\underbrace{2}}=6.$

WHY. Because the deepest (last-pushed) frame finishes first, the multiplications happen outside-in on the way up — the ordering is forced by LIFO, not chosen by us. fact(3) is the last to complete and delivers the final $6$.

PICTURE. The stack shrinking downward, a value $1\to 1\to 2\to 6$ climbing hand-over-hand as each frame pops.

Step 7 — The degenerate & edge inputs

WHAT & WHY, case by case:

• $\text{fact}(0)$ — the smallest legal input. Hits the base case on the very first call. Zero frames stack up beyond the first; answer $1$ returned instantly. This is why we chose $0$ (not $1$) as the base — the function is correct at its floor with no special-casing.
• $\text{fact}(1)$ — one step above the floor. Winds once to fact(0), unwinds once: $1\cdot 1=1$. ✅ (Correct: $1!=1$.)
• $\text{fact}(\text{negative})$ — the trap. Try fact(-1): it is $>0$? No. Is it $=0$? No. So it skips the base case and calls fact(-2), then fact(-3), … forever. The pile overflows → RecursionError. The lesson: your base case must actually catch every path that shrinking can take. A safer guard is if n <= 0: return 1.

PICTURE. Three mini-stacks side by side: fact(0) (one note, instant), fact(1) (two notes), and fact(-1) (an ever-growing red tower crashing through a ceiling).

The one-picture summary

The whole story in one V-shape: down the left arm the frames wind (each pausing, each keeping its own $n$), the base case $0!\to 1$ sits at the bottom of the V, and up the right arm they unwind, multiplying $1\to 1\to 2\to 6$.

Active recall

Related: Iteration — for and while loops · Fibonacci and overlapping subproblems · Big-O and Recursion Depth · Memoization and Dynamic Programming · Tree and Graph Traversal