Case Study: How File Systems and HTML Documents Are Recursive Structures

The Insight

Some of the most important data structures in computing are recursive by nature. Not because a programmer decided to make them recursive — because the problem they represent is inherently self-similar. A folder can contain files and other folders. An HTML element can contain text and other HTML elements. A comment on Reddit can have replies, each of which can have replies.

In this case study, we'll explore two ubiquitous recursive structures — file systems and HTML documents — and write recursive Python code to process them. The goal is to build your intuition for recognizing recursion in the wild.

Part 1: The File System

Why File Systems Are Recursive

A file system is a tree structure: - A directory (folder) can contain files and other directories. - Each sub-directory can contain files and more sub-directories. - This nesting can go arbitrarily deep.

The recursive definition: a directory is a collection of files and directories. A directory contains things of its own type. That's recursion.

Exploring a Directory Tree

Here's a practical program that mimics the Unix tree command — it displays the full structure of a directory:

"""Recursive directory tree display — like the Unix 'tree' command."""
import os


def show_tree(path, prefix="", max_depth=None, current_depth=0):
    """Recursively display a directory tree.

    Args:
        path: The directory path to display.
        prefix: The string prefix for tree-drawing characters.
        max_depth: Maximum depth to traverse (None = unlimited).
        current_depth: Current recursion depth (internal use).
    """
    if max_depth is not None and current_depth > max_depth:
        return

    # Get and sort directory contents
    try:
        entries = sorted(os.listdir(path))
    except PermissionError:
        print(f"{prefix}[Permission denied]")
        return

    # Separate directories and files
    dirs = [e for e in entries if os.path.isdir(os.path.join(path, e))]
    files = [e for e in entries if os.path.isfile(os.path.join(path, e))]

    # Display files first
    for f in files:
        size = os.path.getsize(os.path.join(path, f))
        size_str = format_size(size)
        print(f"{prefix}{f}  ({size_str})")

    # Display directories (with recursion)
    for i, d in enumerate(dirs):
        is_last = (i == len(dirs) - 1)
        connector = "└── " if is_last else "├── "
        print(f"{prefix}{connector}{d}/")

        # Recurse into subdirectory
        extension = "    " if is_last else "│   "
        show_tree(
            os.path.join(path, d),
            prefix + extension,
            max_depth,
            current_depth + 1,
        )


def format_size(bytes_count):
    """Format a file size in human-readable form."""
    for unit in ["B", "KB", "MB", "GB"]:
        if bytes_count < 1024:
            return f"{bytes_count:.0f} {unit}" if unit == "B" else f"{bytes_count:.1f} {unit}"
        bytes_count /= 1024
    return f"{bytes_count:.1f} TB"


# Example usage (adjust path to a directory on your system):
if __name__ == "__main__":
    # Create a sample directory structure for demonstration
    import tempfile
    import shutil

    demo_dir = os.path.join(tempfile.gettempdir(), "recursion_demo")

    # Clean up if it exists from a previous run
    if os.path.exists(demo_dir):
        shutil.rmtree(demo_dir)

    # Build a sample structure
    os.makedirs(os.path.join(demo_dir, "src", "utils"))
    os.makedirs(os.path.join(demo_dir, "src", "models"))
    os.makedirs(os.path.join(demo_dir, "tests"))
    os.makedirs(os.path.join(demo_dir, "docs"))

    # Create some files
    files_to_create = [
        ("README.md", "# My Project\nA sample project.\n"),
        ("src/main.py", "def main():\n    print('Hello')\n"),
        ("src/utils/helpers.py", "def add(a, b):\n    return a + b\n"),
        ("src/utils/config.py", "DEBUG = True\n"),
        ("src/models/user.py", "class User:\n    pass\n"),
        ("tests/test_main.py", "def test_main():\n    assert True\n"),
        ("docs/guide.md", "# User Guide\nHow to use this.\n"),
    ]
    for filepath, content in files_to_create:
        full_path = os.path.join(demo_dir, filepath)
        with open(full_path, "w") as f:
            f.write(content)

    print(f"Directory tree for: {demo_dir}")
    print("=" * 50)
    show_tree(demo_dir)

    # Clean up
    shutil.rmtree(demo_dir)

