Designing Base Cases and Progress Toward Them

Designing bases asks: what is the smallest meaningful input, and what should the answer be when no decision remains? Often mirror the combine step’s identity.

Why this shows up in the real world

Puzzle games, constraint solvers, and interview combinatorial search all share the same skeleton: build state, recurse, undo.

Core idea (explained for students)

Work backward from desired final composition: if combine uses +, base returns 0; if and, base returns True for empty guard carefully.

Try this in Python

def power(x: float, n: int) -> float:
    if n == 0:
        return 1.0
    if n < 0:
        return 1.0 / power(x, -n)
    half = power(x, n // 2)
    return half * half * (x if n % 2 else 1)


print(round(power(2, 10), 3))

Common mistakes

• Base too late—recursion never reaches it.
• Off-by-one when base is len==1 vs len==0.

Key takeaways

• Write recurrence + base together as a math definition first.
• Add defensive asserts for impossible states.