How do you count the number of negative items in a list using a recursive function?-CodePudding

I have to make a recursive function that counts how many negative values there are in a given list, but I can't figure out what I am supposed to return for each conditional.

def countNegatives(list):
    """Takes in a list of numbers and
    returns the number of negative numbers
    that are inside the list."""
    count = 0
    if len(list) == 0:
        return 0
    else:
        if list[0] < 0:
            return count   1
        else:
            return countNegatives(list[1:])

print(countNegatives([0, 1, -1, 3, -5, 6])) # should output 2 but gives me 1
print(countNegatives([-1, -3, 50,-4, -5, 1])) #should output 4 but gives me 1

CodePudding user response：

The problem with your code is that you are not keeping track of the running count of negative numbers in the recursive calls. Specifically, you are returning count 1 when the first item of the list is negative, and discarding the rest of the list, instead of using a recursive call to count the number of negative items in the rest of the list.

To fix the problem, you can add the result of the recursive call to count in both cases, when the first item is negative and when it is not. This way, the running count of negative items will be accumulated through the recursive calls, and returned as the final result when the base case is reached.

Here's a corrected version of your code:

def countNegatives(lst):
    """Takes in a list of numbers and
    returns the number of negative numbers
    that are inside the list."""
    count = 0
    if len(lst) == 0:
        return 0
    else:
        if lst[0] < 0:
            count  = 1
        count  = countNegatives(lst[1:])
        return count

print(countNegatives([0, 1, -1, 3, -5, 6]))  # Output: 2
print(countNegatives([-1, -3, 50, -4, -5, 1]))  # Output: 4

Note that I renamed the parameter list to lst, because list is the name of a built-in Python data type, and it is a good practice to avoid using built-in names as variable names.

CodePudding user response：

When list[0] < 0 your code ignores the rest of the list, yet there could be more negative values there to count.

So in that case don't do:

        return count   1

but:

        return 1   countNegatives(list[1:])

CodePudding user response：

The step you were missing is to add the count to the returned value of the recursive call, so that the returned values of all recursive calls get summed up at the end. Here's one way you could do this:

def countNegatives(list):
    #if the list length is zero, we are done
    if len(list) == 0:
        return 0

    # Get the count of this iteration
    count = 1 if list[0] < 0 else 0
    # sum the count of this iteration with the count of all subsequent iterations
    return count   countNegatives(list[1:])

So, for your first example, the actual steps taken by your code would look like:

return 0   countNegatives([1, -1, 3, -5, 6])
return 0   countNegatives([-1, 3, -5, 6])
return 1   countNegatives([3, -5, 6])
return 0   countNegatives([-5, 6])
return 1   countNegatives([6])
return 0   countNegatives([])
return 0

Expanding all the values gives:

return 0   0   1   0   1   0   0

CodePudding user response：

You want to accumulate count, so pass it to the recursive function. The first caller starts at zero, so you have a good default.

def countNegatives(list, count=0):
    """Takes in a list of numbers and
    returns the number of negative numbers
    that are inside the list."""
    if len(list):
        count  = list[0] < 0
        return countNegatives(list[1:], count)
    else:
        return count

result = countNegatives([1,99, -3, 6, -66, -7, 12, -1, -1])
print(result)
assert result == 5