C++: Runtime error with simple Recursive Search Function

Question

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. =)

No, a static index is almost certainly a bad idea. It's effectively a global variable which never gets reset. — Oliver Charlesworth
– Oliver Charlesworth, Commented Apr 1, 2013 at 14:34
'Am I taking the right approach?' Definitely not, it should be a parameter. — john
– john, Commented Apr 1, 2013 at 14:34
No. It should be passed as a value parameter. Also, your function has no determinate return value on the tail-recurson resolution, so this stands no chance of working as is. — WhozCraig
– WhozCraig, Commented Apr 1, 2013 at 14:35
Surprisingly your code runs fine and gives correct results for me. — user995502
– user995502, Commented Apr 1, 2013 at 14:37
@stardust_ the behavior is undefined, since the function is being exited without a return. — Drew Dormann
– Drew Dormann, Commented Apr 1, 2013 at 14:40

john · Accepted Answer · 2013-04-01 14:36:29Z

4

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.

answered Apr 1, 2013 at 14:36

john

88.3k5 gold badges61 silver badges95 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Drew Dormann Over a year ago

The whole if line can go as well.

user995502 Over a year ago

Technically he doesn't have to return index there. Since it is static right now. As long as there is no code after that statement.

NPE · Accepted Answer · 2013-04-01 14:35:23Z

3

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).

answered Apr 1, 2013 at 14:35

NPE

503k114 gold badges970 silver badges1k bronze badges

Comments

taocp · Accepted Answer · 2013-04-01 14:45:03Z

1

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.

answered Apr 1, 2013 at 14:45

taocp

23.7k10 gold badges52 silver badges62 bronze badges

Comments

JBL · Accepted Answer · 2013-04-01 14:38:41Z

1

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.

answered Apr 1, 2013 at 14:38

JBL

13k5 gold badges56 silver badges88 bronze badges

Collectives™ on Stack Overflow

C++: Runtime error with simple Recursive Search Function

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related