Recursive Linear Search

Linear search can also be implemented recursively:

• You look at the first element of the array.
• If it is the target, you are done.
• If it is not, then you need to search the rest of the array. That is linear search on a smaller version of the same problem, so you can call the same method again on the rest of the array.

Now let’s practice the base-case-first way of thinking by writing a recursive linear search. What is the simplest version of the problem, the one we can answer without any recursive call at all? Here are some candidates:

• The first element is the target, so we can return true immediately.
• The array has only one element, so we can check it and return true or false accordingly.
• The array is empty, so we can return false immediately, whatever the target is.

Each of these can be answered immediately. The question is which one the recursion must have to guarantee it terminates. The recursive case removes one element from the front, so the array gets shorter by one on every call: length 5, then 4, then 3, and so on. If the target is never found, the calls continue down to length 0. So the empty array is the case the recursion is guaranteed to reach, and if we do not handle it, the recursion never stops. Let’s start there:

public static boolean linearSearch(int[] arr, int target) {
  if (arr.length == 0) {
    return false;  // base case: array is empty so target is not found
  }
  // ...
}

If the array is not empty, there is a first element to look at, and if it happens to be the target we are also done. That is another base case. It is not required for termination the way the empty case is. It is the base case that returns true when we find the target.

public static boolean linearSearch(int[] arr, int target) {
  if (arr.length == 0) {
    return false;  // base case: array is empty so target is not found
  } else if (arr[0] == target) {
    return true;  // base case: found the target
  }
  // ...
}

Now we can write the recursive case. We need to search the rest of the array, which is a smaller version of the same problem. We can call linearSearch on the subarray that excludes the first element:

public static boolean linearSearch(int[] arr, int target) {
  if (arr.length == 0) {
    return false;  // base case: array is empty so target is not found
  } else if (arr[0] == target) {
    return true;  // base case: found the target
  } else {
    // recursive case: search the rest of the array
    int[] rest = Arrays.copyOfRange(arr, 1, arr.length);
    return linearSearch(rest, target);
  }
}

We are copying the array on every recursive call, and that is the same waste we saw with binary search. The fix is the same too: keep the one array and pass an index that says where the current call should start looking. Binary search needs two bounds because it narrows the range from both ends. Linear search only moves the start of the range forward, so one index is enough. Here is how that would look:

public static boolean linearSearch(int[] arr, int target, int start) {
  if (start >= arr.length) {
    return false;  // base case: reached the end of the array
  } else if (arr[start] == target) {
    return true;  // base case: found the target
  } else {
    // recursive case: search the rest of the array
    return linearSearch(arr, target, start + 1);
  }
}

Notice the start parameter that keeps track of the current index we are checking. The empty-array base case turned into start >= arr.length, which says the same thing: there is nothing left in the range this call searches. A client who wants to search the whole array can call this method with start = 0:

int[] numbers = {3, 9, 14, 21, 28, 33, 42, 55};
int target = 14;
boolean found = linearSearch(numbers, target, 0);
System.out.println("Target found: " + found);