Sequential Search Recursively

In Chapter 4 we wrote code for sequential search using a loop. The code for sequential search on an array of characters can be written recursively:

public static int seqSearch(char what, char[] anArray){
   return seqSearch(what, anArray, 0);
}

private static int seqSearch(char what, char[] anArray, int loc){
   if (loc >= anArray.length){
      return -1; //signal `not found` condition
   }
   else{
      if (what == anArray[loc]){
          return loc;
      }
      return seqSearch(what, anArray, loc + 1);
    }
}

Notice how we need to track the location in the array. We do this with a parameter to the recursive method. Then to ensure that our original method’s signature remains unchanged, we call the recursive submethod from the wrapper.

Practice Questions

1. Identify the base case(s) in the sequential search recursive method.

2. Identify the recursive call(s) in the sequential search recursive method.

3. Explain how the recursive call(s) move(s) toward base case(s) in the sequential search recursive method.

4. Give the signature of the wrapper.

5. Draw a visualization of the call seqSearch('R', {'a', 'R', 'b', 'R'}, 0).

6. Is seqSearch tail recursive? Why or why not?

To Solutions