lesson 75 Advanced Functions & Recursion · intermediate

Recursion over nested data

Categories contain categories; folders contain folders. A function that calls itself on each child handles any depth, as long as it has a base case that stops.

You'll be able to

Solve a nested problem by handling one level and calling the same function on each child
Identify the base case, the data with no children where the recursion stops
Know that Python stops very deep recursion with RecursionError, and prefer a loop for long flat chains

The idea

A shop's categories nest: *Electronics* contains *Audio*, which could contain *Headphones*, and nobody knows in advance how deep it goes. A loop handles one level; a loop inside a loop handles two. To handle any depth, write a function that handles one category and calls itself for each subcategory.

Two parts make it work. The recursive step solves the problem for one level by combining that level with the answers for its children. The base case is a category with no children: the loop over children doesn't run, so the function returns without calling itself again.

Run each example to see what it prints. Running examples doesn't count toward progress.

example-1.py · Count the products in a category tree

def count_products(category):
    total = len(category["products"])
    for child in category["children"]:
        total += count_products(child)
    return total

catalog = {
    "name": "All",
    "products": [],
    "children": [
        {"name": "Electronics", "products": ["Organic Speaker"], "children": [
            {"name": "Audio", "products": ["Studio Headphones", "Pocket Radio"], "children": []},
        ]},
        {"name": "Home", "products": ["Deluxe Vase", "Nordic Candle"], "children": []},
    ],
}
print(count_products(catalog))
departments = catalog["children"]
print(count_products(departments[0]))

The answer can be a list as well as a number. Here each call returns the paths of the files in one folder and below it. The path so far is passed down as a parameter, so every level knows where it is. extend adds every item of another list to the end of this one.

example-2.py · Every file path in a folder tree

def file_paths(folder, prefix):
    here = prefix + folder["name"] + "/"
    paths = [here + name for name in folder["files"]]
    for sub in folder["folders"]:
        paths.extend(file_paths(sub, here))
    return paths

tree = {"name": "docs", "files": ["notes.txt"], "folders": [
    {"name": "2025", "files": ["report.csv", "budget.csv"], "folders": []},
    {"name": "photos", "files": [], "folders": [
        {"name": "trip", "files": ["beach.jpg"], "folders": []},
    ]},
]}
for path in file_paths(tree, ""):
    print(path)

Every call waits for the calls it makes, and Python keeps a frame in memory for each waiting call. To protect the program, it stops at a limit of about 1,000 nested calls with RecursionError. A function with no base case, or one whose input never gets smaller, always hits it.

example-3.py · A recursion that never stops

def depth_of(level):
    return depth_of(level - 1)

print(depth_of(3))

When to use it: trees of unknown depth: categories, folders, comment threads, nested JSON. Real trees are rarely more than a few dozen levels deep, far below the limit. When a loop is better: a long, flat chain, such as a linked list of 10,000 events, or simple counting. Recursing once per item there hits the limit, and a for or while loop does the same job with no depth at all. Mistakes to avoid: a missing or unreachable base case; forgetting to return (or add up) the result of the recursive call; and building the result in a list defined outside the function, which keeps growing between calls.

Review

A recursive function handles one level and calls itself on each child; the base case (no children) stops it.
Return and combine the results of the recursive calls; pass information down as parameters.
Python stops at about 1,000 nested calls with RecursionError; use a loop for long flat chains.
Next module: Python's collections and itertools, ready-made tools for counting, grouping and combining.

Practise this