Using recursion to search through an array

[glendavis]

This is supposed to return the index of the first empty string in the array using recursion. Instead of returning the index of the FIRST empty string, this function I wrote returns the index of the LAST empty string. I have no idea how to search from the beginning of the array.

int firstEmpty(const string a[], int n)
{
	if (a[n-1].empty())
		return n-1;
	if (n > 0)
	{
		return firstEmpty(a, n-1);
	}
	return -1;
}

[VernonDozier]

How about changing the function to take three arguments? In addition to the two arguments you already have (pointer to the beginning of the array and the size of the array), include a third argument: firstElementNotTested. The original call would have firstElementNotTested equal to 0, since no elements would have been tested yet. However, if that first element was not empty, firstElementNotTested would be incremented and the function recursively called with the new incremented value. You would test for emptiness on the array element with index firstElementNotTested rather than index n - 1 as you do now.

[glendavis]

How about changing the function to take three arguments? In addition to the two arguments you already have (pointer to the beginning of the array and the size of the array), include a third argument: firstElementNotTested. The original call would have firstElementNotTested equal to 0, since no elements would have been tested yet. However, if that first element was not empty, firstElementNotTested would be incremented and the function recursively called with the new incremented value. You would test for emptiness on the array element with index firstElementNotTested rather than index n - 1 as you do now.

Is there any other way? I don't think I am supposed to add parameters to the function.

[VernonDozier]

I can think of a few ways where, if you KNOW that there is definitely an empty string, it will work. I can think of one way where it will work regardless. You will decrement n each recursive call, as you do. However, you will, instead of passing the address of a each time, which is the address of a[0], you will pass it the address of a[0]. then a[1], then a[2], etc. However you'll refer to a[1] or a[2] or whatever as the new a[0] since it is treated as the front of the array.

[glendavis]

Thanks, you can remove that code now.

Also, why do you put

return 1 + firstEmpty(&a[1], n-1);

why do you need the 1?

[VernonDozier]

I'll put the code back up. It's a learning forum so more people will learn if I put it up, plus everyone looking at this thread will be confused if I don't. I think it's OK since you did post code.

int firstEmpty(string a[], int n)
{
    if (a[0].empty())
		return 0;
    else if (n > 0)
  		return 1 + firstEmpty(&a[1], n - 1);
    else 
                return -999;    // changed flag since -1 no longer works as flag.
}

I added the 1 because if I didn't, I couldn't think of any way to keep track of how many times the function had been recalled recursively. Without the 1 there it would just return 0 when it hit the first empty string.

[glendavis]

For this, I have to return the index of the smallest value in the array. This code I wrote does not work. Can someone tell me what I'm doing wrong?

int smallestValue(const string a[], int n)
{
	int least;
	if (n==0)
		return -1;  // If the array is empty, return -1
	if (n == 1)
		int least = 0;
	if (n > 0)
	{
		least = smallestValue(a, n - 1);
		if (a[n-1] < a[least])
			return n;
		else
			return least;
	}
	return -1;
}

[VernonDozier]

I might be able to tell you what you're doing wrong, but I don't know how to make it right. ;) Hopefully someone else can.

First, you are trying to find the index of the "smallest" string. Have you defined what you mean by "smallest"? Does that mean alphabetical order? The "compare" function has already been written for you but you'll want to make sure it does what you want. I think it is based on ASCII values. You may have to write your own function to decide which of two strings is smaller.

http://www.cplusplus.com/reference/string/string/compare.html

Regardless, you do need to use some compare function You are trying to compare two strings in line 11 with the less_than sign. There is no '<' operator defined in the string class in C++. You would need to write your own. I think the "compare" function is the closest you can get. In lines 6 and 7:

if (n == 1)
	int least = 0;

the variable least is going to go out of scope immediately. You've defined it above in a wider scope so I would leave the "int" off of that line if you want to keep its value.

int smallestValue(const string a[], int n)
{
	int least;
	if (n==0)
		return -1;  // If the array is empty, return -1
	if (n == 1)
		int least = 0;
	if (n > 0)
	{
		least = smallestValue(a, n - 1);
		if (a[n-1] < a[least])
			return n;
		else
			return least;
	}
	return -1;
}