Base Cases in Recursive Algorithms

Imagine a sorted array A holding the seven values 3, 7, 11, 15, 19, 24, 30 at indices 0 through 6. A recursive binary search is asked to find the value 10 somewhere in this whole array. Before reading on, decide what the search should return. Think about whether 10 could ever be found, and what the algorithm should do once every remaining candidate has been ruled out.

Many learners first picture recursive binary search as a simple chain of halvings that always ends by landing on the target. In that picture, the middle element is checked, the half containing the target is chosen, and the process repeats until the target turns up. The hidden assumption is that the search never faces a situation where nothing is left to examine. That assumption is wrong. It is one of the most frequent problems students hit when they write this routine themselves: they forget to handle the case where the portion of the list under consideration has no elements at all.

The correction changes how you should think about the recursion. A recursive search is not guaranteed to find the value. It keeps going until one of two things happens: the value is located, or the portion still being searched is empty. Both outcomes must be written into the routine as explicit cases. The rest of this article explains why each one is needed, and then traces the search for both a present value and an absent value.

The original, non-recursive binary search could assume it was looking at an entire array. A recursive version cannot make that assumption, because each call must search only the portion of the array that remains under consideration. For that reason the recursive subroutine takes two extra parameters, loIndex and hiIndex. They mark the first and last positions of the range still being searched, inclusive at both ends. The value being sought is passed along unchanged.

This is a general lesson about recursion. To solve a problem recursively, the problem often has to be generalized a little. The original question was 'find this value in this array.' The generalized question is 'find this value between these two positions of this array.' The whole array is simply the special case where the range runs from 0 to the array length minus one, which is why the whole-array search is started with 0 and A.length minus 1.

The figure shows the state of the search after one comparison when looking for 24. The value 15 at the middle position is smaller than 24, so the portion at or before the middle is discarded, and the recursive call receives the range from index 4 through index 6. Nothing about the array has changed. Only the pair of parameters has moved, and that pair is all the recursive call needs to know about the part of the array it must examine.

Every recursive case works on a strictly smaller range than the one that produced it. The value is either smaller than the middle element, so the lower half is chosen, or larger, so the upper half is chosen. This shrinking is what guarantees that the recursion eventually reaches a base case.

The first base case is the empty range. If the starting index has moved past the ending index, there are no elements left to consider, so the value cannot be present. The answer -1 can be returned immediately. The empty-range check must come before any computation that depends on the range having elements, because an empty range has no middle element to examine.

The second base case is the successful middle check. If the value equals the element at the middle position, the index of that element is the answer, and no further recursion is needed. The search returns that index directly.

Every other situation is a recursive case. When the middle element is not the one sought, the search is handed to one of the two halves of the current range. The base cases are what stop the recursion. The recursive cases are what keep it moving toward them.

Use the same array, 3, 7, 11, 15, 19, 24, 30 at indices 0 through 6, and search for 24 in the whole array. The first call receives the range 0 through 6. The middle position of that range is index 3, which holds 15. Because 24 is larger than 15, the lower portion is discarded and the call makes a recursive call on the range 4 through 6.

Now search for 10 in the same array. The value 10 is not present, so the search can only end when the range runs out of elements. Each call still follows the same rule: compare the value with the middle element, then discard the half that cannot contain it.

Trace the calls step by step. The first call receives range 0 through 6, with middle index 3 holding 15. Since 10 is smaller than 15, the upper portion is discarded and the second call receives range 0 through 2. Its middle index is 1, which holds 7. Since 10 is larger than 7, the third call receives range 2 through 2. Its middle index is 2, which holds 11. Since 10 is smaller than 11, the next range would be from index 2 through index 1. That range is empty, because the starting index has moved past the ending index. The empty-range base case applies, and the call returns -1 immediately.

The -1 does not stay inside the innermost call. Each earlier call received its answer from a recursive call and passes that same value back up to its own caller. The fourth call returns -1 to the third, the third returns -1 to the second, the second returns -1 to the first, and the first returns -1 to the original caller. The original caller therefore learns that 10 is not in the array.