Defining base cases

In the previous module we derived the recurrence relation, which tells us how the value at any state is computed from the values at smaller states. But a recurrence alone is not enough to define a complete algorithm. Every recursive computation has to stop somewhere, at states whose values are known directly rather than computed from anything smaller. Those states are the base cases and they make up the third pillar of any dynamic programming algorithm.

Base cases are the leaves of the state space DAG. They are where the recursion bottoms out, and where the values that get propagated upward through the DAG are first established. A single mistake in the base cases will silently corrupt every value the algorithm ever computes.

In this lesson we develop the conceptual picture of what base cases are and what they do. We define a base case formally, look at the two roles it plays in a dynamic programming solution, distinguish the two types of base case (genuine and boundary), and look carefully at how sentinel values propagate upward through the recurrence.

What base cases are

A base case is a state whose value is given directly, without invoking the recurrence. Formally, the recurrence is a partial definition: for most states s, dp(s) is defined by the Bellman equation in terms of smaller states, but for a designated set of states (base states), dp(s) is defined explicitly, as a value written down by the algorithm designer rather than computed.