Выбор четных чисел с помощью рекурсии

Question

Здесь я определил функцию, которая берет список и возвращает количество четных чисел в этом же списке. Когда я запускаю программу, я получаю None в ответ.

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]))

Где моя проблема?

Answer 1

Есть две основные проблемы с текущей реализацией:

1. c - это int, а int являются неизменяемыми. Если вы измените c, это значит, что не означает, что c в рекурсивных вызовах "обновляется", каждый рекурсивный вызов c будет иметь значение 0; и
2. вы не возвращаете значение в случае, если первый элемент четный, поэтому Python вернет None в этом случае.

def count_even(lst, c = 0):
    if lst == []:
        return c
    if lst[0] % 2 == 0:
        c += 1
    # no else
    return count_even(lst[1:]<b>, c+1</b>)  # pass a new value for c

Однако более компактное представление:

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

Обратите внимание, однако, что линейная рекурсия, как правило, не очень хорошая идея, поскольку стек вызовов будет увеличиваться с увеличением количества элементов и, таким образом, легко приведет к переполнению (тем более что Python не реализует Оптимизация оконечного вызова (TCO) ).

Answer 2

Ты почти сделал это. Просто простое исправление. Вы вызываете рекурсию в блоке else, что неправильно. Вы должны рассмотреть это за пределами блока. Проверьте код ниже:

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]))

Answer 3

В случае lst[0] % 2 == 0 вы ничего не возвращаете (таким образом, неявно возвращая None). Вы также никогда не включите обновленное значение c в рекурсию. Измените это на

if lst == []:
    return c

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

return count_even(lst[1:], c)

и ты в порядке. Поскольку другие ответы включают в себя несколько изящных альтернативных решений, я выберу

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

также.