Recursion and Trees: When a Problem Contains Itself

I ended the last post with a promise: the call stack that runs every function is itself a stack, so recursion is really just a stack you do not have to manage by hand. This post makes good on that, and then shows the shape recursion was born for: the tree.

Recursion scares a lot of people. It should not. Once you see it as “solve a small version, then build up,” it becomes one of the most natural tools you have, especially for anything with a hierarchy.

Recursion, simply

Recursion is a function that solves a problem by calling itself on a smaller piece of the same problem.

Every recursive function has exactly two parts:

1. A base case: the smallest version, where you stop and return an answer directly.
2. A recursive case: do a little work, then call yourself on something smaller, moving towards the base case.

Here is the textbook example, the factorial:

def factorial(n):
    if n <= 1:          # base case: stop here
        return 1
    return n * factorial(n - 1)   # recursive case: smaller problem

To compute factorial(4), the function calls factorial(3), which calls factorial(2), and so on until factorial(1) returns 1, and the answers multiply back up. Each call waits on the call below it. That waiting is the call stack from the last post: every call pushes a frame, and the frames pop off as answers return.

The single most important line is the base case. Forget it, and the function calls itself forever, the stack fills up, and you get the famous “stack overflow.” That error is literally the stack from the previous post overflowing.

The mental trick: trust the smaller call

The thing that makes recursion click is to stop tracing every call in your head. You do not need to. Assume the recursive call already works on the smaller piece, then just handle two things: this one level, and the base case. If both are right, the whole thing is right. That leap of trust is the skill.

Trees: data with a hierarchy

A tree is data arranged in a hierarchy. There is a root at the top, nodes branch into children, and the nodes with no children are leaves. You already know dozens of trees: a file system, an org chart, a table of contents, the comment thread under a post.

The clearest one in my work is the DPM 2025 ready-reckoner. A procurement manual is not a flat list, it is a tree: volumes contain chapters, chapters contain sections, sections contain sub-sections. When I ingested it, the natural representation was a “doctree,” a tree of nodes mirroring the document.

Why recursion and trees belong together

Here is the key insight. Every node in a tree is itself the root of a smaller tree. A chapter is just a smaller document. A section is a smaller chapter. The shape repeats at every level, which is exactly the situation recursion is made for.

So “do something to a whole tree” becomes a tiny recursive idea: handle this node, then recurse on each of its children.

node = {
    "title": "Volume I",
    "children": [
        {"title": "Chapter 1", "children": [
            {"title": "Section 1.1", "children": []},
            {"title": "Section 1.2", "children": []},
        ]},
        {"title": "Chapter 2", "children": []},
    ],
}

def print_titles(node, depth=0):
    print("  " * depth + node["title"])        # handle this node
    for child in node["children"]:             # recurse on each child
        print_titles(child, depth + 1)

print_titles(node)

That handful of lines walks a document of any depth and prints its outline. This pattern, called depth-first traversal, is how I render the navigable hierarchy and how I walk cross-references in the ready-reckoner. The same recursion counts nodes, searches for a section, or flattens the tree into a list.

If instead you want to go level by level (all chapters before any section), you use breadth-first traversal, which uses a queue, the structure from the last post. So the whole series links up: a stack (or recursion) goes deep, a queue goes wide.

Where this shows up in real work

• Documents and outlines. The DPM doctree is the obvious one: parse into a tree, then recurse to render, search, and cross-link.
• Anything nested. JSON, nested config, folders inside folders. A recursive walk handles arbitrary depth without you knowing the depth in advance.
• Categories and threads. Category trees, reply threads, menus. All trees, all naturally recursive.

The honest notes

• The base case is everything. Get it wrong and you get infinite recursion and a stack overflow. Write it first.
• Very deep trees can blow the stack. Because each call uses a stack frame, an extremely deep structure can exhaust it. When that is a real risk, you switch to an explicit stack (iterative depth-first) or a queue (breadth-first). This is the practical link back to the previous post: recursion is convenient, but it is the same stack underneath, and sometimes you manage it yourself.
• Recursion is for clarity, not always speed. If the data is a flat list, a plain loop is simpler. Reach for recursion when the data is genuinely nested or tree-shaped, because then the recursive version is the one that reads like the problem.

The takeaway, and the toolkit

That rounds out four fundamentals, and together they cover an enormous share of everyday programming:

• Hash map: find an exact thing, instantly.
• Binary search: find where something falls in ordered data.
• Stacks and queues: decide what to handle next.
• Recursion and trees: handle things that are nested inside themselves.

None of these are exotic. They are the boring, dependable building blocks under almost everything that looks clever, which has been the theme of this whole series. Learn these four well and most code stops being mysterious and starts looking like combinations of a few simple moves.

A natural follow-on, when you want it: graphs, which are trees with more connections, and the searches that run on them.