# Linear Search: the recursive way.

• 01-12-2002
Nutshell
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.
• 01-12-2002
Sorensen
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; }```
• 01-12-2002
Nutshell
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
• 01-12-2002
Unregistered
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; }```
• 01-13-2002
Nutshell
Hi but i can only use two parameters: the array and its size and thats it?

is it possible ?

thnx
• 01-13-2002
QuestionC
*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.
• 01-14-2002
Nutshell
thnx thats clever

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

I wanna learn.
• 01-15-2002
QuestionC
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;```