Functional & recursion theory

1 · Closures — free variables & cells

Here's a moment you've probably had without a name for it. You needed a little function that "remembers" something — a running total, a rate limiter that knows how many calls are left, a callback that needs one config value — and your instinct said "I'll write a class for this." A whole class, with __init__ and self and a method, just to hold one number between calls. It works, but it feels like renting a truck to carry a sandwich. A closure is the sandwich-sized answer: a function that quietly carries a little private memory with it, no class required.

The everyday analogy is a backpack. When you define a function inside another function, the inner function walks away with a backpack containing the outer function's variables it actually used. It can reach into that backpack later — long after the outer function has returned and its floor of the building has been demolished — because the variables it needs were packed away, not left behind on the stack. That "the variable outlives the function that created it" is the whole trick, and it's why counters, accumulators, and pre-configured callbacks can be built out of nothing but functions.

Why this matters beyond cuteness: closures are the machinery under decorators, under functools.partial, under most callback-based APIs, and under the late-binding bug in the very next section. If closures are fuzzy, all of those stay fuzzy too. And the common mistake is assuming the closure copied the value — it did not. It captured the variable itself (a shared box CPython calls a cell), so if that variable changes later, the closure sees the new value. Hold onto that distinction; it is the single most misunderstood thing about closures and it causes real production bugs.

A closure is a nested function together with the enclosing variables it references — its free variables. CPython stores each captured variable in a cell shared between the outer and inner functions, so the inner function keeps that state alive after the outer returns. Each call to the factory creates fresh cells, so closures have independent state. nonlocal lets the inner function rebind the captured name rather than shadow it with a new local.

closures.py# A closure is a function plus the enclosing variables it captures ("free vars").
def make_counter():
    count = 0                       # a free variable for the inner function
    def inc():
        nonlocal count              # rebind the enclosing name, don't shadow it
        count += 1
        return count
    return inc

c1, c2 = make_counter(), make_counter()
print(c1(), c1(), c1())             # 1 2 3   -> each closure has its OWN cell
print(c2())                         # 1       -> independent state

# Introspection: free variables live in code.co_freevars and in __closure__ cells
print("free vars:", make_counter().__code__.co_freevars)   # ('count',)
print("has closure cells:", make_counter().__closure__ is not None)

1 2 3
1
free vars: ('count',)
has closure cells: True

2 · The late-binding gotcha

This is the bug that makes you doubt your own sanity. You write a clean little loop that builds three callbacks — one per item — and every single one, when you finally run it, does the same thing: it uses the last item. Not the item it was "supposed" to. You stare at it. You add print statements. The loop is obviously iterating over 0, 1, 2 — you can see it — yet all three functions insist the answer is 2. Nearly every Python engineer meets this at least once, usually in event handlers, retry callbacks, or a list of partially-applied jobs, and usually in production rather than in a tutorial where it would have been harmless.

Here is the plain-language reason, and it flows directly from the backpack idea in §1. The three closures did not each pack their own copy of i. They all packed a reference to the same box — the one variable i that the loop keeps overwriting. Think of three people who each wrote down "check the whiteboard for the number" instead of copying the number down. The loop kept erasing and rewriting the whiteboard, and by the time anyone actually looks, the whiteboard says 2. The closures were never wrong; they faithfully read the shared box at call time, and by call time the loop had long since finished and left its final value there.

The mistake to name: "the loop variable is captured by value." It is not — it is captured by reference, and the read happens late (hence late binding). Once you internalize that, the fix is obvious rather than magical: force each closure to write the number down now, at definition time. The two idioms below both do exactly that — a default argument (defaults are evaluated once, at def time, and stored on the function) or a factory function that closes over its own fresh parameter. Both give each closure its own private box instead of a shared whiteboard.

Closures capture the variable, not the value it had when the closure was created. So building lambdas in a loop that all reference the loop variable makes them all see its final value — a bug that bites everyone once. The idiomatic fix is to bind the current value as a default argument (defaults are evaluated at definition time), or to close over a parameter via a factory function.