Expected output (file sizes may vary slightly):

Directory tree for: /tmp/recursion_demo
==================================================
README.md  (28 B)
├── docs/
    guide.md  (30 B)
├── src/
    main.py  (33 B)
    ├── models/
        user.py  (21 B)
    └── utils/
        config.py  (14 B)
        helpers.py  (30 B)
└── tests/
    test_main.py  (29 B)

Analyzing the Recursion

The show_tree function follows the standard recursive pattern:

• Base case (implicit): When a directory contains no subdirectories, the for d in dirs loop doesn't execute, and the recursion stops at that branch.
• Recursive case: For each subdirectory, the function calls itself with the subdirectory's path, an updated prefix (for tree-drawing characters), and an incremented depth.

Each directory is processed exactly once, making this an efficient O(n) traversal where n is the total number of files and directories.

Real-World Application: Directory Statistics

Here's a function that recursively computes statistics about a directory tree:

def directory_stats(path):
    """Recursively compute statistics for a directory tree.

    Returns a dict with file_count, dir_count, total_size, and
    a breakdown by file extension.
    """
    stats = {
        "file_count": 0,
        "dir_count": 0,
        "total_size": 0,
        "by_extension": {},
    }

    try:
        entries = os.listdir(path)
    except PermissionError:
        return stats

    for entry in entries:
        full_path = os.path.join(path, entry)
        if os.path.isfile(full_path):
            stats["file_count"] += 1
            size = os.path.getsize(full_path)
            stats["total_size"] += size

            # Track by extension
            _, ext = os.path.splitext(entry)
            ext = ext.lower() if ext else "(no extension)"
            if ext not in stats["by_extension"]:
                stats["by_extension"][ext] = {"count": 0, "size": 0}
            stats["by_extension"][ext]["count"] += 1
            stats["by_extension"][ext]["size"] += size

        elif os.path.isdir(full_path):
            stats["dir_count"] += 1
            # Recursive case: merge stats from subdirectory
            sub_stats = directory_stats(full_path)
            stats["file_count"] += sub_stats["file_count"]
            stats["dir_count"] += sub_stats["dir_count"]
            stats["total_size"] += sub_stats["total_size"]
            for ext, data in sub_stats["by_extension"].items():
                if ext not in stats["by_extension"]:
                    stats["by_extension"][ext] = {"count": 0, "size": 0}
                stats["by_extension"][ext]["count"] += data["count"]
                stats["by_extension"][ext]["size"] += data["size"]

    return stats

This is the kind of function Dr. Patel would use to survey thousands of sequence files across a complex directory tree. One call to directory_stats("/home/patel/sequences") traverses the entire tree and returns a complete summary — all built from a simple recursive traversal.

Part 2: HTML Documents

Why HTML Is Recursive

An HTML document is a tree of elements. Each element can contain text and other elements. A <div> can contain <p> tags, which can contain <span> tags, which can contain <a> tags. The nesting is recursive: an element contains elements.

Here's a simplified representation of an HTML document as nested Python dictionaries:

"""Processing recursive HTML-like document structures."""


def create_element(tag, text="", children=None, attrs=None):
    """Create an HTML-like element as a dictionary."""
    return {
        "tag": tag,
        "text": text,
        "children": children or [],
        "attrs": attrs or {},
    }


# Build a simple document structure
document = create_element("html", children=[
    create_element("head", children=[
        create_element("title", text="My Page"),
    ]),
    create_element("body", children=[
        create_element("h1", text="Welcome"),
        create_element("div", attrs={"class": "content"}, children=[
            create_element("p", text="First paragraph."),
            create_element("p", text="Second paragraph.", children=[
                create_element("a", text="Click here",
                               attrs={"href": "https://example.com"}),
            ]),
            create_element("ul", children=[
                create_element("li", text="Item 1"),
                create_element("li", text="Item 2"),
                create_element("li", text="Item 3"),
            ]),
        ]),
        create_element("footer", children=[
            create_element("p", text="Copyright 2025"),
        ]),
    ]),
])


