S027 · Recursion — Call Stack, Base Case, Worked Examples

Module M03: Data Structures & Algorithms · Session 27 of 130 · Track: SW 🌀

What you'll be able to do after this session

• Explain Recursion to a friend in one minute, out loud, no notes.
• Recognise it when you see it in real code / systems / papers.
• Complete the hands-on exercise at the end without looking up help.

Prerequisites

If you can't answer these in 30 seconds each, redo the linked session first:

• S007 — Functions — arguments, scope, closures

Pre-read (skim before the session)

• 🎥 Intuition (5–15 min) · Recursion in 100 seconds + example (Fireship) — the shortest sensible intro on the internet.
• 🎥 Deep dive (30–60 min) · MIT 6.006 — Recursion & the Call Stack — how the call stack actually works, formally.
• 🎥 Hands-on demo (10–20 min) · Recursion patterns (NeetCode) — factorial, fib, tree traversal side by side.
• 📖 Canonical article · Wikipedia — Recursion (computer science) — the definition + examples.
• 📖 Book chapter / tutorial · Python docs — Defining functions — the syntax layer you need.
• 📖 Engineering blog · Wikipedia — Tail call optimisation — why Python doesn't do it and how that shapes real code.

(a) Intuition · 5 min

The one-paragraph mental model. Why this concept exists, what problem it solves, and the analogy that makes it stick.

In one sentence: Functions that call themselves — and why that's not scary.

Recursion is a function that solves a big problem by asking a smaller version of itself to solve a smaller version of the problem, until the problem is tiny enough to solve directly. Think of Russian nesting dolls: to count them, you open one, then say "count the rest" — same task, one doll smaller. Eventually you open the smallest doll, find nothing inside, and count = 1. That "smallest doll" is the base case; the "count the rest" step is the recursive case.

Every recursive function has two pieces: (1) a base case that stops the recursion, and (2) a recursive step that reduces the problem and calls itself. Miss either one and you get either an infinite recursion (stack overflow) or a wrong answer.

Under the hood, every recursive call pushes a stack frame — a little box containing the function's local variables — onto the program's call stack. When the call returns, its frame is popped. The stack is finite (usually a few MB), so if your recursion goes millions deep, you crash.

One-sentence gotcha to carry forever: Recursion is the natural language for tree- and graph-shaped problems, and the wrong tool for anything that looks like a flat loop — factorial is prettier as a loop; tree traversal is uglier as one. Match the shape of the recursion to the shape of the data.

(b) Visual walkthrough · 15 min

Diagrams, worked examples, step-by-step visuals.

How factorial(4) unfolds on the call stack:

The stack grows to depth 5, then unwinds. Every recursive call is a physical frame in RAM.

Worked example — Fibonacci naive vs memoised:

Naive:

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2) → fib(1)+fib(0)
│   │   └── fib(1)
│   └── fib(2) → recomputed!
└── fib(3) → recomputed!

fib(n) naively takes O(2ⁿ) calls because it recomputes overlapping subproblems. Add memoisation (cache the answer for each n) and it drops to O(n).

That's dynamic programming waiting to be discovered.

The recursion recipe:

1. Define what the function returns in one clear sentence.
2. Write the base case(s) first — usually the smallest possible input.
3. Assume the recursive call already works (this is the leap of faith) and use it to solve the problem.
4. Check that each call makes the problem smaller — otherwise infinite recursion.

Two flavours to recognise:

• Linear recursion — one recursive call per step (factorial, list length).
• Tree recursion — multiple recursive calls per step (fib, tree traversal, generating subsets). Usually needs memoisation to stay tractable.

(c) Hands-on · 20 min

Code you type and run. Not pseudo-code — real, runnable, copy-pasteable.

# recursion_playground.py
import sys
from functools import lru_cache
from time import perf_counter
 
# ---- 1. Factorial — canonical linear recursion ----
def factorial(n):
    if n <= 1: return 1          # base case
    return n * factorial(n - 1)  # recursive step
 
print("factorial(5) =", factorial(5))
print("factorial(10) =", factorial(10))
 
# ---- 2. Naive Fibonacci vs memoised ----
def fib_naive(n):
    if n < 2: return n
    return fib_naive(n - 1) + fib_naive(n - 2)
 
@lru_cache(maxsize=None)
def fib_fast(n):
    if n < 2: return n
    return fib_fast(n - 1) + fib_fast(n - 2)
 
