Primeiramente, recursão não é a melhor forma de resolver esse problema (veremos opções não-recursivas no final). E busca binária só faz sentido em listas ordenadas (mesmo assim, a busca binária serve para encontrar um único elemento, não para contar quantas vezes um elemento ocorre).
Enfim, uma forma de resolver é:
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
Ou seja, se a lista for vazia, retorna zero. Senão, verifica se o primeiro elemento é igual ao valor (e aí eu decido se contabilizo 1 ou 0).
Depois eu somo isso (o 1 ou 0) com a contagem do restante da lista: lista[1:]
cria uma sub-lista contendo do segundo elemento em diante.
Não é lá muito eficiente porque cria várias sub-listas, além de poder estourar a pilha se a lista for muito grande, veja.
Outra alternativa é passar o índice a ser verificado:
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
Essa é menos pior que a anterior porque não cria sub-listas, mas também tem o problema do estouro de pilha, veja.
Até dá para usar busca binária
Você pode usar busca binária para encontrar a posição do elemento. Mas como já dito, busca binária só funciona se a lista estiver ordenada, então primeiro você deve ordená-la.
Em seguida, como a lista está ordenada, basta verificar os elementos da direita e da esquerda do elemento encontrado e obter a contagem total:
# 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
Não use recursão para este caso
Como já dito, as melhores soluções são as não-recursivas. A mais simples é usar o que já tem pronto na linguagem:
print(itens.count(30))
Mas se quiser fazer manualmente:
cont = 0
for valor in itens:
if valor == 30:
cont += 1
print(cont)
Ou ainda:
print(len(list(filter(lambda x: x == 30, itens))))
# ou
print(sum(1 for _ in filter(lambda x: x == 30, itens)))