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.
Another way to implement the recursive linear search is to reduce the size of the list being searched with each recursive call. Check the first item of the list, and if it is not the key, make a recursive call with a sublist that excludes the first item. For example, if we started with the list {10, 20, 30, 40, 50} and did not find what we were looking for at index 0, we would make a recursive call with the list {20, 30, 40, 50}.
Making new lists is much less efficient than just keeping track of the current index. If we start with a list of \(n\) items using that approach, we would create a list of size \(n-1\) for the first recursive call, then a list of size \(n-2\) for the next call, and so on down to size 1. The total amount of work creating all those lists would be proportional to \(n^2\text{.}\) Which is significantly more work than the work we want to do with the search itself, which is proportional to \(n\text{.}\)
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.
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?
