Lesson 15: Recursion and Functional Programming

Some problems are shaped like smaller copies of themselves: a folder contains folders, a family tree branches into family trees, the factorial of 5 is 5 times the factorial of 4. Recursion — a function calling itself on a smaller input — is the natural tool for those shapes, and it terrifies beginners only because it is usually taught without showing the machinery. This lesson shows the machinery, then pairs recursion with Python's functional toolkit (map, filter, lambdas, comprehensions) for the many jobs where it shines.

The two parts every recursive function needs

A recursive function requires a base case — an input so small the answer is immediate, with no further call — and a recursive case that shrinks the problem and calls itself. Miss the base case, or fail to shrink, and the calls never stop until Python's recursion limit (about 1,000 nested calls) raises RecursionError: maximum recursion depth exceeded.

def countdown(n):
    if n <= 0:
        print("Blast off!")
    else:
        print(n)
        countdown(n - 1)

countdown(3)

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

print(factorial(5))

Output:

3
2
1
Blast off!
120

countdown prints on the way *down*: 3, then the call for 2, then 1, then the base case fires "Blast off!". factorial computes on the way back *up*: factorial(0) returns 1 to factorial(1), which returns 1 × 1 = 1 to factorial(2), which returns 2 × 1 = 2, then 3 × 2 = 6, 4 × 6 = 24, 5 × 24 = 120. Nothing is magic — each call is an ordinary function invocation waiting for a smaller one to finish, stacked like plates. When a recursive function misbehaves, write this expansion out by hand for a tiny input; the bug almost always shows itself in the expansion.

When recursion is the wrong tool — inefficiency you can count

The textbook Fibonacci is recursion's cautionary tale. Naively implemented, fib(10) recomputes the same small values hundreds of times — the call tree repeats itself exponentially. Do not take that on faith; *count* the calls:

from functools import lru_cache

calls = 0

def fib_slow(n):
    global calls
    calls += 1
    if n < 2:
        return n
    return fib_slow(n - 1) + fib_slow(n - 2)

print(fib_slow(10), "took", calls, "calls")

@lru_cache(maxsize=None)
def fib_fast(n):
    if n < 2:
        return n
    return fib_fast(n - 1) + fib_fast(n - 2)

print(fib_fast(10))
print(fib_fast(50))

Output:

55 took 177 calls
55
12586269025

One hundred and seventy-seven calls to answer a question whose value is 55 — and it worsens ferociously (fib(30) takes over two million). The @lru_cache decorator changes everything with one line: it memoises the function, storing each computed result so repeat calls return instantly. fib_fast(50) — a value the naive version could not reach in reasonable time — answers immediately. Two professional morals: measure before optimising (the counter took three lines), and know that recursion plus memoisation (called dynamic programming in its fuller form) turns many "impossible" problems routine.

Worked example 1 — summing a nested structure

Loops iterate flat sequences; nested data — lists inside lists, like folder trees, comment threads or grouped scores — is recursion's home ground. The function's job: add every number, however deep:

def total(data):
    """Sum every number in a nested list structure."""
    s = 0
    for item in data:
        if isinstance(item, list):
            s += total(item)
        else:
            s += item
    return s

print(total([1, [2, 3], [4, [5, 6]], 7]))

Output: 28. Trace the division of labour: the loop handles the *width* of each level, the recursion handles the *depth*. When an item is a list, total(item) fully prices that subtree before the loop moves on — 1, then [2, 3] contributes 5, then [4, [5, 6]] contributes 4 + 11 = 15, then 7: 1 + 5 + 15 + 7 = 28. The base case is implicit but real: a list containing no sublists never recurses, and an empty list sums to 0 through the loop alone. isinstance doing type-directed branching like this is the standard shape of tree-processing code everywhere.

The functional toolkit: map, filter, lambdas

Recursion transforms *structures*; the functional tools transform *collections* declaratively — you describe what you want, not the loop mechanics. A lambda is a small anonymous function (lambda s: s + 5); map applies a function to every element; filter keeps elements where a function returns True:

scores = [45, 82, 91, 67, 88]
passed = list(filter(lambda s: s >= 50, scores))
curved = list(map(lambda s: s + 5, scores))
print(passed)
print(curved)

words = ["banana", "fig", "apple", "kiwi"]
print(sorted(words, key=len))

it = map(lambda s: s + 5, scores)
print(list(it))
print(list(it))

Output:

[82, 91, 67, 88]
[50, 87, 96, 72, 93]
['fig', 'kiwi', 'apple', 'banana']
[50, 87, 96, 72, 93]
[]

