Para entender recursão, você tem que entender recursão :-)
No caso de processar uma lista recursivamente, a ideia geral costuma ser:
- se a lista é vazia, não há o que fazer
- se não for vazia, verifico o primeiro elemento e computo o resultado
- verifico o restante da lista e combino com o resultado do primeiro elemento
No seu caso específico, a ideia então é:
- se a lista é vazia, retorna zero (pois não há o que comparar, então há zero elementos que são maiores que x)
- se não for vazia, verifico se o primeiro elemento é maior que x (se for, computo o resultado como
1
, senão é zero)
- somo esse resultado com a contagem do restante da lista
Traduzindo para Python, ficaria assim:
def funcao(lista, x):
if len(lista) == 0: # lista vazia, não há o que comparar
return 0
# verifica o primeiro elemento
qtd = 1 if lista[0] > x else 0
# soma com a contagem do restante da lista
return qtd + funcao(lista[1:], x)
print(funcao([1,2,3,4,5], 3)) # 2
lista[1:]
retorna uma sub-lista contendo do segundo elemento em diante (ou uma lista vazia se não tiver mais elementos). Sendo assim, na próxima chamada recursiva o "primeiro" elemento dessa sub-lista será na verdade o segundo elemento da lista original. Depois, será gerada outra sub-lista (cujo primeiro elemento será o terceiro da lista original e assim por diante, até que a sub-lista seja vazia, que é quando a recursão se encerra e os resultados são combinados).
Repare que o problema do seu código é que você só estava retornando o resultado do restante da lista, e faltou somar com o elemento que está sendo verificado em cada chamada.
Lembrando que a solução recursiva não é a ideal para este caso. Não só pela ineficiência de ficar gerando várias sub-listas, mas também porque muitas chamadas recursivas podem causar um estouro de pilha se a lista for suficientemente grande, veja aqui um exemplo (e repare que a lista nem precisa ser tão grande assim).
No seu caso, o mais simples é usar o bom e velho loop:
def funcao(lista,x):
qtd = 0
for i in lista:
if i > x:
qtd += 1
return qtd
Ou ainda:
def funcao(lista,x):
return sum(1 for i in lista if i > x)
Os loops acima são melhores porque, além de não criar várias sub-listas, não têm o problema do estouro de pilha, veja aqui a diferença.
Sei que isso pode não parecer relevante à primeira vista, pois "só" foi perguntado como fazer, porém tão importante quanto aprender o algoritmo recursivo, é entender as consequências de usá-lo, e principalmente, saber quando é melhor não usar (o que é o caso aqui). Saiba mais sobre o assunto lendo aqui, aqui, aqui e aqui.