Recursion: base case and walking trees

A lot of data is a tree: nested JSON, a folder hierarchy, a category taxonomy. Recursion is a function that calls itself on a smaller piece of the problem until the piece is trivial. Every recursion needs a base case (when to stop) and a recursive case (reduce the problem and call itself).

Summing every value in a tree reads almost like its own definition — a node's total is its own value plus the totals of its children:

def tree_sum(node):                      # node = {"val": int, "children": [...]}
    return node["val"] + sum(tree_sum(c) for c in node["children"])

Here the base case is a node with no children (the sum of an empty list is 0).

The recursive shape generalises to any nested structure. Reading arbitrarily nested JSON, computing a maximum depth, or totalling values are all the same pattern: handle the current node, then recurse into its children.

import json
root = json.loads(text)        # a nested dict/list tree
print(tree_sum(root))

Code that mirrors a tree's shape is short and obviously correct, which is why recursion is the natural language of hierarchical data. The same idea also drives binary-tree traversals — and an in-order walk of a binary search tree visits values in sorted order.
and leads into “Explicit stacks and the recursion limit”.*