Recursion on Nested Data
Where recursion stops being a curiosity. When the data itself is defined recursively, the code writes itself — one branch per case in the data's definition. Get the definition right and the function follows almost mechanically.
- Write a recursive definition of a data type.
- Turn that definition directly into code, one branch per case.
- Handle nested lists of arbitrary depth.
- Recognise the pattern in problems that look unrelated.
Unit 5 recursed on numbers, where a loop would have done. Here the data has no fixed depth, so there is no loop that could work. This is the case recursion was invented for.
JSON, XML and HTML are all arbitrarily nested. Every parser, every document renderer, every configuration reader walks them recursively.
Lisp, from 1958, made the nested list its only data structure — code and data were the same nested lists. Every function in it was written exactly this way, and the language is still in use for that reason.
Recursive data definitions
A nested list of integers is either:
The definition refers to itself, and one case — the integer — does not. That is exactly the base-case-and-recursive-case structure of a function.
One branch per case:
def f(obj):
if isinstance(obj, int):
# base case: handle a single integer
...
else:
# recursive case: combine f(item) over the elements
...Every function in this unit has that shape. Only the two bodies change.
def total(obj) -> int:
"""Return the sum of the integers in obj, a nested list of ints.
>>> total([1, [2, [3, 4]], 5])
15
"""
if isinstance(obj, int):
return obj
return sum(total(item) for item in obj)
def count(obj) -> int:
"""Return how many integers are in obj.
>>> count([1, [2, [3, 4]], 5])
5
"""
if isinstance(obj, int):
return 1
return sum(count(item) for item in obj)
def largest(obj) -> int:
"""Return the largest integer in obj.
Preconditions: obj contains at least one integer.
>>> largest([1, [7, [3]], 5])
7
"""
if isinstance(obj, int):
return obj
return max(largest(item) for item in obj)Handling the empty case
sum([]) is $0$, which is right for total. But
max([]) raises, which is why largest carries a
precondition. Always ask what the aggregation does on nothing.
def depth(obj) -> int:
"""Return the nesting depth of obj.
An integer has depth 0; a flat list has depth 1.
>>> depth(5)
0
>>> depth([1, 2])
1
>>> depth([1, [2, [3]]])
3
>>> depth([])
1
"""
if isinstance(obj, int):
return 0
if obj == []:
return 1
return 1 + max(depth(item) for item in obj)max can handle.Building new structures
def doubled(obj):
"""Return a new nested list with every integer in obj doubled.
The nesting structure is unchanged.
>>> doubled([1, [2, [3]]])
[2, [4, [6]]]
"""
if isinstance(obj, int):
return obj * 2
return [doubled(item) for item in obj]flatten below, which deliberately
destroys the shape. The difference is one line.def flatten(obj) -> list:
"""Return a flat list of all integers in obj, left to right.
>>> flatten([1, [2, [3, 4]], 5])
[1, 2, 3, 4, 5]
"""
if isinstance(obj, int):
return [obj]
result = []
for item in obj:
result.extend(flatten(item))
return resultextend work at every level.append instead of extend
would nest the results and defeat the entire
purpose.• Forgetting the empty-list case when the aggregation cannot handle
it.
• Returning an integer from the base case when the recursive case expects
a list.
• Using append where extend is
needed.
• Testing type(obj) == list instead of
isinstance.
• Trying to write a loop over depth. There is no such
loop.
Practice
Write out each answer before opening it. Original exercises written for this guide in the style of the course's weekly work.
What are the two cases for a nested list?
Answer
Count the sub-lists, not the integers, in a nested list.
Solution
def count_lists(obj) -> int:
"""Return how many lists appear in obj, including obj itself.
>>> count_lists([1, [2, [3]]])
3
"""
if isinstance(obj, int):
return 0
return 1 + sum(count_lists(item) for item in obj)Why does largest need a precondition?
Answer
max raises on an empty sequence, and there is no sensible
largest integer in a structure containing none.Test whether a value appears anywhere in a nested list.
Solution
def contains(obj, target: int) -> bool:
"""Return whether target appears anywhere in obj.
>>> contains([1, [2, [3]]], 3)
True
"""
if isinstance(obj, int):
return obj == target
return any(contains(item, target) for item in obj)any on an empty list is False, which is correct
here — no precondition needed.What single change turns doubled into
flatten?
Answer
Return a flat list of the negative integers in a nested list.
Solution
def negatives(obj) -> list:
"""Return a flat list of the negative integers in obj.
>>> negatives([1, [-2, [3, -4]]])
[-2, -4]
"""
if isinstance(obj, int):
return [obj] if obj < 0 else []
result = []
for item in obj:
result.extend(negatives(item))
return resultWhy prefer isinstance(obj, int) to
type(obj) == int?
Answer
isinstance accepts subclasses, which is usually what you want.
It is also the idiom the course expects.Why can no loop replace the recursion here?
Answer
Expanded topic checklist
Course coverage. This unit is part of the complete CSC148H1 topic map. It should cover the following items before you move on:
- Recursive definitions. Writing the data definition before the code.
- The mirror. One code branch per case in the definition.
- Aggregation. Combining recursive results, and what each aggregator does on empty.
- Building versus collapsing. Preserving nesting or flattening it.
The calendar's "recursion" topic covers this. Nested-list exercises are standard assignment material; check Quercus for the assigned set.
Recursive data gives recursive code with the same shape. Units 7 and 8 apply the identical technique to trees, where the recursive case is "each subtree" rather than "each element".
Deep practice extensions
Use these after the main practice set. They push on definitions and edge cases rather than routine calculation.
How does the data definition determine the code?
Guide
Why is sum safer than max here?
Guide
sum([]) is
$0$; max([]) raises. Aggregators without an identity value
need an empty case or a precondition.Why does flatten's base case return a list?
Guide
Why is no loop possible?