Python recursive method that returns how many times a given element appears in a vector

Question

I want to make a recursive method in Python that returns how many times an element appears in an array. Below follows my code using binary search:

    def binaryrec(valor, itens, menor, maior):
    vezes = 0
    maior = len(itens) if maior is None else maior
    pos = menor + (maior - menor) // (len(itens) // 2)

    if pos == len(itens):
        return False
    for i in range(len(itens)):
        if itens[pos] == valor:
            vezes = vezes + 1
            return vezes
    if maior == menor:
        return -1
    elif itens[pos] < valor:
        return binaryrec(valor, itens, pos + 1, maior)
    else:
        assert itens[pos] > valor
        return binaryrec(valor, itens, menor, pos)

itens = [0, 10, 20, 30, 40, 30, 30, 70, 80]
valor = 30
maior = 80
menor = 0
r = binaryrec(valor, itens, menor, maior)
print(r)

Answer 1

First of all, recursion nay is the best way to solve this problem (we’ll see non-recursive options at the end). And binary search only makes sense in ordered lists (even so, binary search serves to find a single element, not to count how many times an element occurs).

Anyway, one way to solve it is:

def count(lista, valor):
    if not lista: # lista vazia
        return 0
    c = 1 if lista[0] == valor else 0
    return c + count(lista[1:], valor)

itens = [0, 10, 20, 30, 40, 30, 30, 70, 80]
print(count(itens, 30)) # 3

That is, if the list is empty, it returns zero. Otherwise, it checks if the first element is equal to the value (and then I decide if I count 1 or 0).

Then I add that (the 1 or 0) with the count of the rest of the list: lista[1:] creates a sub-list containing the second element on.

It’s not very efficient because it creates several sub-lists, as well as power blow up the pile if the list is too long, see.

---

Another alternative is to pass the index to be checked:

def count(lista, valor, i=0):
    if i >= len(lista):
        return 0
    c = 1 if lista[i] == valor else 0
    return c + count(lista, valor, i + 1)

itens = [0, 10, 20, 30, 40, 30, 30, 70, 80]
print(count(itens, 30)) # 3

This is less worse than the previous one because it does not create sub-lists, but also has the problem of stack overflow, see.

---

You can even use binary search

You can use binary search to find the position of the element. But as already said, binary search only works if the list is sorted, so first you should order it.

Then, as the list is sorted, just check the right and left elements of the found element and get the total count:

# retorna a posição do valor na lista (ou -1 se não for encontrado)
def busca_binaria(lista, inicio, fim, valor):
    if (fim < inicio):
        return -1

    meio = inicio + (fim - inicio) // 2
    if lista[meio] == valor:
        return meio

    if lista[meio] > valor:
        return busca_binaria(lista, inicio, meio - 1, valor)

    return busca_binaria(lista, meio + 1, fim, valor)

def count(lista, valor):
    # busca o índice do elemento
    ind = busca_binaria(lista, 0, len(lista) - 1, valor)
    # elemento não existe na lista
    if ind == -1:
        return 0

    count = 1
    # verifica os elementos à esquerda
    left = ind - 1
    while left >= 0 and lista[left] == valor:
        count += 1
        left -= 1

    # verifica os elementos à direita
    right = ind + 1
    while right < len(lista) and lista[right] == valor:
        count += 1
        right += 1

    return count 

itens = [0, 10, 20, 30, 40, 30, 30, 70, 80]
itens.sort()
print(count(itens, 30)) # 3

---

Do not use recursion for this case

As already said, the best solutions are non-recursive ones. The simplest is to use what is already ready in the language:

print(itens.count(30))

But if you want to do it manually:

cont = 0
for valor in itens:
    if valor == 30:
        cont += 1
print(cont)

Or else:

print(len(list(filter(lambda x: x == 30, itens))))

# ou
print(sum(1 for _ in filter(lambda x: x == 30, itens)))