late_binding.py# The late-binding gotcha: closures capture the VARIABLE, not its value-at-creation.
funcs = [lambda: i for i in range(3)]
print("late binding:", [f() for f in funcs])   # [2, 2, 2]  (all see final i)

# Fix 1: bind the current value as a default argument (evaluated at def time)
fixed = [lambda i=i: i for i in range(3)]
print("default-arg fix:", [f() for f in fixed])# [0, 1, 2]

# Fix 2: a factory that closes over its own parameter
def make(i):
    return lambda: i
fixed2 = [make(i) for i in range(3)]
print("factory fix:", [f() for f in fixed2])   # [0, 1, 2]

late binding: [2, 2, 2]
default-arg fix: [0, 1, 2]
factory fix: [0, 1, 2]

3 · Pure functions & immutability

Think about a vending machine versus a slot machine. Press B4 on a vending machine and you get the same granola bar every time — same input, same output, and nothing about the machine's mood or the time of day changes that. A slot machine takes the same coin and does something different each pull, and it quietly changes the world (your balance, the jackpot) as a side effect. A pure function is the vending machine: given the same arguments it always returns the same answer, and it touches nothing outside itself. That reliability sounds like a nice-to-have until the day an impure function ruins your afternoon.

And it will. The reason purity earns a whole section is that impurity is where the spooky bugs live — the ones that pass every unit test and then misbehave only in production, only sometimes, only under load. A function that reads a global, or mutates the list you handed it, or depends on the current time, works perfectly in isolation and then does something different when a second caller, a second thread, or a cache gets involved. Pure functions have none of that: you can call them in any order, from any thread, cache their results, and reason about them by just reading the code. Purity is what makes the memoization in §7 correct, makes testing a one-liner (no setup, no mocks), and makes the parallel data pipeline in the ladder safe.

The classic mistake — and it is a rite of passage — is the mutable default argument. You write def f(item, bucket=[]) expecting a fresh empty list every call. But that [] is evaluated once, when the def line runs, and the same list object is reused on every future call — so it silently accumulates state, like a "clean" plate that's actually the same plate handed to every diner. It is the impurity of §1's shared-cell idea wearing a different hat: one object, secretly shared, mutated behind your back. The cure is the None-sentinel habit shown below, and once it's muscle memory you'll never write the bug again.

A pure function returns the same output for the same inputs and has no side effects — it does not mutate arguments, globals, or the outside world. Purity is what makes memoization correct, testing trivial, and parallelism safe. Its opposite shows up in the notorious mutable default argument: a default list is created once and shared across calls, so it accumulates state across invocations.

pure.py# A PURE function: output depends only on inputs, and it mutates nothing external.
def pure_add_tax(price, rate):
    return round(price * (1 + rate), 2)      # no side effects, deterministic

# An IMPURE function: mutates its argument (a side effect) -> surprises callers.
def impure_append(item, bucket=[]):          # classic mutable-default bug!
    bucket.append(item)
    return bucket

print(pure_add_tax(100, 0.2))                # 120.0  (same input -> same output)
print(pure_add_tax(100, 0.2))                # 120.0
print(impure_append(1))                      # [1]
print(impure_append(2))                      # [1, 2]  <- shared default persists!

# The fix for the mutable default:
def safe_append(item, bucket=None):
    bucket = [] if bucket is None else bucket
    bucket.append(item)
    return bucket
print(safe_append(1), safe_append(2))        # [1] [2]

120.0
120.0
[1]
[1, 2]
[1] [2]

4 · Higher-order functions

You already trust higher-order functions in real life — you just don't call them that. When you tell a contractor "for each room, do whatever this checklist says," you're handing over a set of instructions (a function) to be applied by something else. When you give a recipe card to a friend and say "run this on those vegetables," you're passing behavior, not just data. In Python, functions are ordinary first-class values — you can put one in a variable, drop it in a list, pass it into another function, or hand one back as a result — and a higher-order function is simply one that takes or returns a function. That's the entire concept; the rest is vocabulary.

