Recursive function to get the minimum maximum and sum of an array of integers

Question

Hello I'm struggling a little bit, I can't really figure out how to initialize my *min *max and *sum variables so that it doesn't keep reinitializing in the loop

I did this and I'd like to get help regarding what changes I should make

void min_max_sum_rec(int arr[],int length,int *min,int *max,int *sum){

    if(length==1){
        return;
    }
    else{
        if(arr[0]<*min){
            *min = arr[0];
        }
        if(arr[0]>*max){
            *max = arr[0];
        }
        sum+=arr[0];
    }
    min_max_sum_rec(arr+1,length-1,min,max,sum);
}

for reference my professor did this:

void min_max_sum(int arr[],int length,int *min,int *max,int *sum){

    if(length== 1){
        *min=*max=*sum=*arr;
         return;
    }
    min_max_sum(arr+1,length-1,min,max,sum);

    *sum+=arr[0];
    *min = (*min<arr[0]?*min:arr[0]);
    *max = (*max>arr[0]?*max:arr[0]);
}

but I don't really understand since *min *sum and *max are not initialized and also can't understand the if statement.

Wouldn't it make it so that when we only have an array with one integer *max *min and *sum would have the same value so all we did before would be meaningless ?

Maybe your teacher expects the function to be (initially) called with min_max_sum_rec(array, length, INT_MAX, INT_MIN, 0); — pmg
– pmg, Commented Oct 7, 2021 at 17:49
"for reference my professor did this:" Did what? The last piece of code? Please edit your question — 4386427
– 4386427, Commented Oct 7, 2021 at 18:32
@pmg No... The function expects a pointer So you can't pass INT_MAX! And btw... pointers to uninitialized values are fine (in the last code example) — 4386427
– 4386427, Commented Oct 7, 2021 at 18:34

4386427 · Accepted Answer · 2021-10-07 19:53:12Z

1

I assume this is your professors code:

void min_max_sum(int arr[],int length,int *min,int *max,int *sum){

    if(length== 1){
        *min=*max=*sum=*arr;
         return;
    }
    min_max_sum(arr+1,length-1,min,max,sum);

    *sum+=arr[0];
    *min = (*min<arr[0]?*min:arr[0]);
    *max = (*max>arr[0]?*max:arr[0]);
}

and it's fine. But the documentation must clearly state that the function is only allowed to be called with values of n being greater than zero.

You ask:

Wouldn't it make it so that when we only have an array with one integer *max *min and *sum would have the same value so all we did before would be meaningless ?

Well, no... because we did not do anything before!

Notice that all the comparision for max/min and the sum calculation is after the recursion ends.

In other words - the code keeps making recursive calls with shorter and shorter array until there is only one element. The value of that element (which is the last element of the original array) is then used for initializing max/min/sum. As the recursive calls return it's checked whether a previous element is larger/smaller in order to update max/min and also updates sum.

It's a nice and simple implementation but....

This task should never be solved using recursion

You should ask your professor for an assignment where recursion actually makes sense.

edited Oct 7, 2021 at 19:53

answered Oct 7, 2021 at 18:45

4386427

44.7k4 gold badges44 silver badges69 bronze badges

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

2 Comments

Fang Yuan Over a year ago

Thank you, you really helped me understand what he did there

4386427 Over a year ago

@Bob__ Well, adding an assert would be fine but it's not really solving anything... it just makes the program crash. So it's a documentation thing... the documentation needs to state: "When calling this function n must be greater than zero; otherwise the behavior is undefined" (or similar)

Vlad from Moscow · Accepted Answer · 2021-10-07 17:59:55Z

0

The function can look the following way

void min_max_sum_rec( const int a[], size_t n ,int *min, int *max, int *sum )
{
    if ( n )
    {
        min_max_sum_rec( a + 1, n - 1, min, max, sum );

        if ( n == 1 ) 
        {
            *min = a[0];
            *max = a[0];
        }
        else
        {       
            if ( a[0] < *min ) *min = a[0];   
            if ( *max < a[0] ) *max = a[0];
        }
        *sum +=  a[0];
    }
    else
    {
        *min = *max = *sum = 0;
    }
}

That is the function at first calls itself until it gets an empty sub-array. In this case it initializers the objects *min, *max, and sum and returns to the caller.

As for your function implementation then at least this if statement

if(length==1){
    return;
}

does not make a sense.

Also this modified if statement

if(length== 1){
    *min=*max=*sum=*arr;
     return;
}

is general incorrect because the use can pass to the function an argument for the parameter length equal to 0.

And this call

min_max_sum_rec(arr+1,length-1,min,max,sum);

shall be within the else statement.

Note: In the initial code I had a typo using sum instead of *sum.

edited Oct 7, 2021 at 17:59

answered Oct 7, 2021 at 17:37

Vlad from Moscow

313k27 gold badges204 silver badges358 bronze badges

24 Comments

Fang Yuan Over a year ago

Thank you very much for your help

Vlad from Moscow Over a year ago

@EricPostpischil You are right. I have seen this at the last moment. The function has been updated.

Eric Postpischil Over a year ago

In general, a reduction operation can be initialized with its identity element. For addition, that is zero. For multiplication, it is one. For minimum of int, it is INT_MAX. (For minimum of real numbers, it is ∞.) For maximum of int, it is INT_MIN. (For reals, −∞.) Generally the reduction of an empty set should be considered to be the identity element, so the zero case ought to set *min to INT_MAX, *max to INT_MIN, and sum to zero. Then this also serves as the base case, eliminating the need to treat length 1 separately.

4386427 Over a year ago

Why do the recursion to n == 0 ? Stop at 1. See the example in the question. Much easier

4386427 Over a year ago

"the use can pass to the function an argument for the parameter length equal to 0." hmmm or -1, -2, etc. I guess the "contract" is n > 0

|

Collectives™ on Stack Overflow

Recursive function to get the minimum maximum and sum of an array of integers

2 Answers 2

2 Comments

24 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

24 Comments

Your Answer

Sign up or log in

Post as a guest

Related