t0 = perf_counter(); fib_naive(30); t1 = perf_counter()
t2 = perf_counter(); fib_fast(500);  t3 = perf_counter()
print(f"
fib_naive(30)  : {(t1-t0)*1000:.1f} ms")
print(f"fib_fast(500)  : {(t3-t2)*1000:.3f} ms  (memoised, digits: {len(str(fib_fast(500)))})")
 
# ---- 3. Recursive tree traversal ----
class TreeNode:
    def __init__(self, v, left=None, right=None):
        self.v, self.left, self.right = v, left, right
 
# tree:      1
#           / \
#          2   3
#         / \
#        4   5
tree = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
 
def inorder(node):
    if not node: return []
    return inorder(node.left) + [node.v] + inorder(node.right)
 
def height(node):
    if not node: return 0
    return 1 + max(height(node.left), height(node.right))
 
print("
inorder:", inorder(tree))
print("height :", height(tree))
 
# ---- 4. Watch the stack limit ----
sys.setrecursionlimit(2000)
def deep(n):
    if n == 0: return "done"
    return deep(n - 1)
 
try:
    deep(5000)
except RecursionError as e:
    print(f"
deep(5000) crashed: {e}")
 
# ---- 5. Rewrite deep() iteratively — no stack risk ----
def deep_iter(n):
    while n > 0:
        n -= 1
    return "done"
 
print("deep_iter(100000) =", deep_iter(100_000))

Checklist:

1. factorial(5) = 120, factorial(10) = 3628800.
2. fib_naive(30) takes tens to hundreds of ms; fib_fast(500) is essentially instant.
3. Inorder traversal of the tree prints [4, 2, 5, 1, 3], height = 3.
4. deep(5000) raises RecursionError.
5. deep_iter(100000) completes without error.

Try this modification: write a recursive flatten(nested_list) that turns [1, [2, [3, [4]]], 5] into [1, 2, 3, 4, 5]. Then write an iterative version using an explicit stack. Compare which one you'd rather debug at 2 a.m.

(d) Production reality · 10 min

How this shows up in real systems, gotchas, war stories, common bugs.

Recursion is beautiful in code and dangerous in production. The three failure modes you'll see:

1. Stack overflow from adversary-controlled depth. JSON parsers, XML parsers, GraphQL query resolvers, template engines — all commonly use recursion for nesting. If the depth is bounded by user input and unbounded by the code, an attacker sends {"a":{"a":{"a": ... x 100_000}}} and crashes the process. This is a real CVE pattern: CPython's default json module raises RecursionError around depth 1000, but many older parsers segfault instead. Fixes: (a) hard-limit input nesting depth before parsing, (b) rewrite hot recursive parsers as iterative with an explicit stack, or (c) use a streaming parser (SAX/ijson) that doesn't recurse per level.

2. Exponential recursion without memoisation. The naive fib is a toy example, but the pattern shows up in real production: recursive tree-of-options search (chess engines, planners), recursive react component re-renders that trigger recursive re-renders, recursive dependency resolvers (npm's infamous v3 resolution algorithm was O(2^n) in pathological cases and hung on real npm trees). The instinct to memoise (or convert to iterative DP) turns hours of computation into milliseconds.

3. Python has no tail-call optimisation. Guido van Rossum explicitly rejected TCO for CPython — his argument was that debuggability of stack traces matters more than the perf/depth win. So recursive helpers that "just recurse and return" still eat a stack frame per call. If your algorithm is naturally tail-recursive (e.g., walking a linked list), rewrite it as a while loop. Languages that do TCO (Scheme, OCaml, Scala) can use recursion for what Python must express as loops.

Where recursion genuinely shines in production: parser combinators, compilers/AST walkers, tree/graph algorithms (DFS on file systems, dependency graphs), divide-and-conquer sorts (mergesort, quicksort), and functional-style transforms on nested data. In all of these the data itself is tree-shaped, so recursion mirrors the structure and reads better than any loop equivalent.

The rule engineers eventually internalise: recursion for tree-shaped data + bounded depth; iteration for flat data + big-N. When in doubt, ask "could the depth of this recursion be controlled by an adversary?" — if yes, iterate.

(e) Quiz + exercise · 10 min

1. What are the two mandatory pieces of any recursive function?
2. Why does naive fib(n) take O(2ⁿ) time while memoised fib(n) takes O(n)?
3. Explain what a "stack frame" is and why deep recursion can crash a program.
4. Give one concrete data shape where recursion is more natural than iteration, and one where it's less natural.
5. Why doesn't CPython perform tail-call optimisation, and what should you do instead for tail-recursive-looking code?

Stretch (connects to S026 — Stacks): Rewrite the recursive inorder(tree) traversal from the hands-on section as an iterative function using an explicit stack. Verify it produces the same output.

Explain-out-loud test

If you can't teach these 3 things to a friend without notes, redo the session:

1. What is Recursion? (one sentence, no jargon)
2. When would you use it? (one concrete example)
3. When would you NOT use it? (one anti-pattern)

What comes next

• Next session (S028): Trees & BSTs — Traversal (BFS/DFS)
• Previous (S026): Stacks & Queues — LIFO/FIFO in Practice
• Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: (a) intuition · (b) visual walkthrough · (c) hands-on · (d) production reality · (e) quiz + exercise. Duration: 60 minutes.