Recursive function returns subscript of first negative element in array

[dhv]

int firstNegative(const double a[], int n)
{
	if (n < 1) return -1;
	if (a[0] < 0) return ???;
	return firstNegative(a+1, n-1);
}

I need help implementing this function that returns the subscript of the first negative element in an array. I'm not sure how to return the subscript, given that n represents the number of elements left to be re-evaluated. I tried some pointer arithmetic, but that didn't work out. Maybe I am taking entirely the wrong approach. I know this can be done with easily loops, but it is for an assignment on recursion. Thanks for any help!

[simeonz]

Recursion is very intuitive and this is ironically the hardest thing about it. Once you learn how to do things the constructive way, with loops and ect., seeing the solution in declarative form is hard.

For example, here are some hints for your problem:

If you find negative number in the first element, what index should you return?

Here you start breathing heavily, thinking about where the recursion starts, where it ends, how the recursion evolves, what was the problem again... Forget about that. Clear your mind and just answer the question. Let me repeat it.

If you find negative number in the first element, what index should you return?

Now the second question.

If you have found the desired index in the sub-array that starts from the second index of the original array, what do you return?

So, you have b[0] == a[1], b[1] == a[2]... b[n-1] == a[n]. b is the sub-array and a is the original array. You have found the index of the first negative element in b. This is the b-index though. You need the a-index of this very same element. You have to do something to the result that you got from the recursive call in order to get the a-index from the b-index.

Regards

PS: Keep in touch :)

[dhv]

I am still stuck. I tried a bunch of pointer arithmetic stuff but I'm lost.

Let's say I have an array of 10 digits, and a[2] is a negative number.
If I am 3 levels deep, c[0] == a[2], and n = 7. I don't see how I can get the index 2. I tried doing something where I subtract the last element from the current element but I don't have a count of the total amount of elements to get the index.

[Moschops]

If n is the number of elements left to check, start at the end and work backwards, so that at each level you are checking a[n-1].

[dhv]

But I am to return the FIRST index of negative value, not the last.

[simeonz]

What about adding something to the returned index on the way back? ;)
(Don't think of recursion as one way street - you don't have to return directly what is returned to you from the deeper levels. You can post-process the result.)

[Moschops]

You could create a value that remains the same in all calls to the function like this:

static int firstNegativeElement;

and then go through every element of the array from a[n-1] to a[0], and each time you find a negative value, firstNegative=[n-1]. When you've checked every element, return firstNegative.

Simeonz's scheme will work just as well; if you ask five coders how to do this, you'll get back more than five working solutions :p

[dhv]

We aren't allowed to use static variables. I'll try to figure out what simeonz meant in a little bit. Working on something else. Thanks for the help! Don't know if I get it yet, though!

[Moschops]

You could use a global variable outside the function to the same effect.

Let me guess, no global values either? :p

Edit: Really, no static variables? They're so useful in recursive functions that if they didn't already exist, we'd reinvent them.

[dhv]

Yep, no global variables.

So, my solution so calls another function we defined in a previous part of the assignment (I don't think this is breaking the rules, so I'll stick with this for now ;) )

int firstNegative(const double a[], int n)
{
	if (n < 1) return -1;
	if (a[n-1] < 0 && !anyNegative(a, n-2)) return n-1;
	return firstNegative(a, n-1);
}

[simeonz]

I must say I teased you excessively. But I wanted you to get involved. Actually, for the record, your solution works (if it is accepted). It is just slower.

This is what I think was expected:

int firstNegative(const double a[], int n)
{
        if (n < 1) return -1;
        if (a[0] < 0) return 0;
        return 1 + firstNegative(a+1, n-1);
}

Again, I have had mandatory classes on functional and logical programming languages, where recursion is king. So, do not think that the problem is easy the first time around.

Regards

[dhv]

No worries, I actually want to learn this stuff.

I honestly don't know why I didn't think of that, since I have other functions with exactly the line return 1 + somefunctioncall(). Thanks for the help, though. Can't believe this stumped me that long, what a mental work out.

[ne555]

I will use a wrapper

int negative(int *array, int size){
	int *neg=negative_w(array, size);
	return (neg)? (neg-array): -1;
}

int *negative_w(int *beg, int size){
	if(size==1)
		return (*beg<0)? beg: NULL;

	int *left, *right;
	int midpoint = (size/2);
	left = negative_w(beg, midpoint );
	right = negative_w(beg+midpoint, midpoint+(size%2));

	return (left)? left: right;
}

Now in this case there is no dependency between the function calls. You don't need to wait for the left function to end so you can start the right function.
That means that it could be easily parallelised. You will break that property if you need a global, static, or passed by reference variable.

How do you call your function twice, if you use an static variable?

Edit: the wrapper could be easily avoided, I just don't see it in time
return (right!=-1)? rigth+midpoint: left;

[dhv]

int firstNegative(const double a[], int n)
{
	if (n < 1) return -1;
	if (a[n-1] < 0 && firstNegative(a, n-2) == -1 ) return n-1;
	return firstNegative(a, n-1);
}

Returns -1 if no negative value found.

[crosby0371]

Thank you simeonz! Im also working on this problem rite now and your solution is so smart!