The Base Case and the Recursive Case

When we wrote recursive binary search, we saw the two cases every recursive method needs.

• The recursive case reduces the problem to a smaller version of the same problem and calls the method again, trusting that call to handle the rest. In binary search, that is the two calls on the left half and the right half.
• The base case is a version of the problem small enough to answer outright, with no further calls. In binary search, that is low > high.

A recursive method can have more than one base case, and it can have more than one recursive case. Binary search happens to have one of each, but that is not a requirement.

Every recursive case has to move the problem closer to a base case.

When we write a recursive method, we can start with the base case. I did not do that with binary search, because I wanted to show you how to spot the recursive structure first. In practice it is often easier the other way around: decide what the smallest case is and answer it, then build the recursive case on top.