Why does treating functions as data matter enough to teach on its own? Because it lets you separate the what from the how. map knows how to walk a sequence; you supply the "what to do to each item." filter knows how to keep-or-drop; you supply the test. reduce knows how to fold a whole sequence down to one value; you supply the combining step. This is exactly how you plug your own scoring function into a re-ranker, your own validator into a pipeline, or your own tool into an agent loop — the framework provides the machinery, you provide the behavior. And returning a function (a closure, from §1) is how decorators, configurable adders, and pre-wired callbacks get built.

Two mistakes to sidestep. First, map and filter return lazy iterators, not lists — nothing actually runs until you consume them, so a bare map(...) that you never iterate does nothing, and printing it shows a <map object> rather than results (wrap it in list() to force it). Second, don't reach for map+filter+lambda when a comprehension says the same thing more clearly: for a simple transform-and-filter, [x*x for x in nums if x%2] reads better and runs at least as fast. Save map/filter for when you already have a named function to pass, or when you genuinely want the lazy iterator to stream a large source without materializing it.

Functions are first-class values: you can store them, pass them as arguments, and return them. A higher-order function does one of the last two. map and filter take a function and an iterable and return lazy iterators; reduce folds a sequence to one value. Returning a function is how decorators, adders, and configurable callbacks are built.

hof.pyfrom functools import reduce

nums = [1, 2, 3, 4, 5]

# map / filter are lazy iterators; wrap in list() to materialize.
print("map    :", list(map(lambda x: x * x, nums)))        # [1, 4, 9, 16, 25]
print("filter :", list(filter(lambda x: x % 2 == 0, nums)))# [2, 4]
print("reduce :", reduce(lambda a, b: a + b, nums, 0))     # 15

# The Pythonic equivalents are comprehensions (usually clearer & as fast):
print("comp   :", [x * x for x in nums if x % 2])          # [1, 9, 25]

# Higher-order: a function that RETURNS a function (a decorator-style adder).
def adder(n):
    def add(x): return x + n
    return add
add10 = adder(10)
print("hof    :", add10(5))                                # 15

map    : [1, 4, 9, 16, 25]
filter : [2, 4]
reduce : 15
comp   : [1, 9, 25]
hof    : 15

5 · Recursion, the call stack & no TCO

Picture standing between two mirrors. You see yourself, holding a reflection of yourself, holding a reflection of yourself, on and on — each image nested inside the last. Recursion is a function that solves a problem by calling itself on a smaller version of the same problem, and those nested calls are exactly like those nested reflections. It's the most natural way to describe anything tree-shaped: a folder full of folders, a comment thread of replies to replies, a nested JSON blob. You say "process this node, then process each child the same way," and the structure does the bookkeeping for you.

But there's a physical cost the mirror analogy hides, and it's the point of this section. Every time one function calls another, Python sets aside a little workspace called a frame — a note of the arguments, the local variables, and where to return when the call finishes. Those frames pile up on the call stack, one per pending call, and they aren't cleaned up until each call returns. So a recursion that's 50,000 levels deep needs 50,000 frames sitting in memory simultaneously, like 50,000 half-finished tasks on your desk, none of which you can file until the innermost one completes. To stop a runaway recursion from crashing the whole interpreter, Python caps this at a default depth of 1000 and raises a clean RecursionError instead.

Now the mistake that catches experienced engineers — especially anyone coming from Lisp, Scheme, or a functional language. There, a "tail call" (when the recursive call is the very last thing the function does) is optimized away: the interpreter reuses the current frame instead of stacking a new one, so tail recursion runs in constant stack space forever. It is tempting to assume Python does the same. It does not. CPython performs no tail-call optimization — a tail call still allocates a fresh frame just like any other call, so even a perfectly tail-recursive countdown blows the stack at depth. This was a deliberate design decision (frames are what make tracebacks readable), not an oversight. The takeaway: in Python, don't lean on recursion for anything that can go deep — reach for a loop, or the explicit stack you'll build in §6.

