Recursion and Arrays

[thisguyehisaguy]

So, basically, I have never ever seen an example of a recursive function that takes only an array as its sole parameter and somehow manages to recursively return the index of its minimum element (if the minimum is repeated, the lowest index containing the minimum is returned). I suspect that this is not possible, and that at least one parameter would be required, namely, the size of the array. Am I right? Or is it actually possible!

Note: My lab professor seems to have assigned us several homework problems that lack any parameter for the size or index or a recursive function taking an array as one of its parameters. Depending on the input here I will search for a way to do so, or else, to complete the assignments in question by adding the necessary parameters.

I hope the question is clear. Please help!

[Aceix]

AFAIK, recursion can lead to fatal errors and buffer overflows, if not handled propely so I think it's not a good idea.

Aceix.

[thisguyehisaguy]

I'm not a "fan" of recursive functions, either. But I need to know if it's possible to do this, and if so, a helpful hint in the right direction.

[Catfish4]

Arrays decay to pointers, so yes you probably do need an extra parameter for size.
Unless the size is a hard-coded and you may take it for granted, e.g.:

const int SIZE = 40;
// or
#define SIZE 40

// later ...

int array[SIZE];

int zero(int *pi)
{
    for (int i=0; i < SIZE; ++i)
        pi[i] = 0;
}

[vlad from moscow]

You can write two overload functions. One that you will call in program will have one parameter of type reference to array. The other that will be called internally from the first one will have two parameters - pointer and the size of the arrray

For example (without testing)

template <typename T>
size_t min_element( const T *a, size_t n )
{
   if ( n == 1 ) return ( 0 );

   n = min_element( a + 1, n - 1 );

   return ( a[n+1] < a[0] ? n + 1 : 0 );
}
 
template <typename T, size_t N>
size_t min_element( const T ( &a )[N] )
{
   return ( min_element( a, N ) );
}

[Catfish4]

Solution in good old C from me.

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

int min_rec(const int *pci, size_t sz)
{
	assert(sz >= 2);

	if (sz == 2)
		return pci[0] < pci[1] ? pci[0] : pci[1];

	const int temp = min_rec(pci + 1, sz - 1);
	return pci[0] < temp ? pci[0] : temp;
}

void fill(int *pci, size_t sz, int min_value, int max_value)
{
	for (size_t i=0; i < sz; ++i)
		pci[i] = rand() % (max_value - min_value + 1) + min_value;
}

void print(const int *pci, size_t sz)
{
	printf("Array contains: ");

	for (size_t i=0; i < sz; ++i)
		printf("%d ", pci[i]);

	printf("\n");
}

int main(void)
{
	const size_t sz = 10;
	int ia[sz];

	srand(time(NULL));
	fill(ia, sz, -30, 30);
	print(ia, sz);
	printf("Min is: %d\n", min_rec(ia, sz));
}

[vlad from moscow]

@Catfish4

Your solution is 1) invalid and 2) does satisfy exactly the assignment.:)

[Catfish4]

I do not understand what you mean, Vlad.
Give more detail please.

[vlad from moscow]

Arrays can have only one element but your program will ignore such arrays. In the assignment there is said that the function must return an index of the minimal element not the minimal element itself.

[thisguyehisaguy]

Okay, guys, I appreciate the help... In my desperation I tried this:

int index = 0;
int getMin(double arr[]) {
    int min;
    if(index == 0) {
       min = index;
    }
    else {
        if(arr[index] < min) {
            min = index;
        }
    }
    getMin(arr[++index]);
    return min;
}

But it won't compile.... Note: I'm coding for a linux environment and it allows me to call the index of an array via a variable. Still having a lot of trouble with this... It's down to the wire and I was doing so well in my class until this homework!

[vlad from moscow]

Apart from syntaxical errors It is a stupid function.
I already showed how this function can be written.

[thisguyehisaguy]

Appreciate the input vlad, but the function that you wrote uses stuff that we have not gone over in class. Thanks, though, I'm still working on it.

[vlad from moscow]

You can remove all stuff that deals with templates. For example

size_t min_element( const int *a, size_t n )
{
   if ( n == 1 ) return ( 0 );

   n = min_element( a + 1, n - 1 );

   return ( a[n+1] < a[0] ? n + 1 : 0 );
}
 

const size_t N = 20;
size_t min_element( const int ( &a )[N] )
{
   return ( min_element( a, N ) );
}