how can i return the index of an integer in an array using a recursive function?

Question

i have to find the index of an integer in an array using a recursive function this is what i have up to now:

#include <iostream>

int linear_search(int array[], int choice_, int size) {

    if (array[choice_] >= 0) {
        return array[choice_];
    }
    else {
        return -1;
    }
}

for example if the:

 int array[]= {3,4,7,8};

if i type that i want to search for number 3 it should give me the index of 0 but instead it gives me the number 8. can i get some advise please?

Possible duplicate: https://stackoverflow.com/questions/3909784/how-do-i-find-a-particular-value-in-an-array-and-return-its-index. I don't understand where the recursion should occur in your example — RoQuOTriX, Oct 18 '19 at 07:15
You need to derive some recurrence relationship for the solution of your problem. Such that: index of a value _v_ in a sequence _(3,4,7,8)_ is either 1 (if _v_ equals 3), or 1 + an index of _v_ in sequence _(4,7,8)_. Now, just translate this into C++ code (with arrays and zero-based indexing). — Daniel Langr, Oct 18 '19 at 07:24

score 1 · Answer 1 · answered Oct 18 '19 at 07:34

1

Recursion is about narrowing down a problem to a smaller problem.

In the case of this particular search, try to think of it in terms of the found-item being either in the first position in the array, or maybe in the remainder of the array. This then reduces the problem to searching a smaller array, until you either find the item or you hit the trivial case of an empty array.

int linear_search(int array[], int choice_, int size)
{
    // Array is empty -- not found
    if (size <= 0)
        return -1;

    // Found at position 0
    if (array[0] == choice_)
        return 0;

    // TODO: Search position in remaining array
    int pos = linear_search(/* USE BRAIN HERE */);

    // TODO: You may want to do something to the result before returning it

    return pos;
}

As you can see, I've left some parts for you to fill in. I have faith in you. You can do it!

Happy coding!

answered Oct 18 '19 at 07:34

paddy

60,864
6
61
103

I don't see how this will return the index of `choice_`. As I see it the return value is always 0 or -1. – Support Ukraine Oct 18 '19 at 07:40
This is because it requires the OP to make an effort by completing the missing parts. – paddy Oct 18 '19 at 07:41
You see, _"i have to write a recursive function to perform a linear search"_ is quite obviously a homework exercise intended for learning. Many beginners struggle with recursion, and this particular person is also struggling with array access. I think I've left out just enough to make them work for it and get an _"aha!"_ moment, while also providing enough framework to guide them there. – paddy Oct 18 '19 at 07:44
Hmm... well, okay - I do understand the idea that OP has to do some work to learn. But I'm not sure this answer will make OP able to solve the task. The "framework" seems a bit too complex for task to be solved. – Support Ukraine Oct 18 '19 at 08:28
Yes, I am serious. I doubt OP will figure out that pos needs to be incremented in an if statement when the returning starts. Further this is not needed if the array is searched backwards. Therefore I think this approach is unnecessarily complex. See the answer I added – Support Ukraine Oct 19 '19 at 05:07

score 0 · Answer 2 · answered Oct 18 '19 at 08:06

This is binary search. It is a recursive function.

int binary_search_recursive(const int b[], int search_key, int low, int high)  
{  
    if (low > high)  
        return -1;  

    int mid = low + (high - low) / 2;  

    if (search_key == b[mid])  
        return mid;     
    else if (search_key < b[mid])  
        return binary_search_recursive(b, search_key, low, mid - 1);    
    else  
        return binary_search_recursive(b, search_key, mid + 1, high);  
}

Why do you want binary search? The array is not sorted so you gain nothing except more complicated code — Support Ukraine, Oct 18 '19 at 08:13

Support Ukraine · Answer 3 · 2019-10-18T08:36:05.850

This code is wrong

if (array[choice_] >= 0) {
    return array[choice_];

When you do array[choice_] you are looking at the array value at index choice_. That is not what you want. Instead you want to find out if the array at some index is equal to choice_. That would be if (array[some_index] == choice_) return some_index;

Further, to make this a recursive approach, the function needs to call itself. Your code doesn't do that so it's not recursive.

Here is a recursive approach:

int searchArray(const int* array, const int choice_, const int size)
{
    if (size > 0)
    {
      if (array[size-1] == choice_) return size-1;  // Hit! Return the index
      return searchArray(array, choice_, size-1);   // Recursive call - pretend array is 1 shorter
    }
    return -1;
}

The code looks at the last element in the array.

If it is a hit it simply returns the index.
If it is not a hit, it calls itself but decrements size to pretend that the array is one element shorter.

In this way it goes from the end of the array towards the start of the array while looking for choice_.

BTW: Notice that it's a very bad idea to use recursion for this task - never do that! Use a simple for loop. But I guess this is just another example of a very bad homework task...

is this way considered as linear search? recursion is very hard to understand, thanks for the advise! — cppnoob, Oct 19 '19 at 00:29
when you wrote ` int searchArray(const int* array, const int choice_, const int size)` the "const int*array " is the same as writing const int array[] right since pointers are basically arrays? — cppnoob, Oct 19 '19 at 00:47
@cppnoob Yes, it is a linear search. If the array is sorted you can do a better performing search like binary search but when the array is unsorted a linear search is required. — Support Ukraine, Oct 19 '19 at 04:58
@cppnoob Correct. The two ways of writing the array argument are the same. — Support Ukraine, Oct 19 '19 at 05:00

how can i return the index of an integer in an array using a recursive function?

3 Answers3