Each function call pushes a frame onto the call stack (arguments, locals, return address). Recursion just calls the same function again, stacking frames until a base case unwinds them. Python caps recursion depth (default 1000) to catch runaway recursion before it exhausts the C stack. Crucially, CPython performs no tail-call optimization: even a function whose recursive call is the last thing it does still allocates a new frame, so deep recursion raises RecursionError.

recursion.pyimport sys

# Recursion uses the call stack: each call adds a frame. Python does NOT optimize
# tail calls, so recursion depth is bounded by the recursion limit.
print("recursion limit:", sys.getrecursionlimit())   # 1000 by default

def factorial(n):
    return 1 if n == 0 else n * factorial(n - 1)      # not tail-optimized either
print("factorial(10):", factorial(10))                # 3628800

# Even a perfectly tail-recursive function blows the stack — no TCO in CPython:
def count_down(n):
    if n == 0:
        return "done"
    return count_down(n - 1)                          # tail call, still a new frame

try:
    count_down(100_000)
except RecursionError:
    print("RecursionError: CPython has no tail-call optimization")

recursion limit: 1000
factorial(10): 3628800
RecursionError: CPython has no tail-call optimization

6 · Recursion → explicit stack

Here's the fix for the crash you just met in §5, and it's more clever than it first sounds. When recursion overflows, the reflex is to bump sys.setrecursionlimit higher — and that's a trap, because the real limit is the fixed-size C stack underneath, and pushing past it segfaults the whole process instead of raising a catchable error. The professional move is different: stop letting Python manage the stack for you, and manage one yourself. It turns out the call stack was never magic — it was just a stack — so you can replace it with an ordinary list that you push and pop by hand.

The analogy that makes this click: recursion is like reading a book and, every time you hit a footnote, immediately flipping to it — and if that footnote has its own footnote, flipping again, keeping every page held open with a finger. Run out of fingers and you're stuck. The explicit-stack version is keeping a to-read list on a notepad instead: jot down each footnote you encounter, finish your current line, then pop the next item off the notepad when you're ready. Same pages get read, same order if you want it — but now your "how deep can I go" limit is how much paper you have (memory, on the heap), not how many fingers (frames, on the tiny call stack).

That shift buys you three things worth naming. First, no RecursionError — a 50,000-deep structure is no harder than a 5-deep one, because the notepad grows on the heap. Second, control: because you own the loop, you can pause and resume, cap the work, or swap traversal order just by changing how you push and pop. Third, honesty about cost — the memory that recursion was quietly spending on frames is now visible as the size of your list. The one subtlety to watch (the common mistake): a stack reverses order, so if left-to-right traversal matters, push children in reverse so they pop back in the order you meant — exactly the reversed() detail you'll see in the DFS exercise later.

Any recursion can be rewritten with an explicit stack (a list) that you push and pop yourself. The work then lives on the heap instead of the call stack, so it is bounded only by memory — no RecursionError, and you can pause/resume or change traversal order at will. This is the standard fix when a tree or nested structure can be arbitrarily deep.

explicit_stack.py# Convert recursion to an EXPLICIT stack -> no depth limit, iterative control.
def sum_nested_recursive(x):
    if isinstance(x, int):
        return x
    return sum(sum_nested_recursive(c) for c in x)

def sum_nested_iterative(root):
    total, stack = 0, [root]
    while stack:                    # our own stack on the heap, not the call stack
        node = stack.pop()
        if isinstance(node, int):
            total += node
        else:
            stack.extend(node)      # push children
    return total

data = [1, [2, 3, [4, 5]], 6]
print("recursive:", sum_nested_recursive(data))   # 21
print("iterative:", sum_nested_iterative(data))   # 21

# The iterative version handles arbitrarily deep nesting without RecursionError.
deep = 1
for _ in range(50_000):
    deep = [deep]                    # 50k-deep nesting
print("deep sum:", sum_nested_iterative(deep))     # 1

recursive: 21
iterative: 21
deep sum: 1

7 · Memoization & complexity

