Follow the shape
For nested data, handle one item and recurse on any nested item. The calls mirror the containers.
Leaf is the base
A value that is not a container is the base case. Every branch ends at a leaf.
Recursion on nested data
When the data itself nests, recursion is the natural fit. A function that handles a piece and calls itself on the sub-pieces mirrors the shape.
What you will see
2
About 3 min of reading
Quick check
Before this new lesson, one small question about the lesson you just finished. Recall it, do not look it up.
Try It
Walk nested data with recursion.
1
Sum a nested list.
def total(a):
s = 0
for x in a:
if isinstance(x, list):
s += total(x)
else:
s += x
return s
print(total([1, [2, [3]]]))
Before you run it, say out loud what it will print. Then open the answer.
What it prints
6
2
Count leaves.
def leaves(a):
n = 0
for x in a:
if isinstance(x, list):
n += leaves(x)
else:
n += 1
return n
print(leaves([1, [2, [3]]]))
Before you run it, say out loud what it will print. Then open the answer.
What it prints
3
3
Flatten a list.
def flat(a):
out = []
for x in a:
if isinstance(x, list):
out += flat(x)
else:
out.append(x)
return out
print(flat([1, [2, [3]]]))
Before you run it, say out loud what it will print. Then open the answer.
What it prints
[1, 2, 3]
4
Count nested dict keys.
def count_keys(d):
n = len(d)
for v in d.values():
if isinstance(v, dict):
n += count_keys(v)
return n
print(count_keys({"a": {"b": 1}}))
Before you run it, say out loud what it will print. Then open the answer.
What it prints
2
Put it in order
Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.
Data Flow
Nested data recurses naturally: handle a leaf directly and call the same function on any nested container, mirroring the shape.
1
nested data
↓
2
leaf is base
↓
3
recurse on sub-list
↓
4
walk mirrors shape
Line by line
Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.
def total(a):
sets nothing on screen
s = 0
sets nothing on screen
for x in a:
sets nothing on screen
if isinstance(x, list):
sets nothing on screen
s += total(x)
sets nothing on screen
else:
sets nothing on screen
s += x
sets nothing on screen
return s
sets nothing on screen
print(total([1, [2, [3]]]))
6
Why this works
Examples
Sum a nested list
def total(a):
s = 0
for x in a:
if isinstance(x, list):
s += total(x)
else:
s += x
return s
print(total([1, [2, [3]]]))A list item is summed by the same function. The nesting of data drives the nesting of calls.
Count the leaves
def leaves(a):
n = 0
for x in a:
if isinstance(x, list):
n += leaves(x)
else:
n += 1
return n
print(leaves([1, [2, [3]]]))Each leaf counts one; each list recurses. The shape of the data is the shape of the work.
Find the depth
def depth(a):
if not a:
return 1
return 1 + max(depth(x) if isinstance(x, list) else 0 for x in a)
print(depth([1, [2, [3]]]))The deepest branch sets the answer. Recursion measures the nesting.
Empty is the base
def total(a):
s = 0
for x in a:
if isinstance(x, list):
s += total(x)
else:
s += x
return s
print(total([]))An empty list sums to zero. That base case ends the walk.
Dict nests too
def count_keys(d):
n = len(d)
for v in d.values():
if isinstance(v, dict):
n += count_keys(v)
return n
print(count_keys({"a": {"b": 1}}))A nested dictionary is walked the same way. The container type decides the recursion.
Flatten one level
def flat(a):
out = []
for x in a:
if isinstance(x, list):
out += flat(x)
else:
out.append(x)
return out
print(flat([1, [2, [3]]]))Flatten calls itself on each sublist. The result is one flat list of leaves.
Recursion mirrors shape
def total(a):
s = 0
for x in a:
if isinstance(x, list):
s += total(x)
else:
s += x
return s
print(total([5]))The function reads like the definition of nested data. That is the reason recursion fits.
Base is a leaf
def leaves(a):
n = 0
for x in a:
if isinstance(x, list):
n += leaves(x)
else:
n += 1
return n
print(leaves([7]))A non-list item is a leaf, counted directly. Leaves are the base cases.
Words this lesson uses
Each one is defined here on this site. Open the entry for the full definition and the other words it points at.
← The call stack
Previous Lesson
The call stack