Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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?

share|improve this question
    
Can you please rephrase on what this is supposed to do? –  Bobby Feb 10 at 15:56
    
@Bobby Sure. I'll edit. –  Lucas Henrique Feb 10 at 15:58
    
You probably have a bug since you use none_negative == true as assignment, when it is not... –  Uri Agassi Feb 10 at 16:34
    
@UriAgassi Wow! I didn't saw that! Thank you! –  Lucas Henrique Feb 10 at 16:36
    
Is the recursion imposed somehow? Because for such a task, a simple loop is going to be a lot faster. –  Alexis Wilke Feb 14 at 5:54
show 1 more comment

5 Answers 5

up vote 11 down vote accepted
  • 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.

share|improve this answer
    
Yep, I already use containers. This challenge was creating algorithm only built-in C++ features. –  Lucas Henrique Feb 10 at 16:12
    
Array is from 0 to "array", scan from the first value, with the "array" delimiter. –  Lucas Henrique Feb 10 at 16:19
    
@LucasHenrique: That's fine. I can remove the second bulletpoint. –  Jamal Feb 10 at 16:28
    
So, my code, can be better? (With the requirements) –  Lucas Henrique Feb 10 at 16:31
    
@LucasHenrique: I hope this was helpful enough for you. :-) I understand that I didn't address the recursion nor the instance variable, but I also didn't run this code myself. The main thing here, in terms of performance, is that you should avoid looping when you already have recursion. That was addressed very well in another answer. –  Jamal Feb 10 at 17:45
show 1 more comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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).
share|improve this answer
add comment

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);
}
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.