Not the exercise. This counts the people in a family tree, where each person has a list of children who are people too.
def count_people(person):
count = 1 # this person
for child in person["children"]:
count += count_people(child) # and everyone below them
return count
family = {"name": "Ada", "children": [
{"name": "Byron", "children": []},
{"name": "Grace", "children": [{"name": "Hal", "children": []}]},
]}
print(count_people(family)) # -> 4
- Every node has the same shape here
Each person has children, even if the list is empty, so one rule covers every node. Folders and files do not work like that: a file has no children at all.
- The leaves are the base case
Someone with no children returns 1 without recursing. In the exercise a file plays that part: it answers with its size and goes no deeper.
- Recurse on the child, not the parent
count_people(child), never count_people(person). Calling it on the node you already have is a call that never gets any smaller.
Look at the node first. If it has a "size", it is a file and you already know the answer. If it has "children", its size is the total of theirs.
For a folder, start a total at 0 and add total_size(child) for every child. Each child can be a file or a folder; total_size already handles both.
if "size" in node: check it is not negative, then return it. Otherwise return the sum of total_size(child) for child in node["children"].
def total_size(node): if "size" in node: if node["size"] < ____: raise ValueError(...) return node["____"] return sum(____(child) for child in node["children"])
def total_size(node):
if "size" in node:
if node["size"] < 0:
raise ValueError(f"{node['name']} has a negative size")
return node["size"]
return sum(total_size(child) for child in node["children"])
A file and a folder need different answers, so the first line tells them apart. Everything after that is one of two simple cases.
Because every file, at any depth, goes through the same few lines, one check there covers the whole tree. A check only at the top would miss a bad size three folders down.
An empty folder needs no special case: sum() of nothing is 0.
On a real disk, os.walk or pathlib’s rglob already walk the tree for you, and do it without Python’s recursion limit. Write the recursion yourself when the tree is data you were handed, like an API response, not a directory you can walk.
- Return the size of each folder as well, as a dict from path to size.
- Find the largest file anywhere in the tree and return its name.
- Rewrite it with an explicit stack instead of recursion and compare the two.