counting odd numbers in a list python

Question

This is a part of my homework assignment and im close to the final answer but not quite yet. I need to write a function that counts odd numbers in a list.

Create a recursive function count_odd(l) which takes as its only argument a list of integers. The function will return a count of the number of list elements that are odd, i.e., not evenly divisible by 2.\

>>> print count_odd([])  
0  
>>> print count_odd([1, 3, 5])  
3  
>>> print count_odd([2, 4, 6])  
0  
>>> print count_odd([0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144])  
8  

Here is what i have so far: #- recursive function count_odd -#

def count_odd(l):
    """returns a count of the odd integers in l.
    PRE: l is a list of integers.
    POST: l is unchanged."""
    count_odd=0

    while count_odd<len(l):
        if l[count_odd]%2==0:
            count_odd=count_odd
        else:
            l[count_odd]%2!=0
            count_odd=count_odd+1
    return count_odd

#- test harness  
print count_odd([])  
print count_odd([1, 3, 5])  
print count_odd([2, 4, 6])  
print count_odd([0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144])  

Can u help explain what im missing. The first two test harness works fine but i cant get the final two. Thanks!

Answer 1

Since this is homework, consider this pseudo-code that just counts a list:

function count (LIST)
    if LIST has more items
        // recursive case.
        // Add one for the current item we are counting,
        // and call count() again to process the *remaining* items.
        remaining = everything in LIST except the first item
        return 1 + count(remaining)
    else
        // base case -- what "ends" the recursion
        // If an item is removed each time, the list will eventually be empty.
        return 0

This is very similar to what the homework is asking for, but it needs to be translate to Python and you must work out the correct recursive case logic.

Happy coding.

Answer 2

def count_odd(L):
    return (L[0]%2) + count_odd(L[1:]) if L else 0

Answer 3

All of the prior answers are subdividing the problem into subproblems of size 1 and size n-1. Several people noted that the recursive stack might easily blow out. This solution should keep the recursive stack size at O(log n):

def count_odd(series):
    l = len(series) >> 1
    if l < 1:
        return series[0] & 1 if series else 0
    else:
        return count_odd(series[:l]) + count_odd(series[l:])

Answer 4

Are slices ok? Doesn't feel recursive to me, but I guess the whole thing is kind of against usual idioms (i.e. - recursion of this sort in Python):

def countOdd(l):
    if l == list(): return 0           # base case, empty list means we're done
    return l[0] % 2 + countOdd(l[1:])  # add 1 (or don't) depending on odd/even of element 0.  recurse on the rest

x%2 is 1 for odds, 0 for evens. If you are uncomfortable with it or just don't understand it, use the following in place of the last line above:

   thisElement = l[0]
   restOfList = l[1:]
   if thisElement % 2 == 0: currentElementOdd = 0
   else: currentElementOdd = 1
   return currentElementOdd + countOdd(restOfList)

PS - this is pretty recursive, see what your teacher says if you turn this in =P

>>> def countOdd(l):
...     return fold(lambda x,y: x+(y&1),l,0)
... 
>>> def fold(f,l,a):
...     if l == list(): return a
...     return fold(f,l[1:],f(a,l[0]))

Answer 5

I would write it like this:

def countOddNumbers(numbers): 
    sum = 0
    for num in numbers:
        if num%2!=0:
            sum += numbers.count(num)
    return sum 

Answer 6

not sure if i got your question , but as above something similar:

def countOddNumbers(numbers): 
    count=0
    for i in numbers:
        if i%2!=0:
            count+=1
    return count

Answer 7

The goal of recursion is to divide the problem into smaller pieces, and apply the solution to the smaller pieces. In this case, we can check if the first number of the list (l[0]) is odd, then call the function again (this is the "recursion") with the rest of the list (l[1:]), adding our current result to the result of the recursion.

Answer 8

def count_odd(series):
    if not series:
        return 0
    else:
        left, right = series[0], series[1:]
        return count_odd(right) + (1 if (left & 1) else 0)

Answer 9

Tail recursion

def count_odd(integers):
    def iter_(lst, count):
        return iter_(rest(lst), count + is_odd(first(lst))) if lst else count
    return iter_(integers, 0)

def is_odd(integer):
    """Whether the `integer` is odd."""
    return integer % 2 != 0 # or `return integer & 1`

def first(lst):
    """Get the first element from the `lst` list.

    Return `None` if there are no elements.
    """
    return lst[0] if lst else None

def rest(lst):
    """Return `lst` list without the first element."""
    return lst[1:]

There is no tail-call optimization in Python, so the above version is purely educational.

The call could be visualize as:

count_odd([1,2,3])    # returns
iter_([1,2,3], 0)      # could be replaced by; depth=1
iter_([2,3], 0 + is_odd(1)) if [1,2,3] else 0 # `bool([1,2,3])` is True in Python
iter_([2,3], 0 + True) # `True == 1` in Python
iter_([2,3], 1)        # depth=2
iter_([3], 1 + is_odd(2)) if [2,3] else 1
iter_([3], 1 + False)  # `False == 0` in Python
iter_([3], 1)          # depth=3
iter_([], 1 + is_odd(3)) if [3] else 1
iter_([], 2)           # depth=4
iter_(rest([]), 2 + is_odd(first([])) if [] else 2 # bool([]) is False in Python
2 # the answer

Simple trampolining

To avoid 'max recursion depth exceeded' errors for large arrays all tail calls in recursive functions can be wrapped in lambda: expressions; and special trampoline() function can be used to unwrap such expressions. It effectively converts recursion into iterating over a simple loop:

import functools

def trampoline(function):
    """Resolve delayed calls."""
    @functools.wraps(function)
    def wrapper(*args):
        f = function(*args)
        while callable(f):
            f = f()
        return f
    return wrapper

def iter_(lst, count):
    #NOTE: added `lambda:` before the tail call
    return (lambda:iter_(rest(lst), count+is_odd(first(lst)))) if lst else count

@trampoline
def count_odd(integers):
    return iter_(integers, 0)

Example:

count_odd([1,2,3])
iter_([1,2,3], 0)         # returns callable
lambda:iter_(rest(lst), count+is_odd(first(lst))) # f = f()
iter_([2,3], 0+is_odd(1)) # returns callable
lambda:iter_(rest(lst), count+is_odd(first(lst))) # f = f()
iter_([3], 1+is_odd(2))   # returns callable
lambda:iter_(rest(lst), count+is_odd(first(lst))) # f = f()
iter_([], 1+is_odd(3))
2                         # callable(2) is False

Answer 10

Generator can give quick result in one line code:

sum((x%2 for x in nums))