Recursion, trees and graphs
Functions that call themselves, and the shapes most real data takes.
Create a free account Try part of it here
Why it matters
Most real data isn't a flat list. Folders hold folders. JSON holds objects inside objects. Web pages link to pages, and tasks depend on other tasks. This course's own knowledge map is a graph of lessons and prerequisites. Trees and graphs are how software models all of it, and recursion is the natural way to walk them. Agents use the same ideas to plan steps that depend on each other.
What you'll be able to do
- Write a recursive function with a base case, and read the call stack it builds
- Walk a tree, such as nested folders or JSON, with recursion
- Represent a graph as an adjacency list and find the fewest-steps path with breadth-first search
- Order tasks by their dependencies with a topological sort, and detect cycles
What it covers
- Recursion: a function that calls itself
- Trees
- Graphs
- Dependencies are a graph
- Topological sort: an order that respects dependencies
- Why recursion goes wrong
- When to avoid recursion
Recursion: a function that calls itself
You're in a long line and want to know your place in it. You ask the person ahead, "What number are you?" They ask the person ahead of them, and so on. The person at the front says "1", and the answer passes back, each person adding one.
That's a recursive function: it solves a problem by solving a smaller version of the same problem. It needs two parts:
- a base case: a version so small the answer is obvious, so the function stops (the person at the front);
- a recursive case: shrink the problem and call itself on the smaller version (asking the person ahead).
def countdown(n): if n == 0: # base case print("liftoff") return print(n) countdown(n - 1) # recursive case: a smaller problem countdown(3)
Each call waits for the one it made to finish. Python keeps track of the waiting calls on the call stack, the same stack idea as the last lesson. Step through this one and watch the stack grow, then unwind:
Three frames for sum_to stack up before any of them can return. Then each one finishes, adding its n to the answer from below.
Forget the base case and the calls never stop. Python stops them for you, at about 1,000 waiting calls:
def forever(n): return forever(n + 1) forever(0)
Trees
A family tree starts with one person and branches downward. A tree in code is data where each item can hold more items of the same kind. A folder holds files and more folders. A JSON object holds values and more objects. The top item is the root, and items with nothing inside are leaves.
Recursion fits trees perfectly, because each part of a tree is itself a smaller tree:
# Folders are dicts; files are sizes in KB. project = { "README.md": 4, "src": {"app.py": 12, "utils.py": 6, "models": {"user.py": 3}}, "data": {"sales.csv": 900}, } def total_size(node): if isinstance(node, int): # base case: a file return node return sum(total_size(child) for child in node.values()) print(total_size(project), "KB") print(total_size(project["src"]), "KB in src")
Notice there's no loop over "levels". The function doesn't know or care how deep the folders go.
In plain words: to measure a folder, add up its files and measure each folder inside it the same way.
def depth(node): return 1 + max(depth(c) for c in node.values())
Show the answer
There's no base case, so it fails when it reaches a file (an int) or an empty folder
It needs a base case. For a file, return 0 before trying to look inside it. An empty folder also needs handling, because max() of nothing raises an error.
Graphs
Think of a subway map: stations joined by lines, with many ways around. A graph is a set of nodes joined by edges. Unlike a tree, any node can connect to any other, and paths can loop back. Road maps, links between web pages and friendships are graphs. In a directed graph, edges have a direction, like one-way streets, or "lesson A is a prerequisite of lesson B".
The usual way to store a graph in code is an adjacency list: a dict from each node to the list of nodes it connects to. It's like writing down, for each station, the stations you can reach from it.
Breadth-first search
To find the fewest hops between two nodes, explore in rings, the way ripples spread on a pond: first everything one step away, then two steps, and so on. That's breadth-first search (BFS), and it uses a queue:
from collections import deque links = { "home": ["shop", "blog"], "shop": ["tent", "checkout"], "blog": ["tent"], "tent": ["checkout"], "checkout": [], } def shortest_path(graph, start, goal): queue = deque([[start]]) seen = {start} while queue: path = queue.popleft() node = path[-1] if node == goal: return path for nxt in graph[node]: if nxt not in seen: seen.add(nxt) queue.append(path + [nxt]) return None print(shortest_path(links, "home", "checkout"))
The seen set matters. Without it, a graph with a loop would send the search around forever. Swap the queue for a stack and you get depth-first search (DFS), which follows one path as far as it goes before backing up, like walking through a maze.
Show the answer
Nodes are accounts; edges are follows, with a direction
Each follow points from one account to another, so it's a directed graph. Cycles are allowed: two people can follow each other.
Dependencies are a graph
Some lessons in this course list prerequisites, so the course map is a directed graph. Here's a tiny piece of it. Which lessons are ready once you've finished variables?
prereqs = {
"variables": [],
"numbers": ["variables"],
"strings": ["variables"],
"conditionals": ["numbers", "strings"],
}
done = {"variables"}
ready = [lesson for lesson, needs in prereqs.items()
if lesson not in done and all(n in done for n in needs)]
print(ready)numbers and strings only need variables, so both are ready. conditionals needs both of them first. Build tools, package managers and spreadsheet recalculation all ask this same question: "what can run now?"
Topological sort: an order that respects dependencies
Socks go on before shoes. Say you have tasks with prerequisites, and you need one order where every task comes after the tasks it depends on. That's a topological sort. Package installers use it to pick what to install first. Build systems use it to pick what to compile first.
Kahn's algorithm does it with counting:
- For each task, count how many prerequisites it still waits on.
- Every task waiting on zero can run. Take one, add it to the order.
- Each task that depended on it now waits on one fewer. If that reaches zero, it can run too.
- Repeat until nothing is left.
If tasks remain but none is waiting on zero, they wait on each other in a loop: a cycle. You can't get the job without experience, and you can't get experience without the job. Then no valid order exists. "A needs B and B needs A" is a bug to report, not a puzzle to solve.
Show the answer
build, test, deploy
Each task must come after the ones it needs. build needs nothing, so it goes first, then test, then deploy.
Why recursion goes wrong
Every recursive function needs two things: a base case that stops, and a step that moves toward it. Most recursion bugs are one of those missing.
def total(items): if not items: # base case: nothing left return 0 return items[0] + total(items[1:]) # a smaller problem each time print(total([3, 5, 2]))
If the base case can never be reached, Python stops at about 1,000 nested calls with a RecursionError. When you see one, look at what changes between calls. Is the problem really getting smaller? For example, total(items) calling itself with the same list never gets anywhere.
Graphs can loop back
A tree has no cycles, so walking it always ends. A graph can loop: A links to B, and B links back to A. Walk it like a tree and you'll go round forever. That's why graph searches keep a seen set, and skip anything already visited. Forgetting it is the classic graph bug.
Depth-first and breadth-first search also find different things. Depth-first goes as far as it can down one path before backing up. It will find a route, but not necessarily the shortest. Breadth-first checks everything one step away, then two steps away, so the first time it reaches a node, that's a shortest route, counting steps.
And if tasks depend on each other in a circle, no order can work. A topological sort will reach a point where nothing is ready, and that's your signal that the dependencies contain a cycle. Real build tools report this as an error, because it needs a person to fix it.
When to avoid recursion
Very deep data, like a linked list of 100,000 items, will hit the recursion limit. A loop with your own stack handles any depth, and it's the safer choice there.
Practice what you just read
- 6 code examples you can edit and run
- a practice exercise that checks your code
- a 5-question quiz
- 5 review cards for spaced repetition
Try a quiz question
What are the two parts every recursive function needs?