Recursion Base Cases

Base cases are the terminating snapshots: empty input, goal reached, or “no moves left” — they must return the correct neutral value for composition (0, True, []).

Why this shows up in the real world

Tree leaves in recursion mirror base cases; parsers hit EOS token.

Core idea (explained for students)

List all bases: smallest n, empty string, invalid state. Ensure recursive step always moves strictly toward one of them.

Try this in Python

def sum_list(xs: list[int]) -> int:
    if not xs:
        return 0
    return xs[0] + sum_list(xs[1:])


print(sum_list([2, 3, 5]))

Common mistakes

• Partial base that returns wrong value for compose (max path returning -inf incorrectly).
• Multiple bases overlapping—define precedence.

Key takeaways

• Match base return type to monoid identity of combine step.
• Unit-test bases in isolation.