def render_html(element, indent=0):
    """Recursively render an element tree as formatted HTML."""
    spaces = "  " * indent
    tag = element["tag"]
    attrs = element["attrs"]

    # Build attribute string
    attr_str = ""
    for key, value in attrs.items():
        attr_str += f' {key}="{value}"'

    # Opening tag
    result = f"{spaces}<{tag}{attr_str}>"

    if element["text"] and not element["children"]:
        # Inline element: <tag>text</tag>
        result += f"{element['text']}</{tag}>\n"
    elif element["children"]:
        result += "\n"
        if element["text"]:
            result += f"{spaces}  {element['text']}\n"
        for child in element["children"]:
            result += render_html(child, indent + 1)
        result += f"{spaces}</{tag}>\n"
    else:
        result += f"</{tag}>\n"

    return result


def extract_text(element):
    """Recursively extract all text content from an element tree."""
    texts = []
    if element["text"]:
        texts.append(element["text"])
    for child in element["children"]:
        texts.extend(extract_text(child))
    return texts


def find_elements_by_tag(element, tag):
    """Recursively find all elements with a specific tag."""
    results = []
    if element["tag"] == tag:
        results.append(element)
    for child in element["children"]:
        results.extend(find_elements_by_tag(child, tag))
    return results


def count_elements(element):
    """Recursively count all elements in the tree."""
    count = 1  # Count this element
    for child in element["children"]:
        count += count_elements(child)
    return count


# Demo
if __name__ == "__main__":
    print("=== Rendered HTML ===")
    print(render_html(document))

    print("=== All Text Content ===")
    for text in extract_text(document):
        print(f"  - {text}")

    print()
    print("=== All <p> Elements ===")
    for p in find_elements_by_tag(document, "p"):
        print(f"  <p> → {p['text']!r}")

    print()
    print(f"Total elements in document: {count_elements(document)}")

Expected output:

=== Rendered HTML ===
<html>
  <head>
    <title>My Page</title>
  </head>
  <body>
    <h1>Welcome</h1>
    <div class="content">
      <p>First paragraph.</p>
      <p>
        Second paragraph.
        <a href="https://example.com">Click here</a>
      </p>
      <ul>
        <li>Item 1</li>
        <li>Item 2</li>
        <li>Item 3</li>
      </ul>
    </div>
    <footer>
      <p>Copyright 2025</p>
    </footer>
  </body>
</html>

=== All Text Content ===
  - My Page
  - Welcome
  - First paragraph.
  - Second paragraph.
  - Click here
  - Item 1
  - Item 2
  - Item 3
  - Copyright 2025

=== All <p> Elements ===
  <p> → 'First paragraph.'
  <p> → 'Second paragraph.'
  <p> → 'Copyright 2025'

Total elements in document: 14

The Pattern

Every function that processes the HTML tree follows the same recursive pattern:

1. Process the current element.
2. For each child element, recurse.

This is identical to the directory traversal pattern. It's identical to the TaskFlow category search from Section 18.10. The same recursive pattern works on any tree structure. Once you recognize this pattern, you can apply it to:

• File systems (directories contain directories)
• HTML/XML documents (elements contain elements)
• JSON data (objects contain objects)
• Organization charts (managers manage managers)
• Comment threads (replies have replies)
• Category hierarchies (categories have subcategories)

Part 3: Other Recursive Structures in the Wild

JSON API Responses

Many APIs return nested JSON data. Here's a recursive function that extracts all values for a given key, no matter how deeply nested:

import json


def find_in_json(data, target_key):
    """Recursively find all values for target_key in nested JSON data."""
    results = []

    if isinstance(data, dict):
        for key, value in data.items():
            if key == target_key:
                results.append(value)
            results.extend(find_in_json(value, target_key))
    elif isinstance(data, list):
        for item in data:
            results.extend(find_in_json(item, target_key))

    return results


