Finding minimum element in array using recursion

Question

so I'm having trouble trying to understand how recursion of this code works.

int minimum(int array[], int size) {
    if (size == 1) {
        return array[0];
    }
    else {
        return (array[size] < int min = minimum(array, size - 1))? array[size] : min;
    }
}

int array[4] = {5, 99, 205, 1};
int smallest = minimum(array, 3); // 3 = index of the last element

Here is the explanation I saw: this function searches the lowest value in an int array by using recursion. At first it checks how many elements are in the array by checking if the size equals to 1 and then returns the first value as result. If the table is bigger than 1 (and technically also when lower) it compares the last value in the array with the recursive call with the rest of the array.

The recursion stops at the 0-index and then compares that value with the index 1. Then it compares the lowest value of index 0 and 1 with the value from index 3 and so on until it reaches last value.

But I still can't imagine how the recursion run in my head, especially min = minimum(array, size - 1) . Can someone be so kind to explain it to my slow brain how this code run in stack? Thank you so much.

That code is wrong – if (size == 1) should be if (size == 0). — Chronial
– Chronial, Commented Oct 28, 2020 at 14:20
@Chronial in this case size is index of last element though, so it is correct. — Nam Hoang
– Nam Hoang, Commented Oct 28, 2020 at 14:23

Chronial · Accepted Answer · 2020-10-28 14:45:48Z

1

I fixed the code (by accessing array[size-1] instead of array[size] and simplified it a bit (by using std::min).

int minimum(int array[], int size) {
    if (size == 1) {
        return array[0];
    } else {
        return std::min(array[size - 1], minimum(array, size - 1))
    }
}

int array[4] = {5, 99, 205, 1};
int smallest = minimum(array, 4);

Now you might be able to see that minimum(array, 4) is equal to std::min(array[3], minimum(array, 3)), is equal to std::min(array[3], std::min(array[2], minimum(array, 2))) ... is equal to std::min(array[3], std::min(array[2], std::min(array[1], array[0]))).

answered Oct 28, 2020 at 14:45

Chronial

71.9k14 gold badges100 silver badges108 bronze badges

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

Collectives™ on Stack Overflow

Finding minimum element in array using recursion

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related