find maximum and minimum value from array using recurrsion

Question

I wrote a code to find the maximum and second maximum using recursion:

struct max_min
{
        int max;
        int min;
}obj;

int find_l_m(int a[], int size)
{
        int next_element;

        if (size == 1)
                return a[0];

        next_element = find_l_m(a, size-1);

        if (a[size-1] > next_element) {
                obj.max = a[size-1];
                obj.min = next_element;

                return a[size-1];
        } else {
                obj.max = next_element;
                obj.min = a[size-1];

                return next_element;
        }

}

int main()
{
        int a[] = {1, 11, 4, 9, 6, 7, 8, 10};

        find_l_m(a, sizeof(a) / sizeof(a[0]));
        printf("%d\n%d\n", obj.max, obj.min);
}

I have couple of query:

Can this be made more simple, should be able to return max and second max without using struct object.
How above code can be changed to find maximum (that it does) and minimum value from array

Using recursion for this particular purpose is a bad idea. Just iterating over the array once is going to be much more efficient in many ways. It is also poor design to use a global variable to store the results of a function. A better approach would be to write separate functions for highest and lowest, or returning multiple results in a pointer argument, or just sorting the array. — Cheatah
– Cheatah, Commented Oct 2, 2021 at 21:30
@Cheatah: Linear tail recursion captures iteration over an array quite well. — einpoklum
– einpoklum, Commented Oct 2, 2021 at 21:47
you're algorithm is wrong. For {10, 11, 1} it returns {11,1} what is not a valid pair for maximum and the second maximum. It looks that the code actually returns the minimum and the maximum of the array. — tstanisl
– tstanisl, Commented Oct 2, 2021 at 21:54
@Cheatah, scanning multiple times over the array may invalidate quite a lot of cache. It will likely degrage performance. If possible it is still better to find both statistics in one run — tstanisl
– tstanisl, Commented Oct 2, 2021 at 22:05

0___________ · Accepted Answer · 2021-10-02 21:46:49Z

1

recursion is good (assuming that it is good for anything) in finding max or min.

typedef struct 
{
        int max;
        int min;
}obj;

int max_min(int minmax, int arr[], size_t size)
{
    if(size == 1) return *arr;
    else 
    {
        int result = max_min(minmax, arr + 1, size - 1);
        if(minmax) return result <= *arr ? *arr : result;
        else return result >= *arr ? *arr : result;
    }
}

obj test(int *arr, size_t size)
{
    return (obj){max_min(1, arr, size), max_min(0, arr, size)};
}

int main(void)
{
    int arr[] = {1,4,9,3,2,-4,0,2,3};
    obj o = test(arr, sizeof(arr)/sizeof(arr[0]));

    printf("max = %d min = %d\n", o.max, o.min);
}

https://godbolt.org/z/zGrYMYjx7

answered Oct 2, 2021 at 21:46

0___________

71.6k4 gold badges41 silver badges94 bronze badges

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

1 Comment

Milan Over a year ago

@0___________, wanted to know, are we storing, structure member in {max_min(1, arr, size), max_min(0, arr, size)};} ?, and is it the first max_min(1, arr, size) return maximum value from array, right ?

Louen · Accepted Answer · 2021-10-02 21:49:23Z

To answer your first question:

Can this be made more simple, should be able to return max and second max without using struct object.

There are a couple of ways to return two (or more) values from one function in C. The first one, as you noted, is using a struct, this way:

// Define a struct holding two integers 
struct Pair_of_int {
    int a;
    int b;
 };


// Define a function returning a `PairOfInt`
struct Pair_of_int my_function(int[] a, int size) {
     struct Pair_of_int result;
     // Do some work
     result.a = /*...*/;
     result.b = /*...*/;
     return result;
 }

This is how you would call such a function in your main function :

struct Pair_of_int pair = my_function(...);
printf("First %d, second %d", pair.a, pair.b);

Note that this is not exactly what you have done in the code you've shown. In your code you have a global instance of your struct max_min that gets updated by the function. What you want is to use the structure as the return value of the function, as shown above.

The other way is to use pointers to return multiple values. Here if you want two ints you have to define your function to accept two pointers to int as arguments and use them to store the values.

void my_function(int[]a, int size, int* out_a, int* out_b) {
    // Do some work
    *out_a = /*...*/;
    *out_b = /*...*/;
}

Here as you can see the function returns nothing. Instead it uses the two pointers out_a and out_b to store the result. This is how you would use it in the main function :

int a; int b;
my_function(array, size, &a, &b);
printf("First %d, second %d", a, b);

You create two variables a and b that will hold the results and pass their address to my_function with the & operator.

How above code can be changed to find maximum (that it does) and minimum value from array

This is shouldn't be too hard if you get the first case working correctly. You have to keep track of the two values separately. You might have to add some more arguments to your function for it to work recursively.

einpoklum · Accepted Answer · 2021-10-02 21:51:48Z

1

Can this be made more simple, should be able to return max and second max without using struct object.

You could factor out the update of a min-max structure with a single value into a separate function. Then, you could probably make your recursive function into a one-liner.

How above code can be changed to find maximum (that it does) and minimum value from array

Well, you would need to:

return a struct max_min.
properly initialize your struct max_min (e.g. for the case of an empty array; defining the semantics appropriately).

answered Oct 2, 2021 at 21:51

einpoklum

137k86 gold badges445 silver badges917 bronze badges

Collectives™ on Stack Overflow

find maximum and minimum value from array using recurrsion

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related