Watch a child compute Fibonacci by hand and you'll see the waste instantly. To get fib(5) they compute fib(4) and fib(3); but fib(4) re-computes fib(3) all over again, and fib(3) re-computes fib(2), which has already been worked out on another branch — the same subproblems solved again and again, an entire branching tree of duplicated effort. It's like a student who, every time they need a fact, re-derives it from scratch instead of jotting it in the margin. The tree of calls grows exponentially; asking for fib(50) naively will out-wait your patience.

Memoization is simply "write the answer in the margin." The first time you compute fib(n), you stash the result in a lookup table keyed by n; every later request for that same n is a table read instead of a recomputation. That one habit collapses the exponential call tree into a straight line — each value is computed exactly once, so an O(φn) disaster becomes O(n) time, at the cost of O(n) space to hold the table. This is the seed of dynamic programming, and it's the same trick prompt-caching and RAG result-caching use at a larger scale: pay once, remember, reuse. Python hands it to you as a single decorator, functools.lru_cache, so you rarely write the table by hand.

But the decorator is a loaded gun if you forget §3. Memoization is only correct for pure functions with hashable arguments — because a cache is a bet that "same inputs mean same output," and that bet only pays off if the function has no hidden dependence on time, randomness, global state, or mutable inputs. The classic mistakes: caching a function that reads a database or the clock (you serve stale answers forever), passing a mutable argument like a list (it's unhashable and raises TypeError, or worse, the key stops reflecting the value after mutation), or caching a per-user result and leaking one user's data to another. And leaving maxsize=None on a hot path is a slow memory leak. Cache the pure core, pass tuples/frozensets, bound the size — then reap the speedup safely.

Memoization caches a pure function's results so repeated inputs are returned instantly. On naive recursive Fibonacci it collapses an exponential O(φn) call tree into linear O(n) time (each n computed once) at O(n) space. functools.lru_cache does this in one decorator — but only correctly for pure functions with hashable arguments.

memoization.pyfrom functools import lru_cache
import time

# Naive Fibonacci is exponential: O(phi^n) calls (recomputes the same subproblems).
def fib_slow(n):
    return n if n < 2 else fib_slow(n - 1) + fib_slow(n - 2)

# Memoized: each n computed once -> O(n) time, O(n) space. Requires a PURE function.
@lru_cache(maxsize=None)
def fib_fast(n):
    return n if n < 2 else fib_fast(n - 1) + fib_fast(n - 2)

print("fib_fast(30):", fib_fast(30))      # 832040
print("cache:", fib_fast.cache_info())    # hits/misses show the reuse

# fib_slow(35) is already noticeably slow; fib_fast(100) is instant:
print("fib_fast(100):", fib_fast(100))    # 354224848179261915075

fib_fast(30): 832040
cache: CacheInfo(hits=28, misses=31, maxsize=None, currsize=31)
fib_fast(100): 354224848179261915075

8 · Partial application & currying

You do this every day at the coffee shop without thinking. The full "function" is make a drink, which takes a size, a type, and a milk. But you don't re-specify all three each morning — you have "your usual," a version with most of the arguments pre-filled, so you only say what's left. Partial application is that: you take a general function, lock in some of its arguments, and get back a new, more specialized function that needs only the rest. square is just power with the exponent pinned to 2; log_error is just print with the "[ERROR]" prefix pinned. Nothing new is computed — you're just making a convenient, pre-configured handle onto an existing function.

The reason this is worth a section rather than a footnote is that it's the clean answer to a smell you'll otherwise create: passing the same configuration argument through five layers of calls, or writing five nearly-identical wrapper functions that differ by one constant. Instead of threading a rate or a client or a prefix everywhere, you bake it in once with functools.partial and hand around the specialized function. It shines for pre-configuring callbacks (an event system wants a zero-argument function, but your handler needs context — partial supplies the context now, the event supplies the rest later) and for API wrappers where the endpoint or auth is fixed but the payload varies.

Currying is the closely related idea from functional languages: rather than fixing some arguments, you rewrite an n-argument function as a chain of one-argument functions, so f(a, b) becomes f(a)(b) — each call takes one argument and hands back a function waiting for the next. In Python you build it by hand with nested closures (there it is, §1 again). The common confusion to clear up: partial application and currying are not the same thing — partial fixes arguments to shrink the arity, currying reshapes the calling convention into single-argument steps. In practice, Python engineers reach for partial constantly and hand-rolled currying rarely, but knowing both lets you read functional code and pick the lighter tool for the job.

Partial application fixes some of a function's arguments to produce a new, more specialized function. functools.partial is the standard tool — great for pre-configuring callbacks and API wrappers. Currying is the related idea of turning an n-argument function into a chain of one-argument functions, which you can do by hand with nested closures.

partial.pyfrom functools import partial

def power(base, exponent):
    return base ** exponent

# partial application: pre-fill some arguments to make a specialized function.
square = partial(power, exponent=2)
cube   = partial(power, exponent=3)
print("square(5):", square(5))     # 25
print("cube(2):", cube(2))         # 8

# "Currying" by hand: turn f(a, b) into f(a)(b) via nested closures.
def curry_add(a):
    return lambda b: a + b
print("curried:", curry_add(3)(4)) # 7

# partial is common for pre-configuring callbacks / API wrappers:
log_error = partial(print, "[ERROR]")
log_error("disk full")             # [ERROR] disk full

square(5): 25
cube(2): 8
curried: 7
[ERROR] disk full

def make_counter():
    count = 0
    def inc():
        nonlocal count
        count += 1
        return count
    return inc

a, b = make_counter(), make_counter()
print(a(), a(), a())   # 1 2 3
print(b())             # 1  (independent)

1 2 3
1

def buggy(item, bucket=[]):
    bucket.append(item); return bucket
print(buggy(1))   # [1]
print(buggy(2))   # [1, 2]  <- shared!

def fixed(item, bucket=None):
    bucket = [] if bucket is None else bucket
    bucket.append(item); return bucket
print(fixed(1))   # [1]
print(fixed(2))   # [2]

[1]
[1, 2]
[1]
[2]

def down(n):
    if n == 0: return 'done'
    return down(n - 1)          # tail call, but a NEW frame

try:
    down(100_000)
except RecursionError:
    print('overflowed: no TCO')

def down_iter(n):
    while n:                     # same logic, constant stack
        n -= 1
    return 'done'
print(down_iter(100_000))        # done

overflowed: no TCO
done

def leaves_rec(x, out=None):
    out = [] if out is None else out
    if isinstance(x, int): out.append(x)
    else:
        for c in x: leaves_rec(c, out)
    return out

def leaves_iter(root):
    out, stack = [], [root]
    while stack:
        node = stack.pop()
        if isinstance(node, int): out.append(node)
        else: stack.extend(reversed(node))   # preserve left-to-right DFS
    return out

t = [1, [2, [3, 4]], 5]
print(leaves_rec(t))    # [1, 2, 3, 4, 5]
print(leaves_iter(t))   # [1, 2, 3, 4, 5]
deep = 1
for _ in range(50_000): deep = [deep]
print(leaves_iter(deep))# [1]  (no RecursionError)

[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]
[1]

from functools import lru_cache

@lru_cache(maxsize=1024)
def score(user, item):           # pure: depends only on its args
    return (hash((user, item)) % 1000) / 1000.0

for _ in range(3):
    score('u1', 'i1'); score('u1', 'i2')
print(score.cache_info())        # hits=4, misses=2, currsize=2

CacheInfo(hits=4, misses=2, maxsize=1024, currsize=2)

from functools import reduce

def normalize(rec):            # pure
    return {**rec, 'name': rec['name'].strip().lower()}

def is_valid(rec):             # pure predicate
    return rec.get('score') is not None

def process(batch):
    cleaned = (normalize(r) for r in batch)          # map, lazy
    valid = [r for r in cleaned if is_valid(r)]      # filter
    total = reduce(lambda acc, r: acc + r['score'], valid, 0)  # fold
    return valid, total

batch = [{'name': ' Ada ', 'score': 3}, {'name': 'Bo', 'score': None},
         {'name': 'CE', 'score': 5}]
records, total = process(batch)
print(len(records), total)     # 2 8

2 8