CODEWITHSUNDEEP
arrayscrecursionminfunction-definition
Cyro
Cyro

Reputation: 1

MInimum element in array ( C )

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);
  }
}

Upvotes: 0

Views: 1963

Answers (3)

Damien
Damien

Reputation: 4864

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;
}

Upvotes: 0

Vlad from Moscow
Vlad from Moscow

Reputation: 311088

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.

Upvotes: 1

mch
mch

Reputation: 9814

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

Upvotes: 0

Related Questions