CODEWITHSUNDEEP
pythonlistrecursion
user10158754
user10158754

Reputation:

Picking even numbers using recursion

Here I have defined a function that takes in a list and returns the count of the even numbers in that same list.When I run the program I get None in return.

def count_even(lst, c = 0):
    """
    parameters : a lst of type list
    returns : the even elements from that list
    """
    if lst == []:
        return c
    if lst[0] % 2 == 0:
        c += 1
    else:
        return count_even(lst[1:])


print(count_even([1,2,3,4,5,6,7,8,9]))

Where is my problem?

Upvotes: 1

Views: 1404

Answers (3)

fuglede
fuglede

Reputation: 18201

In case lst[0] % 2 == 0, you are not returning anything (thus implicitly returning None). You also never include the updated value of c in the recursion. Change that to

if lst == []:
    return c

if lst[0] % 2 == 0:
    c += 1

return count_even(lst[1:], c)

and you're good. Since the other answers include some nifty alternative solutions, I'll go ahead and nominate

def count_even(lst):
    return 1 - lst[0]%2 + count_even(lst[1:]) if lst else 0

as well.

Upvotes: 7

Sanchit Kumar
Sanchit Kumar

Reputation: 1695

You almost did it. Just a simple correction. You are calling the recursion in else block which is not right. You should consider it outside the block. Check the below code : 

def count_even(lst, c = 0):
    """
    parameters : a lst of type list
    returns : the even elements from that list
    """
    if lst == []:
        return c
    if lst[0] % 2 == 0:
        c = c + 1
    return c + count_even(lst[1:])


print(count_even([1,2,3,4,5,6,7,8,9]))

Upvotes: 1

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476554

There are two basic problems with the current implementation:

  1. c is an int, and ints are immutable. If you change c, this thus does not mean the c in recursive calls is "updated", each recursive call c will have as value 0; and
  2. you do not return a value in case the first item is even, so Python will return None in that case.
def count_even(lst, c = 0):
    if lst == []:
        return c
    if lst[0] % 2 == 0:
        c += 1
    # no else
    return count_even(lst[1:], c+1)  # pass a new value for c

A more compact representation is however:

def count_even(lst, c = 0):
    if not lst:
        return c
    return count_even(lst[1:], c + 1 - lst[0] % 2)

Note however that linear recursion is typically not a good idea, since the call stack will grow with the number of elements, and thus easily result in an overflow (especially since Python does not implement tail call optimization (TCO)).

Upvotes: 1

Related Questions