Find Array Item Recursively

[Husker]

I'm having trouble with my latest assignment. The purpose is to return the index of the first item with more than one entry in the array using recursion (directly), cannot use for, while, etc. The parameters for this function are limited to array name and size. I am allowed to use a helper function but it also has to use recursion. For the life of me, I cannot figure out how to search the array from the beginning of the list using recursion to ensure I return the first index and not a later index. I'm not looking for someone to code this, I just need a hint or two. My code to this point is below.

int IndexMatch(int arr[], int size)
{
	if(size < 2)
		return -1;

	int cursor = Compare(arr, size-1, arr[size-1], size-1);
	
	if(cursor > -1)
		return cursor;
	else
		return IndexMatch(arr, size-1);
}
//helper function definition
int Compare(int arr[], int size, int target, int curs)
{
	if(size < 1)
		return -1;
	else if(target == arr[curs-1])
		return curs-1;
	else
		return Compare(arr, size - 1, target, curs-1);
}

[jsmith]

If the array is sorted the problem is much easier. I don't know if it is, because you didn't say.
Assuming it is not, you will need a couple of recursive functions. Here is a non-recursive
version of the algorithm you need:

for( int first_idx = 0; first_idx < size; ++first_idx )
    for( int second_idx = first_idx + 1; second_idx < size; ++second_idx ) 
         if( arr[ first_idx ] == arr[ second_idx ] )
             return first_idx;

// If the loop never returns, a match was not found...
return -1;

You need to code this recursively. Since you are not allowed to use looping, and since
I used two for() loops, you will need two recursive functions.

[Husker]

Thanks. The non-recursive version works well but I'm still stuck on how to recursively increase first_idx. Any time I initialize this variable in the recursive version it is reinitialized when I call the function recursively.

This is what I believe should happen, assume size 10. Index starts off pointed to arr[0]. The compare function compares arr[0] to arr[1-9]. If it matches it returns index of 0, if not it returns to indexMatch and then indexMatch is called recursively decrementing size (IndexMatch(arr, size-1). compare is then called again, index now points to arr[1] and compare compares arr[1] to arr[2-9], etc. until answer is found or size < 2, which returns -1. Is this not an accurate view of how this should work recursively? I'm obviously missing something.

[jsmith]

Yes, that sounds right.

[Husker]

Got it, thanks.

const int IndexMatch(const int arr[], const int size)
{
	//base case one
	if(size < 2)
		return -1;
	//base case two
	if( Compare(arr, size - 1, arr[0], 1) )
		return 0;

	//track index
	int index = IndexMatch(arr + 1, size - 1);
			
	if( Compare(arr, size-1, arr[0], index+1) )
		return index;
	else			
		return 1 + index;
}
//helper function - looking for match in array
bool Compare(const int arr[], const int size, int target, int index)
{
	if(size < 1)
		return false;
	else if(target == arr[index])
		return true;
	else
		return Compare(arr, size - 1, target, ++index);
}