CODEWITHSUNDEEP
c++arraysrecursion
Eric after dark
Eric after dark

Reputation: 1808

C++: Runtime error with simple Recursive Search Function

So I have a program here that's supposed to do the very simple job of searching through an Array of 100 integers to find a specific key. The linearSearch function in this program is supposed to be recursive, so I have to call the function from within itself. The program compiles fine, but for some reason only returns the first element 0, in the array no matter what search key you put in. What am I not seeing? Thanks.

#include <iostream>
using namespace std;

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

int main()
{
    const int arraySize = 100; //size of array  
    int a[arraySize]; //create array a
    int searchKey; //value to locate in array a

    for(int i = 0; i < arraySize; i++)
            a[i] = 2 * i; //create data

    cout << "Enter integer search key: ";
    cin >> searchKey;

    //attempt to locate search key in array a
    int element = linearSearch(a, searchKey, arraySize);

    //display results
    if(element != -1)
               cout << "Found value in element: " << element << endl;
    else
               cout << "Value not found" << endl;

    system("pause");   
}

//linearSearch Function ****Returns 0 as index all the time *************
int linearSearch(const int array[], int key, int sizeOfArray)
{
    static int index = 0;

    //if Out of range, return -1 (Value not found)
    if(index >= sizeOfArray){return -1;}

    //if array value = key, array index is returned
    if(array[index] == key){return index;}

    //if array value is not equal to key, add to index and call func again                
    if(array[index] != key)
    {
                    index++;
                    linearSearch(array, key, sizeOfArray);                
    }   
}

I'm taking the correct approach by declaring index as static, right?

~Thanks a lot, you guys were quick and a HUGE help. =)

Upvotes: 0

Views: 357

Answers (4)

taocp
taocp

Reputation: 23634

You can also change your search function to the following without using static local variable index.

int linearSearch(const int array[], int index, int key, int sizeOfArray)
{
   //if Out of range, return -1 (Value not found)
   if(index >= sizeOfArray){return -1;}

   //if array value = key, array index is returned
   if(array[index] == key){return index;}

   //if array value is not equal to key, add to index and call func again                
    return linearSearch(array, index + 1, key, sizeOfArray);                
 }

The only change is that you are passing the starting index into the search function.

Upvotes: 1

JBL
JBL

Reputation: 12907

When doing this type of search recursively, you must propagate the index you're currently at in your array.

The way you're doing it, there's a global variable, index which is the same in every call to your function because of the static keyword.

The index should rather be a parameter, and each time you call the function recursively, you pass index+1 as a parameter.

Also, you must return the value of the recursive calls, otherwise it just does nothing and doesn't store/process the returned value.

Upvotes: 1

john
john

Reputation: 87959

Your mistake is that

if(array[index] != key)
{
    index++;
    linearSearch(array, key, sizeOfArray);                
}

should be

if(array[index] != key)
{
    index++;
    return linearSearch(array, key, sizeOfArray);                
}

You don't return any value when the key is not equal.

Plus the static index is bad, as has already been said.

Upvotes: 4

NPE
NPE

Reputation: 500367

I'm taking the correct approach by declaring index as static, right?

No. Rather, index should be an argument to the recursive function.

Due to the static state, the function is hard to test and is not thread-safe. Furthermore, it inadvertently keeps state between invocations, meaning that if you were to call it a second time, it wouldn't work (since index would still have the old value).

Upvotes: 3

Related Questions