Identifying first negative number in array of doubles

Question

I was asked to create a function that checks if an array of doubles has all negative numbers or none. If these 2 (all negative, all positive) are false, check the first negative number, using recursion and only using built-in C++ features.

int first_negative(const double val [] , unsigned array, unsigned short instance_ = 0) //Dont change instance!
{
    //None negative?
    bool none_negative;
    for(int i = 0; i < array; i++)
    {
        if(val[i] > 0) none_negative = true;
        else
        {
            none_negative = false;
            break;
        }
    }
    if(none_negative) return 0;

    //All negative?
    bool negative_instance;
    for(int i = 0; i < array; i++)
    {
        if(val[i] < 0) negative_instance = true;
        else
        {
            negative_instance = false;
            break;
        }
    }


    //Never change instance!
    static short instance = instance_;
    if(array < 1) return 0;
    if(val[instance] < 0) return instance;
    instance++;
    return first_negative(val, array, instance);
}

Can I make it better? Can I remove the instance parameter?

Answer 1

• I believe the parameter names val and array are switched around. An array shouldn't be a single variable, and a value shouldn't be an array. Otherwise, the names themselves are okay.

• It's preferred to index through a C-style array with an std::size_t, especially if the array size is larger than an int. This could be helpful if you'll be working with very large numbers, although the recursion aspect here may render that unlikely. Even if you're not, it's best to develop that habit.

• This looks a bit misleading:

  if(val[instance] < 0) return instance;
  instance++;
  

  At first, I thought the instance++ was missing indentation and belonged to the if statement. To make this clearer, you could separate the two lines or, even better, have curly braces for the if statement. The latter also helps with better maintainability.

  if (val[instance] < 0)
  {
      return instance;
  }
  
  instance++;
  

• Again, some of the naming is misleading:

  if(array < 1) return 0;
  

  From a glance, that just looks incorrect as you cannot check an array like that. Proper naming is very important, even for a small program like this.

Answer 2

I thought "negative" means "less than zero" and "positive" means "greater than zero", with zero being neither positive nor negative. So if all array elements are zero, they are not all positive, not all negative, and there is no first negative element. If the array has no elements at all, then they are all positive and at the same time all negative. So the specification for the function is a bit on the weak side.

Usually you use "non-negative" for "positive or zero". If you meant "Positive or zero" when writing "positive" that should be checked.

Answer 3

You might be missing the point of recursion. Basically recursion replaces a loop. So, in your case, it doesn't make much sense to have the loop(s) inside the function. See if something like this works:

int FirstNeg(const double dblearray[], size_t size, int firstnegindex = -1, unsigned int index = 0, bool allpos = true, bool allneg = true)
{
    if((int)size == index || (!allpos && !allneg))
    {
        if(allpos || allneg)
            firstnegindex = -1;
        return firstnegindex;
    }
    if(firstnegindex == -1 && dblearray[index] < 0)
        firstnegindex = index;
    if(allpos && dblearray[index] < 0)
        allpos = false;
    if(allneg && dblearray[index] >= 0)
        allneg = false;
    return FirstNeg(dblearray,size,firstnegindex,++index,allpos,allneg);
}

This will return a -1 if the array is all negative or all positive and will return as soon as both positive and negative are shown to be present. I used an array but this should work for any indexed container.

Your call to the function only needs to include the array and the size assuming you are starting at index 0.

Answer 4

This sounds artificial to me. Why the mundane/recursive requirements?

To check if all values are positive, or negative, you have to scan all of the doubles.

While you are doing that, you may as well identify which member is the first negative.

Doing it all in combination would result in an O(n) operation that is small, and as fast as it could possibly be (unless you have things like sorted data).

So, create a DoubleDetails class that takes an array of double as a parameter, scan the entire array, and save away the first negative, and two bools, whether it is all positive, or all negative.

Then have methods that you can call on the class that return:

• allpositive() - true if they are all positive
• allnegative() - true if all negative.
• firstnegative() - the first negative value (if !allpositive && !allnegative).

Answer 5

I started with tinstaafl's answer, but modified it a bit to short circuit as soon as we know the answer:

int FirstNeg(const double dblearray[], size_t size, int firstnegindex = -1, unsigned int index = 0, bool haspos = false, bool hasneg = false)
{
    if((int)size == index)
        return -1;
    if(!hasneg && dblearray[index] < 0) {
        firstnegindex = index;
        hasneg = true;
    }
    if(!haspos && dblearray[index] >= 0)
        haspos = true;
    if (haspos && hasneg)
        return firstnegindex;   
    return FirstNeg(dblearray,size,firstnegindex,++index,haspos,hasneg);
}

Answer 6

First, let's write a recursive function that returns the index of the first negative number.

int first_negative(const double numbers[], int size, int current) 
{
    if (current >= size)
    {
        return -1;
    }

    if (numbers[current] < 0.0)
    {
        return current;
    }

    return first_negative(numbers, size, ++current);
}

This is nice and simple. Easy to read and understand. It doesn't fit the criteria, so it may not be obvious how this helps. But using this, let's write the more complicated function.

int first_negative_if_has_positives(const double numbers[], int size) 
{
    if (size <= 0)
    {
        return -1;
    }

    if (numbers[0] < 0.0)
    {
        return (first_nonnegative(numbers, size, 1) >= 0) ? 0 : -1;
    }

    return first_negative(numbers, size, 1);
}

The basic logic here is simple. If the first number in the array is negative, check if there are any positive numbers in the array. If there are, return 0 (the index of the first element in the array, which we already know is negative). If not, return -1 because all the numbers are negative. Otherwise if the first number is not negative, we know that there are some positives, so we can just look for the first negative number.

Now we need first_nonnegative, which is essentially the same function as first_negative with a different test.

int first_nonnegative(const double numbers[], int size, int current) 
{
    if (current >= size)
    {
        return -1;
    }

    if (numbers[current] >= 0.0)
    {
        return current;
    }

    return first_nonnegative(numbers, size, ++current);
}

Now we have a complete solution. While this is more code than the other solutions, it will actually do fewer operations. The other solutions don't make full use of the elegance of recursion. They try to carry state from call to call that is unnecessary. They have to check that state in each call. Instead of carrying that state around, this solution uses the state of the first number to determine what it needs to learn. Then it uses one of two functions depending on that initial state.

Let's look back at the criteria:

• return -1 if the numbers are all negative or all positive. This does that.
• Find the index of the first negative number otherwise. This does that.
• Using recursion. While the initial function is not recursive itself, it does use two recursive functions to generate the answer. It uses no loops.
• Only built-in C++ features. I'm not entirely sure what this means, but this solution only uses function calls, if statements, and return. It seems to fit.

Complexity is the enemy of good software. It decreases performance and increases bugs. If you find yourself adding complexity, it is often helpful to step back and ask if you're going the wrong direction.