Recursion Basics

Concepts covered: Recursion

A loop handles nesting only as deep as the loops you wrote. An event payload with lists inside dicts inside lists, to a depth that varies from row to row, needs a function that treats each inner piece the way it treats the whole. A recursive function does that by calling itself on a smaller part of its own input.

Every recursive function has 2 parts. The base case answers directly, without calling itself, for input small enough to need no further splitting. The recursive case calls the function on a smaller piece and builds its answer from the result. Each call gets a frame of its own, with its own local variables, and a frame waits until the call it made returns.

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

print("5! =", factorial(5))
5! = 120

factorial(1) is the base case and returns 1 without calling anything. Then the frames close from the bottom up: factorial(2) returns 2 and factorial(3) returns 6. By the time factorial(5) returns 120, factorial(4) has already returned 24. Without the base case the calls would never stop descending.

Nested lists of any depth

def sum_nested(data):
    total = 0
    for item in data:
        if isinstance(item, list):
            total += sum_nested(item)
        else:
            total += item
    return total

nested = [1, [2, 3], [4, [5, 6]], 7]
print("Sum of nested:", sum_nested(nested))
Sum of nested: 28

The loop covers a single level, and the recursive call covers everything below it. A number is a leaf and adds itself; a list hands its contents to a fresh call. The base case here is implicit: a list holding no inner lists finishes its loop without calling sum_nested again. The same 8-line function sums [1, 2] or a list nested 40 levels deep, and for this input the total is 28.

Dicts and lists mixed together

Event payloads mix dicts and lists. The function below checks which kind of container it holds, recurses into every value inside it, and counts anything else as 1 leaf.

def count_leaves(node):
    if isinstance(node, dict):
        total = 0
        for key, value in node.items():
            total += count_leaves(value)
        return total
    if isinstance(node, list):
        total = 0
        for item in node:
            total += count_leaves(item)
        return total
    return 1

event = {
    "id": "evt_1",
    "customer": {"id": "cus_4", "address": {"city": "Dublin", "zip": "D02"}},
    "items": [{"sku": "A1", "qty": 2}, {"sku": "B7", "qty": 1}],
}
print(count_leaves(event))
print(count_leaves({"id": "evt_2", "items": []}))
print(count_leaves(7))

Output:

8
1
1

The empty items list contributes 0 because its loop never runs, and the bare 7 counts as 1 leaf because it falls through to the last return. No extra code handles either edge case; the structure of the function covers them.

What does this program print, line by line?

def show(data, depth):
    for item in data:
        if isinstance(item, list):
            show(item, depth + 1)
        else:
            print(item, depth)

show([1, [2, [3]], 4], 1)

The call stack has a ceiling

Every waiting frame takes memory, so Python caps how many can be open at once and raises RecursionError past the cap; sys.getrecursionlimit() reports the current cap. A missing or unreachable base case hits that ceiling within a fraction of a second. Nested payloads rarely go deeper than a few dozen levels, so recursion suits them. A chain of 100,000 records, each pointing to the next, belongs in a while loop.

Recursion meets a memo dict

A payload nests its amounts at different depths, and many of them share a currency. The walker below recurses through dicts and lists until it reaches a dict holding an amount, which is its base case, and converts that amount through cached_rate from the memoization section. Any other leaf, such as an id string, adds 0.

calls = 0
rate_cache = {}

def slow_rate(currency):
    global calls
    calls += 1
    table = {"eur": 108, "gbp": 127, "usd": 100}
    return table[currency]

def cached_rate(currency):
    if currency not in rate_cache:
        rate_cache[currency] = slow_rate(currency)
    return rate_cache[currency]

def total_usd(node):
    if isinstance(node, dict) and "amount" in node:
        return node["amount"] * cached_rate(node["currency"]) // 100
    total = 0
    if isinstance(node, dict):
        for key, value in node.items():
            total += total_usd(value)
    elif isinstance(node, list):
        for item in node:
            total += total_usd(item)
    return total

payload = {
    "id": "evt_7",
    "orders": [
        {"lines": [{"amount": 1000, "currency": "eur"}, {"amount": 500, "currency": "usd"}]},
        {"lines": [{"amount": 2000, "currency": "eur"}]},
    ],
    "shipping": {"amount": 300, "currency": "usd"},
}
print(total_usd(payload))
print("slow lookups:", calls)

Output:

4040
slow lookups: 2

The walker finds 4 amounts, 3 inside order lines and 1 directly under the payload, and returns 4040 US cents. The euro lines contribute 1080 and 2160; the dollar amounts add 500 and 300. Only 2 slow lookups ran, 1 per distinct currency, because the second euro amount found its rate already in rate_cache.

About this lesson

This section is part of the Functions: Advanced lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.