Every line earns its place. filter with a threshold predicate keeps the four passing scores in order; map rebuilds the list with a curve applied; sorted(words, key=len) ranks by a function of each element — the key-function idea you have used since Lesson 5, here with a built-in. And the final pair of lines demonstrates the gotcha that bites everyone once: map and filter return iterators, one-shot streams. Consuming it into a list exhausts it; the second list(it) is [] — not an error, just emptiness, which makes the bug sneaky. Wrap results in list(...) immediately (comprehensions, [s + 5 for s in scores], do exactly that and are usually clearer) and never "save" a bare map object for later.

Common mistakes

• No base case, or input that never shrinks. factorial(n) calling factorial(n) out of a copying slip recurses until RecursionError. Test recursive functions on the smallest inputs first (0, 1, empty list) — that is where the base case proves itself.
• Recursing where a loop is simpler. Summing a flat list recursively works but wastes memory and risks the depth limit at ~1,000 elements; sum() or a loop is the right tool. Recursion is for self-similar *structure*, not for counting.
• Treating a map/filter object as a list. Printing it shows <map object at 0x...>; len() fails; a second pass yields nothing. Convert immediately.
• Over-lambda-ing. A lambda spanning logic you cannot read at a glance deserves a named def — the name becomes documentation, and Lesson 17's tests can target it.

Real-World Challenge

The task. A folder structure stored as nested dictionaries (folder names map to either a sub-dictionary or a file's None) needs searching: find every file with a given extension, wherever it is buried. Iteration alone cannot know the depth in advance — this is recursion's exact home.

Worked solution.

def find_files(tree, extension):
    """Collect the names of all files ending with extension, recursively."""
    found = []
    for name, contents in tree.items():
        if isinstance(contents, dict):
            found.extend(find_files(contents, extension))
        elif name.endswith(extension):
            found.append(name)
    return found

school = {
    "notes.txt": None,
    "Maths": {"algebra.pdf": None, "geometry.pdf": None, "plan.txt": None},
    "Science": {"Biology": {"cells.pdf": None}},
}
result = sorted(find_files(school, ".pdf"))
print(result)
print(len(result), "PDF files")

Output:

['algebra.pdf', 'cells.pdf', 'geometry.pdf']
3 PDF files

How it works. The function mirrors total from the worked example: loop across the current level, recurse into anything that is a container. A dictionary value means "folder — search inside and extend the findings" (extend adds the sub-results *into* the list; append would nest a list inside it, corrupting the shape). Anything else is a file, kept when its name matches the extension. Files hide one, two and three levels deep here — cells.pdf sits inside Science → Biology — and the recursion neither knows nor cares: the base case is any level with no subfolders, reached naturally. Sorting at the end gives a deterministic report regardless of dictionary traversal order, the same discipline Lesson 11 applied to task listings.

Extension. Grow the finder into a tree reporter: print the structure indented by depth (pass a depth parameter defaulting to 0 and print " " * depth + name), folder names first, with a running count of files and folders. The recursive call passes depth + 1 — the shrink-and-carry pattern in its purest form.

Going further — recursion on text, and divide and conquer

Strings are self-similar too: a word is its first letter plus a smaller word, which makes text a natural recursion playground and a gentle route into divide and conquer — solve the smallest piece, trust the recursion on the rest:

def reverse(text):
    if len(text) <= 1:
        return text
    return reverse(text[1:]) + text[0]

def is_palindrome(text):
    if len(text) <= 1:
        return True
    if text[0] != text[-1]:
        return False
    return is_palindrome(text[1:-1])

print(reverse("python"))
print(is_palindrome("racecar"), is_palindrome("python"))

Output:

nohtyp
True False

reverse peels the first character, reverses the remainder (trusting the recursive call completely — the mental leap every recursion learner must make), and appends the peeled letter at the end. is_palindrome compares the two ends and recurses inward only while they match, exiting early on the first mismatch; its base case covers both the empty string and the single middle character of odd-length words. Honesty about cost belongs here too: each slice text[1:] copies the string, so reverse does more total copying than a loop or the built-in reversed would — clarity and efficiency genuinely trade off, and naming that trade-off (rather than pretending recursion is free) is part of thinking like an engineer. Python also makes no tail-call optimisation, unlike some languages, so deep recursion is bounded by the recursion limit regardless of how the calls are arranged.

Practice corner — comprehensions say the same thing shorter

The map/filter examples translate word-for-word into comprehensions — apply-and-keep in one expression, with no lambda bookkeeping:

scores = [45, 82, 91, 67, 88]
print([s + 5 for s in scores])
print([s for s in scores if s >= 50])

Output:

[50, 87, 96, 72, 93]
[82, 91, 67, 88]

Identical results to the functional versions — verify them against the main lesson's outputs, because that cross-check is the point: the comprehension is not a different computation, it is the same one in Python's preferred notation, and it returns a real list immediately (no iterator-exhaustion trap). Style guidance in one line: use a comprehension when the transformation fits on one readable line; graduate to an explicit loop the moment a second condition or a side effect appears, because clarity outranks brevity at exactly that point.