how to find the maximum and minimum in an array using structures and recursion in C

Question

I have the following functions that find the maximum and minimum in a matrix, how can I add a structure with min and max to be able to do only a function that finds minimum and maximum ?

int maximum(int array[], int index, int len) 
{
    int max;

    if(index >= len-2)
    {
        if(array[index] > array[index + 1])
            return array[index];
        else
            return array[index + 1];
    }




    max = maximum(array, index + 1, len);

    if(array[index] > max)
        return array[index];
    else
        return max;
}

int minimum(int array[], int index, int len)
{
    int min;

    if(index >= len-2)
    {
        if(array[index] < array[index + 1])
            return array[index];
        else
            return array[index + 1];
    }

    min = minimum(array, index + 1, len);

    if(array[index] < min)
        return array[index];
    else
        return min;
}

Why use recursion for this? This will consume a lot of stack space.. -- At least you should split the remaining range in half each time (but you can do this in a single loop). — Danny_ds
– Danny_ds, Commented Feb 26, 2019 at 17:15
In that case you should split the remaining range in half on each iteration, and call the function for both halves. For example: for 1 million items this will result in a 'recursion depth' of around 20 instead of 1 million..) — Danny_ds
– Danny_ds, Commented Feb 26, 2019 at 17:19
In the real-world, recursion is usually very expensive, so should be avoided. Some people like to use it as a thought-exercise to begin tackling a problem, however. It also seems to be used in dealing with folder/path 'trees' such as would be found in Windows Explorer. — JosephDoggie
– JosephDoggie, Commented Feb 26, 2019 at 17:22
@JosephDoggie You mean stack space and function calls aren't free of charge? ^^ — Swordfish
– Swordfish, Commented Feb 26, 2019 at 17:31

Swordfish · Accepted Answer · 2019-02-26 17:32:07Z

1

#include <assert.h>
#include <stddef.h>
#include <stdio.h>

typedef struct minmax_tag {
    int min;
    int max;
} minmax_t;

minmax_t get_minmax(int const *data, size_t length)
{
    assert(length);

    minmax_t minmax = { data[0], data[0] };

    for (size_t i = 1; i < length; ++i) {
        if (data[i] < minmax.min)
            minmax.min = data[i];
        if (data[i] > minmax.max)
            minmax.max = data[i];
    }

    return minmax;
}

int main(void)
{
    int foo[] = { 12, 484, 487, 1, 500 };
    minmax_t result = get_minmax(foo, sizeof(foo) / sizeof(*foo));
    printf("Min: %d\tMax: %d\n\n", result.min, result.max);
}

Sowwy, recursive:

#include <assert.h>
#include <stddef.h>
#include <stdio.h>

typedef struct minmax_tag {
    int min;
    int max;
} minmax_t;

minmax_t get_minmax_impl(int const *data, size_t pos, size_t length, minmax_t previous)
{
    if (pos == length)
        return previous;

    if (data[pos] < previous.min)
        previous.min = data[pos];
    if (data[pos] > previous.max)
        previous.max = data[pos];

    return get_minmax_impl(data, pos + 1, length, previous);
}

minmax_t get_minmax(int const *data, size_t length)
{
    assert(length);

    minmax_t previous = { data[0], data[0] };
    return get_minmax_impl(data, 1, length, previous);
}

int main(void)
{
    int foo[] = { 12, 484, 487, 1, 500 };
    minmax_t result = get_minmax(foo, sizeof(foo) / sizeof(*foo));
    printf("Min: %d\tMax: %d\n\n", result.min, result.max);
}

edited Feb 26, 2019 at 17:32

answered Feb 26, 2019 at 17:18

Swordfish

13.2k3 gold badges24 silver badges47 bronze badges

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

3 Comments

Danny_ds Over a year ago

I wonder what the maximum length of the array would be for the recursive version.

Swordfish Over a year ago

@Danny_ds Depends on the sizeof(size_t) and available space on the stack. Well, more on available stack space.

Danny_ds Over a year ago

I know, but the 'depth' will be N instead of logN.. It would be better to split in 2 on each iteration.

Bob__ · Accepted Answer · 2019-02-26 20:52:00Z

As noted in the comments by Danny-ds, if you really need to do this using recursion (for didactic purpose), at least use a divide and conquer technique to limit the stack consumption to O(ln(n)).

In the following I'll create a function which accepts a range defined as a pointer first to the first element of an array (or subarray) and a pointer last to past one the last element of the same array (or subarray). Note that those two pointer can be safely compared, but last shouldn't be dereferenced.

This function returns a struct which aggregates two pointers to the min and max values. If the passed array is empty (when first == last, with this convention) those pointers are set to last and this condition should be checked before using the struct.

#include <stdio.h>

typedef struct {
    int *min;
    int *max;
} min_max_t;

min_max_t min_max_element(int *first, int *last)
{
    // First check if the range is at least two elements wide, to stop the recursion.
    if ( first == last  ||  first + 1 == last )
        return (min_max_t){first, first};

    // Then apply the algorithm to two sub-range
    int *middle = first + (last - first)/2;
    min_max_t left = min_max_element(first, middle);
    min_max_t right = min_max_element(middle, last);

    // No need to compare 'right.min' with 'left.max' or 'right.max' with 'left.min'
    if ( *(right.min) < *(left.min) )
        left.min = right.min;

    if ( *(right.max) > *(left.max) )
        left.max = right.max;

    return left;
}

// Helper function to print the result. The only part which is really necessary is
// the check before accessing the resulting struct.
void print_min_max(size_t n, int *arr)
{ 
    int *arr_end = arr + n;
    min_max_t result = min_max_element(arr, arr_end);
    if (result.min != arr_end)
        printf("Min: %d\tMax: %d\n", *(result.min), *(result.max));
    else
        puts("Error: invalid array.");
}

int main(void)
{
    int a1[] = { 1, 2, 3, 4, -5 };
    print_min_max(5, a1);               // -> Min: -5   Max: 4

    int a2[] = { 4, 2, 1, 4, -2, 0 };    
    print_min_max(6, a2);               // -> Min: -2   Max: 4

    int *a3 = NULL;    
    print_min_max(0, a3);               // -> Error: invalid array.

    int a4[] = { 1 };    
    print_min_max(1, a4);               // -> Min: 1    Max: 1

    int a5[] = { 2, 2, 2, 2 };    
    print_min_max(4, a5);               // -> Min: 2    Max: 2
}

Collectives™ on Stack Overflow

how to find the maximum and minimum in an array using structures and recursion in C

2 Answers 2

Sowwy, recursive:

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Sowwy, recursive:

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related