Foundations — Recursion — call stack visualization, base case, recursive case

Before you can read the parent note, you need to own every piece of notation it throws at you. This page starts from absolute zero and builds each symbol on the one before it. Nothing is used before it is drawn.

1. What is a function? (the box that eats and returns)

Look at the figure: the input goes in the left side, the machinery churns, and exactly one value comes out the right side (the return value).

In Python this box is written:

def double(x):      # 'def' = "define a box named double that eats x"
    return x + x    # hand back x + x, then stop

• def ::: the keyword that starts the box definition.
• double ::: the box's name — how you call it later.
• (x) ::: the parameter, a placeholder for whatever input you pass in.
• return x + x ::: compute x + x, then send it back out and stop.

See Functions and return values for the full story of inputs and outputs.

2. Calling a function (and calling itself)

A function is even allowed to call itself with a different input:

def f(n):
    return f(n - 1)   # f calls f — this is recursion (careful: no stop here!)

That line — a box using its own name inside itself — is the seed of recursion. It only becomes safe once we add a stopping rule (Section 6).

3. The symbol n and the operation n - 1

Look at the number line in the figure: each recursive call slides the marker one place left, marching toward the special stopping value.

4. Lists and the slice L[0], L[1:]

The parent's second example uses lists, so we define them from zero.

The colon : means "and all that follows." The figure shows the list split into head (L[0], one item) and tail (L[1:], the leftovers).

5. The factorial symbol n!

The parent's main derivation uses n!, so let's earn that symbol.

6. Base case vs recursive case (the two mandatory halves)

Now the two starring terms of the whole topic.

The figure shows the fork every recursive function contains: a question at the top ("is the input tiny?"), a stop-and-answer branch (base case), and a shrink-and-call-again branch (recursive case).

7. The call stack: LIFO, frames, RecursionError

See The Call Stack and Stack Frames for the memory-level picture, and Big-O and Recursion Depth for how deep is too deep.

Prerequisite map

Each foundation feeds the next: a function that can return and call itself, plus a way to make the input smaller (n-1, L[1:]), plus a known stopping value (base case), all managed by the call stack.

Equipment checklist

Test yourself — cover the right side and answer before revealing.

Ready? Head back to the parent: the main note builds fact and traces the stack using exactly these pieces. Prefer loops instead? Compare with Iteration — for and while loops.