Is there a way to find the INDEX of the minimum value in an array using a recursive function? C++

Question

I need to find the Index of the minimum number in an array using a recursive function in c++ the function can only get 2 parameters: the pointer to the array and the size of it.

int smallest(int arr[], int num);

I managed to do this but with a helper variable that is static and declared outside the function here is what I got:

static int flag = 0;
int smallest(int* arr, int num) {
   if (flag == num - 1)
      return flag;
   if (arr[num - 1] > arr[flag]) {
      return smallest(arr, num - 1);
   } else {
      flag++;
      return smallest(arr, num);
   }
}

Now my question is can I do this without the static variable or any other variable other than the num? here is what I got so far:

int smallest(int arr[], int num) {
    if (arr != &arr[num - 1])
        if (*arr < arr[num - 1])
            smallest(arr, num - 1);
        else
            smallest(arr + 1, num);
    return num - 1;
}

It doesn't return the index of the minimum value but it does get to its adress, the function ends when the array pointer address is the same as the address of the minimum value. how can I get it to return the index?

I'm a student and I'm pretty new to C++ I appreciate the help! thanks!

===

edit:

this is originally from a homework assignment but the constraint to not use external help variables or functions is mine! and I'm curious to know if its even possible.

the function can only get 2 parameters Whose constraint is that? — R Sahu
– R Sahu, Commented Feb 12, 2020 at 23:24
arr != &arr[num - 1] should be arr != (arr + num - 1). *arr < arr[num - 1] should be *arr < *(arr + num - 1) or arr[0] < arr[num - 1]. Better not to mix and match the * and [] notations. — okovko
– okovko, Commented Feb 12, 2020 at 23:26
If you can get the address, the index is address - arr. subtracting pointers give you the difference in number of elements between the two pointers. Obviously this is meaningless if the two addresses are not in the same array. — user4581301
– user4581301, Commented Feb 12, 2020 at 23:28
With your constraint, the only way I can think to do this is to return a difference between arr and a call to smallest, where smallest returns a pointer within arr. — okovko
– okovko, Commented Feb 12, 2020 at 23:28
You have an array int[N]. You want to find the index of the smallest element. You can ask Someone Else to find the index of the smallest element of an array int[N-1]. How will you do it? — Beta
– Beta, Commented Feb 12, 2020 at 23:36

Kevin Anderson · Accepted Answer · 2020-02-13 05:18:20Z

2

Because this is obviously homework, I'm not going to reveal the ACTUAL answer in entirety, but I'll give some (hopefully) good advice.

With recursion, think first of what your end condition is. That should be an array of 1 element. You return the index 0 in that case because of the array you have, it's the only element, so return the index of it.

if(num == 1)
{
    return 0;
}

So then how is that useful to you? Compare it to exactly one other element. That's how you break this down. Your array turns into "one element and MANY" or "It's just one element." If it's just one, return the only value. If it's many, call yourself recursively from the second element (index 1) onward:

int restOfArraySmallest = smallest(arr+1, num-1) + 1;

You need the +1 because you've offset where it starts from. But you know the value in restOfArraySmallest is the index into YOUR arr of the smallest value of everything except the first element. Because your recursive calls don't include the first element, just the rest.

Hopefully that's enough to get you the rest of the way.

Edit: Because the OP has responded and said it wasn't essential to their homework assignment, here's the entire function:

// Recursively finds the index of the smallest element of the passed-in array
int smallest(int* arr, int num)
{
    if(num <= 1)
    {
        return 0;  // If we're in the last element, the smallest is the only element
    }
    // More than one element, so find the least element in all the elements
    // past the first element of the array
    // Note: the index returned is offset from our current view of the array,
    //       so add +1 to any returned result so we can index directly from it
    int restOfArraySmallest = smallest(arr+1, num-1) + 1;

    // Compare the first element in the array to the smallest of the entire rest
    // of the array:
    if(arr[0] < arr[restOfArraySmallest])
    {
        // The first element is smaller, it's the smallest, so return that index
        return 0;
    }
    else
    {
        // The element already found is smaller, so return that index.  It's already
        // correctly offset
        return restOfArraySmallest;
    }
}

And that's it. If there's duplicate entries for smallest, it will favor the LAST one.

The trick with recursion is to NOT keep external variables. What you pass as the arguments and RETURN BACK are all the information you have. For some algorithms, it's enough.

Note, if you use recursive functions with datasets big enough, you will eventually get a Stack Overflow. Not the website, the crash type. This algorithm is pretty light in that only one extra variable and the two arguments themselves get allocated each pass, but it adds up eventually.

edited Feb 13, 2020 at 5:18

answered Feb 12, 2020 at 23:43

Kevin Anderson

7,0884 gold badges35 silver badges56 bronze badges

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

2 Comments

Meir Roth Over a year ago

Thank you Kevin for your help! I spent today at least 5 hours trying to figure it out! you are correct about the homework but its not required for the assignment to not use an additional variable so my first solution is good for that, however because I'm curious and I wanted to challenge myself I tried to find a solution, but I still can't figure out how to keep a "counter" in a recursion function to keep track of the round number. or how to go back in a recursive function. thanks

Kevin Anderson Over a year ago

Edited it with the full function. I hope it makes sense how I don't need an extra global variable. If you found it useful, please mark it as the accepted answer.

Collectives™ on Stack Overflow

Is there a way to find the INDEX of the minimum value in an array using a recursive function? C++

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related