2

Preciso contar quantas vezes uma comparação é verdadeira dentro de uma função recursiva, porém, não sei como fazer, pois qualquer variável de contagem será zerada quando iniciar o código.

def funcao(lista,x):
    i = len(lista)-1
    if lista[i] > x:
        k = 1
    if len(lista) == 1:
        return qntd #qntd = quantidade de números na lista maiores que x
    return funcao(lista[:i],x)

Preciso contar quantas vezes lista[i] > x, sem utilizar uma variável que seja declarada fora da função. No return eu já tentei várias contas (somas e produtos entre as variáveis da função) que me retornassem o que preciso, mas sem sucesso.

7
  • 3
    @tvdias me parecem diferentes a respostas, em especial na explicação detalhada. Conseguiria descrever mais ou menos em que parte as duas tem similaridade? Não achei semelhanças nas duas respostas não (tirando o fato de serem pra mesma pergunta, claro - é normal que alguma coisa tenha em comum). De qq maneira, como foi o Feitosafelipe quem selecionou, só ele pode dizer de fato.
    – Largato
    Commented 21/06/2020 às 0:55
  • 1
    @tvdias A "parte do for" tem tudo a ver sim, pois fala sobre a ineficiência do algoritmo e o problema do estouro de pilha, que são 2 detalhes importantes que muitos "ignoram"/"esquecem" ao falar de recursão. Pra mim tem relação direta porque tão importante quanto aprender a fazer, é saber as consequências de fazê-lo e principalmente quando não usar (e tudo isso faz parte de "aprender sobre recursão") :-) De qualquer forma, editei a resposta para deixar mais claro esse ponto.
    – hkotsubo
    Commented 21/06/2020 às 12:02
  • 2
    @tvdias Vale lembrar que a ideia do Stack Overflow em Português é formar uma base de conhecimento sobre programação e as respostas devem ser úteis não apenas para quem pergunta, mas para qualquer pessoa que visite o site futuramente. Por isso é importante não ficar "só" no que foi perguntado e tentar agregar conhecimento indo um pouco além (só tomando cuidado pra não desviar muito do foco, claro, mas em linhas gerais é isso) :-)
    – hkotsubo
    Commented 21/06/2020 às 12:03
  • 1
    Sobretudo é um aprendizado também para quem responde. :) @hkotsubo obrigado pela atenção.
    – tvdias
    Commented 21/06/2020 às 13:05
  • 1
    @tvdias Considerei a resposta do hkotsubo como correta pois além de responder à pergunta feita, ele explicou um pouco melhor sobre o que é recursão e qual a desvantagem de utilizar este método. A sua resposta também foi muito boa, dado o fato de que considerou como algo importante o aprendizado do assunto e não apenas a solução. Mas como a outra resposta ficou mais didática, acredito que seria melhor para outras pessoas que tiverem problemas semelhantes, pois tem a solução da pergunta e uma abordagem ampla do assunto. Commented 21/06/2020 às 16:46

2 Respostas 2

4

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.

0

Sempre fico na dúvida se devo responder este tipo de questão. Porque se dou a resposta vc dificilmente aprenderá a fazer recursividade; e, se respondo de forma "genérica", a resposta simplesmente não deverá ser aceita e ainda posso ser negativado por não dar a resposta ao problema.

Resolvi responder com algumas dicas e, de bônus, dou a solução. Se quiser mesmo aprender, diria para não olhar diretamente a solução e tentar fazer sozinho com base nas dias.

Tenho alguns "truques" para resolver esse tipo de problema. O 1o é pensar no "caso base" ou "resposta trivial". Neste caso podemos assumir que seria quando a lista é vazia, devendo retornar 0. A seguir deve-se "resolver" o problema e chamar o passo seguinte. Para esse caso, seria retornar 0 ou 1 (conforme a comparação) e somar ao próximo caso e ao próximo e ao outro, ... Entretanto, para fazer essa soma "que nunca acaba" é que usamos a recursividade e devemos garantir que o nosso caso base vai parar a recursão.


Dessa forma, tenho a solução abaixo. Note que, no lugar de remover o último elemento da lista, fiz a recursividade pelo 1o elemento. Sendo assim, posso ler sempre o elemento de índice 0, evitando algumas linhas desnecessárias.

def funcao(lista, x):
  if len(lista) == 0:
    return 0

  if lista[0] > x:
    return 1 + funcao(lista[1:], x)

  return funcao(lista[1:], x)

O código acima pode ser melhorado de muitas formas, mas acredito que perderia um pouco da sua didática. Penso que essa seja a forma que facilita o raciocínio e leitura, face ao problema apresentado.

https://repl.it/repls/ScientificModestRoutine

1
  • O voto negativo poderia ser justificado?
    – tvdias
    Commented 22/06/2020 às 18:05

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .