Base cases anchor recursive solutions

Beginner Recursion & structural decomposition

Created by Pavel · 29.04.2026 at 19:04 UTC

When you ingest nested JSON from a feature store, walk a directory of experiment artefacts, or implement a tiny decision-stump routine for teaching, you are doing the same structural thing: decompose a big blob into smaller pieces until each piece is trivial to handle. Recursion is the programming pattern that mirrors that decomposition.

A base case is the branch where you stop calling yourself: the empty list, the scalar leaf in a nested dict, depth zero in a tree, or n == 0 in factorial. Without it, every call spawns another call and you eventually hit RecursionError. A second failure mode is subtler: you terminate, but you forget to combine partial answers on the way back up—factorial that returns fact(n-1) without multiplying by n, or a tree visitor that recurses into children but never adds their contributions to the parent aggregate.

For data scientists, recursion is a readability tool when data shape matches call shape: arbitrarily nested lists of batch metrics, schema trees, or grouped pandas structures you intentionally represent as plain Python nesting. It is a liability when depth tracks dataset size (millions of rows) because CPython allocates a real stack frame per call and does not optimise tail recursion away.

Glossary (recursion): [1].

Sources

[1]https://docs.python.org/3/glossary.html#term-recursion Return to text

University approvals: 0

Tasks

Question 1

What does this code print?

def walk(d, depth=0):
    if not isinstance(d, dict) or not d:
        return depth
    k = next(iter(d))
    return walk(d[k], depth + 1)

print(walk({'a': {'b': {'c': 1}}}}))

Hint

Each nonempty dict step recurses into one child and adds 1.

Question 2

In a data pipeline, you validate a nested API payload by recursing until each leaf is a number. Which statement is most accurate?

Hint

Containers vs leaves mirror recursive structure.

The base case should run only once per HTTP request

The base case handles leaves; recursive steps handle containers

Recursion removes the need to check types at leaves

Base cases are optional if you wrap calls in try/except

Question 3

Implement fact(n: int) -> int for non-negative integers: fact(0) == 1, fact(n) == n * fact(n-1) for n > 0. For negative n raise ValueError. Expression tests call fact. Stdlib only.

Hint

Reject negatives first, then the n == 0 branch, then recurse.

def fact(n: int) -> int:
    # recursive factorial
    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