Recursion — call stack visualization, base case, recursive case

DERIVATION — building `factorial` from scratch

We want $n! = 1 \cdot 2 \cdot 3 \cdots n$ .

Step 1 — Spot self-similarity. Notice $n! = n \cdot (n-1)!$ . Why this step? Because the product of $1..n$ is just $n$ times the product of $1..(n-1)$ — the same kind of problem, one size smaller. That self-reference is the recursive case.

Step 2 — Find where shrinking stops. $(n-1)!$ leads to $(n-2)!$ ... down to $0!$ . By definition $0! = 1$ . Why this step? We need an input we can answer with no further recursion. $0! = 1$ needs no multiplication, so it's the base case.

Step 3 — Combine into a function.

def fact(n):
    if n == 0:          # base case
        return 1
    return n * fact(n-1)  # recursive case

Worked example Second example — sum of a list

summ([4, 2, 7]) Self-similarity: $\text{sum}(L) = L[0] + \text{sum}(L[1:])$ . Base: empty list sums to $0$ .

def summ(L):
    if not L:        # base case: empty list
        return 0
    return L[0] + summ(L[1:])  # recursive case

Trace: summ([4,2,7]) → 4 + summ([2,7]) → 4 + (2 + summ([7])) → 4 + (2 + (7 + summ([]))) → 4 + (2 + (7 + 0)) = 13. Why L[1:]? That's the "smaller problem" — the rest of the list. Each call removes one element, so we must reach [].

Worked example Forecast-then-Verify

Forecast: What does count_down(2) print for

def count_down(n):
    if n < 0: return
    print(n)
    count_down(n-1)

Predict before reading → 2, 1, 0 then stops. Verify: n=2→print 2; n=1→print 1; n=0→print 0; n=-1→base case, return. ✅ Why print BEFORE the call? Because the print happens during winding. If you moved print(n) after count_down(n-1), it would print during unwinding → 0,1,2.

Common mistakes (Steel-manned)

Recursion vs Iteration (80/20)

Recall Feynman: explain to a 12-year-old

Imagine you're standing in a long line and want to know your position. You can't see the front, so you tap the person ahead and ask "what's your number?" They do the same thing, tapping the next person, and so on — until the very first person says "I'm number 1!" (that's the base case — they answer without asking anyone). Then the answer travels back: each person adds 1 to what they heard and tells the person behind. That's recursion: ask a smaller copy of yourself, wait, then add your bit. The "people waiting for answers" are the call stack.

Active-recall flashcards

What two parts must every recursive function have?

A base case (stops recursion) and a recursive case (calls itself on a smaller input).

What is the base case?

The smallest input whose answer is known directly, with no further recursive call — it stops the recursion.

Why does a missing/wrong base case crash?

Recursion never stops, frames pile up, and Python hits maximum recursion depth → RecursionError (stack overflow).

What data structure stores active function calls, and what order does it follow?

The call stack, which is LIFO (last-in-first-out).

In fact(3), which call returns its value FIRST?

fact(0) — the base case — because the deepest/last-pushed frame finishes first (LIFO).

What are the two phases of a recursive run?

Winding (pushing frames going down) and unwinding (popping frames and combining returns going back up).

Why must the recursive call use n-1 (or L[1:])?

To make progress toward the base case; otherwise the problem never shrinks and recursion is infinite.

What happens if you forget return in the recursive case?

The sub-call's result is discarded; the function returns None instead of the computed value.

Do all recursive calls share the same local variable n?

No — each stack frame has its own independent copy of the locals.

Self-similar definition of factorial used to derive recursion?

n! = n · (n-1)! with 0! = 1.

Connections

Functions and return values — recursion needs solid return semantics.
The Call Stack and Stack Frames — memory model behind recursion.
Iteration — for and while loops — every recursion has an iterative twin.
Fibonacci and overlapping subproblems — leads into Memoization and Dynamic Programming.
Tree and Graph Traversal — naturally recursive structures.
Big-O and Recursion Depth — cost of stacking frames.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Recursion ka matlab hai ek function jo khud ko hi call karta hai — lekin har baar thode chote problem ke saath. Socho jaise factorial: $n! = n \times (n-1)!$ . Yahan bada answer chote answer pe depend karta hai, isiliye function khud ko n-1 ke saath call karta hai. Do cheezein hamesha chahiye: base case (jahan answer seedha pata hai, jaise $0! = 1$ , aur recursion ruk jaata hai) aur recursive case (jahan function chote input ke saath khud ko bulata hai). Base case bhool gaye to recursion kabhi rukega nahi → RecursionError (stack overflow).

Call stack ko aise samjho: jab fact(3) chalta hai, woh fact(2) ka answer maangta hai, isliye pause ho jaata hai aur memory mein ek "frame" ban jaata hai. Phir fact(2), fact(1), fact(0) — frames ek ke upar ek pile-up hote jaate hain. Isko winding kehte hain. Jab base case (fact(0)=1) hit hota hai, tab return values neeche se upar travel karte hain: $1 \to 1 \to 2 \to 6$ . Yeh unwinding hai. Stack LIFO hota hai — sabse last call sabse pehle khatam hoti hai.

Sabse common galti: log sochte hain "input chota ho raha hai to apne aap ruk jayega" — nahi! Jab tak tum explicitly if n == 0: return nahi likhoge, rukega nahi. Doosri galti: recursive call mein return lagana bhool jaana — phir answer waapas hi nahi aata, None mil jaata hai. Yaad rakho B.A.S.E.: Base case pehle, Always shrink karo, Save (return + combine) the result, aur Each call ka apna alag frame hota hai. Yeh idea aage Fibonacci, tree traversal, aur dynamic programming mein bahut kaam aayega.

Recursion — call stack visualization, base case, recursive case

WHAT is recursion?

HOW the call stack works

DERIVATION — building `factorial` from scratch

Common mistakes (Steel-manned)

Recursion vs Iteration (80/20)

Active-recall flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Introduction to Programming (Python)

Connections