To implement a linear search recursively we can look at the first element of the list. If it is the key, return its index. If not, recursively search the rest of the items. To do this job, we need to know the list, the key we are looking for, and the current index we are checking.
Base cases: reach the end of the list or find the key.
template<typename T>
int linearSearchRecursive(const vector<T>& vec, T key, int currentIndex = 0) {
if (currentIndex >= vec.size()) {
// Reached the end without finding the key
return -1;
} else if (vec.at(currentIndex) == key) {
// Found the key at the current index
return currentIndex;
} else {
// Not found yet, check the next index, return the result
return linearSearchRecursive(vec, key, currentIndex + 1);
}
}
Lines 2 and 5 are the two base cases: either we have found the key at the current index, or we have checked all indexes without finding it. If neither base case is met, we recursively move on to the next index in line 10.
Note that the currentIndex parameter has a default value of 0. So we can make a call to the function without specifying that parameter to start searching from the beginning of the list.
Although any iteration can be turned into recursion, some algorithms are more naturally expressed recursively than others. Binary search is an algorithm that has a very natural recursive structure. How do you do binary search on a list of items? You check the middle item and if it is not what you are looking for, you do binary search on either the lower half or the upper half of the list.
Again, there are two base cases that can end the recursion. But, there are also two recursive cases. Either we can recursively search the bottom half of the remaining items, or we can recursively search the top half.
For this function, we use a non-recursive “wrapper” function to kickstart the recursion. When main calls binarySearch(numbers, key), that function calls the recursive function with indexes 0 and size - 1. We could skip that helper by having main pass those indexes directly to the recursive function. But having the wrapper function makes it easier to use.
Another way to implement the recursive binary search would be to only pass half the list on each recursive call. For example, if we started with the list {10, 20, 30, 40, 50} and realized that the middle value (30) was too small, we would make a recursive call with the list {40, 50}. This version would not need to keep track of the start and end indexes as parameters.
However, making new lists would be much less efficient. If we start with \(n\) items, the first recursive call would create a new list with \(n/2\) items, the second recursive call would create a new list with \(n/4\) items, and so on. The total number of items copied across all recursive calls would be \(n + n/2 + n/4 + ... + 1\text{.}\) This series simplifies to \(O(n)\text{.}\) Thus, we would spend at least \(O(n)\) time just copying items into new lists, which means our binary search would not be \(O(log n)\)
Suppose you have the following sorted list {3, 5, 6, 8, 11, 12, 14, 15, 17, 18} and are using the recursive binary search algorithm. Which group of numbers correctly shows the sequence of comparisons used to search for the key 16?
