Thread: Linear Search: the recursive way.

Like I said, doing it from the front is a bit more complicated, although the steps are basically going to be the same, now it involves checking recursive return and pointer arithmatic. Interestingly, the check could be tossed out if instead of using the invalid return -1, we use the invalid return size (since there is no array[size] in an array of size elements).

int linearSearch(const int array[], int key, int size)
returns the index of the first occourance of key

1) if size = 0, return error
2) if the first element of the array is it, then return 0
3) otherwise, check the array starting at the next element
and return 1 + the answer from that
3b) handle error

Code:

int linearSearch(const int array[], int key, int size)
{
 int n;
 if (size == 0) return -1;
 if (*array == key) return 0;
 n = linearSearch (array + 1, key, size - 1);
 if (n != -1) n ++;
 return n;
}

For the sake of explanation, I'm gonna go ahead and step through this.

Code:

int main (void)
{
 int x;
 int array [] = {3, 8, 2, 6, 9};
 x = linearSearch (array, 2, 5};
 return 0;
}

Code:

x = linearSearch ({3 8 2 6 9}, 2, 5);
  size != 0, *array != key, so we search the array {8 2 6 9}
  n = linearSearch({8 2 6 9}, 2, 4);
    size != 0, *array != key, so we search the array {2 6 9}
    n = linearSearch({2 6 9}, 2, 3);
      size != 0, but *array == key, so key is the 0 element of this
      array, so we return 0
    n = 0; key was the 0th element of {2 6 9}, so it's the 0 + 1
    element of this array (1)
    so we return 1
  n = 1; key was the 1st element of {8 2 6 9}, so it's the 1 + 1
  element of this array (2)
  so we return 2
x = 2;