Recursion mirrors problem structure

Beginner Recursion & structural decomposition

Created by Pavel · 29.04.2026 at 19:04 UTC

Many real datasets are not rectangular tables yet: responses from REST APIs mix dicts and lists; YAML configs nest sections; intermediate representations for custom transforms are lists of lists of arrays. When the problem repeats inside itself—the same rule applies at every level of nesting—a recursive function often reads like a specification: “if this is a leaf, do X; otherwise, do X for each child and merge.”

Iterative code with an explicit collections.deque or a manual stack can solve the same problems and avoids deep recursion limits, but it scatters the structural invariant across loop and push/pop logic. Recursion keeps the invariant local: each call handles one “layer” only.

In machine-learning codebases you still see recursion for tree models (internal nodes vs leaves), for parsing small expression DSLs, and for walking object graphs before serialisation. Choose recursion when clarity wins and depths stay modest; choose iteration when depth is bounded only by raw row counts.

Data model docs (JSON type hierarchy): [1].

Sources

[1]https://docs.python.org/3/library/json.html Return to text

University approvals: 0

Tasks

Question 1

What does this code print?

def flatten_keys(d, prefix=''):
    out = []
    for k, v in d.items():
        p = f'{prefix}.{k}' if prefix else k
        if isinstance(v, dict):
            out.extend(flatten_keys(v, p))
        else:
            out.append(p)
    return out

print(sorted(flatten_keys({'m': {'a': 1, 'b': 2}})))

Hint

Recursion builds dotted paths; both leaves append m.a and m.b.

['m.a', 'm.b']

['a', 'b']

['m', 'a', 'b']

Error — dicts cannot nest

Question 2

When is recursion usually the clearest choice for data scientists?

Hint

Match control flow to self-similar data.

Whenever you need the fastest possible NumPy kernel

Only inside async def coroutines

When nested data or rules repeat at every level of structure

Never—pandas always replaces recursion

Question 3

nested_sum(x) traverses arbitrarily nested structures of ints and lists: ints sum as themselves; lists sum recursively over elements. Empty list sums to 0.
Example: nested_sum([1, [2, 3], 4]) == 10.

Hint

Use isinstance(x, list) to branch; recurse on elements.

def nested_sum(x):
    # ints vs lists
    pass

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

2 test cases will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Card Info

Topic: Recursion & structural decomposition
Difficulty: Beginner
Completed: 0 users

Creator

Pavel