MInimum element in array ( C )

Question

I'm a newbie both here in stackoverflow and both in the world of programming.

Today i was solving some exercise about recursion, and one of these asked to write a recursive function for finding minimum element of an array.

After many tries, I have finally wrote this working code, but i want to ask you if this is a "good" code. I mean, the fact it's working aside, is it written well? There's something that should be changed? And, above all, there's a way to make this functions working well without declaring that global int "min"? :)

Here's the code:

#include <stdio.h>

int recursiveMinimum(int array[], size_t size);

int min = 1000;

int main(void) {
  int array[] = {55, 5, 1, 27, 95, 2};

  printf("\nMinimum element of this array is: %d\n\n",
         recursiveMinimum(array, 6));
}

int recursiveMinimum(int array[], size_t size) {
  if (size == 1) {
    return min;
  } else {
    if (array[size] <= min) min = array[size];
    return min = recursiveMinimum(array, size - 1);
  }
}

Questions about whether code is good or bad are opinion-based, which is off-topic on this site. You may want to ask over on Code Review instead. But global variables used like this are generally not a good idea — UnholySheep
– UnholySheep, Commented Feb 3, 2022 at 15:59
And note that it actually doesn't work if the array is of size 1. recursiveMin({5}, 1) will return 1000 instead of 5. — Bill Lynch
– Bill Lynch, Commented Feb 3, 2022 at 16:01
" And, above all, there's a way to make this functions working well without declaring that global int "min"" add a new smallestSoFar parameter. — Alexander
– Alexander, Commented Feb 3, 2022 at 16:01
Your initial value should either be INT_MAX or one of the elements of your array. Imagine that all the values in your array are above 1000. Then you might give 1000 as a minimum while it's not even in your array. — Dominique
– Dominique, Commented Feb 3, 2022 at 16:04

Vlad from Moscow · Accepted Answer · 2022-02-03 16:34:37Z

1

It is a bad idea when a function depends on a global variable.

But in any case your function is incorrect and invokes undefined behavior.

In the first call of the function this if statement

if (array[size] <= min) min = array[size];

trying to access memory outside the passed array because the valid range of indices is [0, size).

Also the array can contain all elements greater than the initial value of the global variable

int min = 1000;

And the function may not be called a second time because the value of the variable min is unspecified.

The function should return the index of the minimal element in the array. In general the user can pass the second argument equal to 0. In this case again the function will invoke undefined behavior if you will try to return a non-existent element of an empty array.

The function can be declared and defined the following way

size_t recursiveMinimum( const int a[], size_t n ) 
{
    if ( n < 2 )
    {
        return 0;
    }
    else
    {
        size_t min1 = recursiveMinimum( a, n / 2 );
        size_t min2 = recursiveMinimum( a + n / 2, n - n / 2 ) + n / 2;

        return a[min2] < a[min1] ? min2 : min1;
    }
}

Here is a demonstration program

#include <stdio.h>

size_t recursiveMinimum( const int a[], size_t n )
{
    if (n < 2)
    {
        return 0;
    }
    else
    {
        size_t min1 = recursiveMinimum( a, n / 2 );
        size_t min2 = recursiveMinimum( a + n / 2, n - n / 2 ) + n / 2;

        return a[min2] < a[min1] ? min2 : min1;
    }
}

int main( void )
{
    int a[] = { 55, 5, 1, 27, 95, 2 };
    const size_t N = sizeof( a ) / sizeof( *a );

    size_t min = recursiveMinimum( a, N );

    printf( "\nMinimum element of this array is: %d at the position %zu\n",
            a[min], min );
}

The program output is

Minimum element of this array is: 1 at the position 2

Pay attention to that the first parameter has the qualifier const because the passed array is not being changed within the function. And to decrease the number of recursive calls the function calls itself for two halves of the array.

edited Feb 3, 2022 at 16:34

answered Feb 3, 2022 at 16:13

Vlad from Moscow

313k27 gold badges204 silver badges358 bronze badges

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

5 Comments

Cyro Over a year ago

Thanks Vlad! :) Just one question: what's that " * " inside of sizeof? A pointer? Because iIhave not arrived yet to study pointers xD

Vlad from Moscow Over a year ago

@Cyro It is the same as to write a[0] because this expression is evaluated like *( a + 0 ) that is the same as just *a.

Cyro Over a year ago

Uhmm, interesting. And is it necesary to do this division? I mean, you couldnt just do sizeof ( a ) to have the size of array? Sorry if it may seems banal xD

Vlad from Moscow Over a year ago

@Cyro Yes sizeof( a ) gives the size of the array. But you need to pass the number of elements in the array. The size of the array is calculated like sizeof( a ) = N * sizeof( int ) So to get the number of elements N you need to write N = sizeof( a ) / sizeof( int ) that is the same as N = sizeof( a ) / sizeof( *a ) because the type of the expression *a is int.

Cyro Over a year ago

Perfect, I got it. Thanks so much Vlad, you were really helpful! Have a good day ;P

mch · Accepted Answer · 2022-02-03 16:08:33Z

0

Recursion works by reducing the size at the call to the next iteration and comparing the result of the call with the current value and return the lower of the 2.

As recursion stop you can simply return the first element

int recursiveMinimum(int array[], size_t size) {
  if (size == 1) return array[0];
  int min_of_rest = recursiveMinimum(array, size - 1);
  if (array[size - 1] <= min_of_rest) return array[size - 1];
  return min_of_rest;
}

Full example: https://godbolt.org/z/sjnh8sYz3

answered Feb 3, 2022 at 16:08

mch

9,8243 gold badges33 silver badges46 bronze badges

Comments

Damien · Accepted Answer · 2022-02-03 16:42:42Z

In the past, we used to implement it with pointers, KR-C style.

Using pointers in a harsh way was a mean to deal with inefficiency of compilers at that time.

Not sure it is considered good practice now. An example is provided hereafter.

Anyway, it would be better (easier and more efficient) to implement it in a non recursive manner.

#include <stdio.h>
void recursiveMinimum(int *array, size_t size, int *min) {
    if (size == 0) return;
    if (*array < *min) *min = *array;
    recursiveMinimum (array+1, size-1, min);
    return;
}
int main(void) {
    int array[] = {55, 5, 1, 27, 95, 2};
    size_t size = sizeof(array)/sizeof(*array);
    int min = array[0];
    recursiveMinimum (array, size, &min); 
    printf("\nMinimum element of this array is: %d\n", min);
    return 0;
}

Collectives™ on Stack Overflow

MInimum element in array ( C )

3 Answers 3

5 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related