# Simulated API response with nested data
api_response = {
    "organization": "Acme Corp",
    "departments": [
        {
            "name": "Engineering",
            "manager": {"name": "Alice Chen", "email": "alice@acme.com"},
            "teams": [
                {
                    "name": "Backend",
                    "lead": {"name": "Bob Smith", "email": "bob@acme.com"},
                },
                {
                    "name": "Frontend",
                    "lead": {"name": "Carol Diaz", "email": "carol@acme.com"},
                },
            ],
        },
        {
            "name": "Marketing",
            "manager": {"name": "Dave Wilson", "email": "dave@acme.com"},
            "teams": [],
        },
    ],
}

print("All 'name' values:")
for name in find_in_json(api_response, "name"):
    print(f"  {name}")

print()
print("All 'email' values:")
for email in find_in_json(api_response, "email"):
    print(f"  {email}")

Expected output:

All 'name' values:
  Alice Chen
  Backend
  Bob Smith
  Frontend
  Carol Diaz
  Engineering
  Dave Wilson
  Marketing

All 'email' values:
  alice@acme.com
  bob@acme.com
  carol@acme.com
  dave@acme.com

Reddit-Style Comment Threads

Comment threads are recursive: every comment can have replies, and every reply is itself a comment that can have replies:

def display_thread(comment, depth=0):
    """Recursively display a comment thread with indentation."""
    indent = "  " * depth
    bar = "│ " * depth
    print(f"{bar}{'┌─ ' if depth > 0 else ''}{comment['author']} ({comment['votes']} pts)")
    print(f"{bar}{'│  ' if depth > 0 else ''}{comment['text']}")

    for reply in comment.get("replies", []):
        display_thread(reply, depth + 1)


thread = {
    "author": "user_42",
    "text": "Recursion is confusing at first, but it clicks eventually.",
    "votes": 128,
    "replies": [
        {
            "author": "cs_student",
            "text": "It clicked for me when I stopped tracing every call.",
            "votes": 85,
            "replies": [
                {
                    "author": "prof_jones",
                    "text": "That's the 'leap of faith' — exactly right!",
                    "votes": 42,
                    "replies": [],
                },
            ],
        },
        {
            "author": "debug_master",
            "text": "Adding print statements with indentation helped me a lot.",
            "votes": 63,
            "replies": [],
        },
    ],
}

display_thread(thread)

Expected output:

user_42 (128 pts)
Recursion is confusing at first, but it clicks eventually.
│ ┌─ cs_student (85 pts)
│ │  It clicked for me when I stopped tracing every call.
│ │ ┌─ prof_jones (42 pts)
│ │ │  That's the 'leap of faith' — exactly right!
│ ┌─ debug_master (63 pts)
│ │  Adding print statements with indentation helped me a lot.

The Unifying Principle

Every example in this case study — file systems, HTML documents, JSON data, comment threads — follows the same recursive structure:

1. A container holds items and sub-containers.
2. Each sub-container holds items and sub-sub-containers.
3. The nesting can go to any depth.

The recursive processing pattern is always the same: 1. Process items at the current level. 2. Recurse into each sub-container. 3. The base case is implicit: when there are no sub-containers, the loop simply doesn't execute.

Once you see this pattern, you'll recognize it everywhere — and you'll know exactly how to process it.

Discussion Questions

1. File systems have a maximum path length on most operating systems (e.g., 260 characters on older Windows systems). How does this effectively limit recursion depth? Could a deeply nested directory tree cause a RecursionError in a recursive traversal?

2. Real web browsers parse HTML using a technique called recursive descent parsing. Why is a recursive approach natural for parsing nested structures like HTML?

3. The find_in_json function finds all occurrences of a key. How would you modify it to find only the first occurrence and stop searching? What are the performance implications?

4. Think of another real-world data structure that is recursive by nature (not mentioned in this case study). Describe its recursive definition and sketch what a recursive processing function would look like.

Mini-Project

Build a "JSON explorer" that takes a JSON file as input and provides an interactive CLI: - tree — display the full structure with types (dict, list, str, int, etc.) at each level - find <key> — recursively find all occurrences of a key - depth — recursively compute the maximum nesting depth - stats — recursively count the total number of keys, values, and nesting levels

Test it on a real JSON file — you can download sample data from any public API or use a configuration file from a project on your computer.