Linear Search: the recursive way.

helo,

I want to modify a linear Search program which is currently using a loop to search for a number in an array to a recursive one. But don't know where to start. Pls direct. Thnx in advance. The current iterative version of linearSearch is :

Code:

#include <stdio.h>
#define SIZE 100

int linearSearch( const int [], int, int );

int main()
{   
   int a[ SIZE ], x, searchKey, element;

   for ( x = 0; x <= SIZE - 1; x++ )  /* create data */
      a[ x ] = 2 * x;

   printf( "Enter integer search key:\n" );
   scanf( "%d", &searchKey );
   element = linearSearch( a, searchKey, SIZE );

   if ( element != -1 )
      printf( "Found value in element %d\n", element );
   else
      printf( "Value not found\n" );

   return 0;
}

int linearSearch( const int array[], int key, int size )
{
   int n;

   for ( n = 0; n <= size - 1; ++n )
      if ( array[ n ] == key )
         return n;

   return -1;
}

To modify this code to recursive, i can pass two arguments to the function: 1. integer array 2. size of the array
Is it possible? Pls show.

Somethnig like -

Code:

int linearSearch( const int array[], int key, int size )
{
	int ret =-1;
	if (array[0]==key)
		ret=key;
	else
		if(size>0)
			ret = linearSearch(&array[1],key,size-1);
   
	return ret;
}

sorry i forgot to mention. I have the return the array subscript in which the searchkey is found, not the actual search key. Thats what troubling me.

thnx

Here's Sorensen's code modified to return the index of the array instead of the key.

Code:

int linearSearch( const int array[], int key, int size, int i )
{
  int ret = -1;
  if (array[i] == key)
    ret = i;
  else
    if(size > 0){
      ret = linearSearch(array, key, size - 1, ++i);
    }
   
  return ret;
}

Hi but i can only use two parameters: the array and its size and thats it?

is it possible ?

thnx

*shrug* sure....

Code:

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

Really, it might be easier to just have a wrapper function, or macro, which just takes care of tossing in the extra value instead of writing a function that doesn't use it.

This function that I've got basically starts at the back of the array and works up to the top. It's possible to go the other way with just 2 args, but it's a little more complicated if you want to handle the case where the element is not in the array.

thnx thats clever

but can you also show me to go from the beginning instead of doing from the back up?

I wanna learn.

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;