To understand recursion, you have to understand recursion :-)
In the case of processing a list recursively, the general idea is usually:
- if the list is empty, there is nothing to do
- if not empty, I check the first element and compute the result
- check the rest of the list and match with the result of the first element
In your specific case, the idea then is:
- if the list is empty, returns zero (as there is nothing to compare, then there are zero elements that are greater than x)
- if it is not empty, I check if the first element is greater than x (if it is, I compute the result as
1
, else is zero)
- we count the rest of the list
Translating to Python would look like this:
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:]
returns a sub-list containing the second element on (or an empty list if there are no more elements). Therefore, in the next recursive call the "first" element of this sub-list will actually be the second element of the original list. Then another sub-list will be generated (whose first element will be the third of the original list and so on, until the sub-list is empty, which is when the recursion ends and the results are combined).
Note that the problem with your code is that you were only returning the result of the rest of the list, and failed to add with the element that is being checked in each call.
Remember that the recursive solution is not ideal for this case. Not only for the inefficiency of generating multiple sub-lists, but also because many recursive calls can cause a pile burst if the list is large enough, see here an example (and notice that the list doesn’t even have to be that big).
In your case, the simplest is to use the good old loop:
def funcao(lista,x):
qtd = 0
for i in lista:
if i > x:
qtd += 1
return qtd
Or else:
def funcao(lista,x):
return sum(1 for i in lista if i > x)
The loops above are better because, in addition to not creating multiple sub-lists, they don’t have the stack crash problem, see here the difference.
I know this may not seem relevant at first glance, because "only" was asked how to do it, but as important as learning the recursive algorithm, it is understanding the consequences of using it, and especially knowing when it is best not to use it (which is the case here). Learn more about the subject by reading here, here, here and here.
I wanted to understand what was the differential for the accepted answer, since it has basically the same content as the other that was answered earlier.
– tvdias
@tvdias seem different to me to answers, especially in the detailed explanation. Could you describe more or less where the two have similarities? I did not find similarities in the two answers no (apart from the fact that they are for the same question, of course - it is normal that something has in common). However, as it was Feitosafelipe who selected, only he can say in fact.
– Bacco
They seem to me the same answer, with the same content, with practically the same words, but organized in Bullets. With the addition of the comment on the for, it has no relation to the asked, since the goal seemed to be "to learn" about recursiveness. But I’m glad they’re seen differently by so many people, so I can see it was just a misguided perception of me.
– tvdias
@tvdias The "part of the for" has everything to do yes, because it talks about the inefficiency of the algorithm and the stack overflow problem, which are 2 important details that many "ignore"/"forget" when talking about recursion. For me it has a direct relationship because as important as learning to do, it is to know the consequences of doing it and especially when not using (and all this is part of "learning about recursion") Anyway, I edited the answer to make this point clearer.
– hkotsubo
@tvdias It is worth remembering that the idea of [pt.so] is to form a knowledge base on programming and the answers should be useful not only for those who ask, but for anyone who visits the site in the future. That is why it is important not to be "alone" in what was asked and try to aggregate knowledge going a little further (just taking care not to deviate too much from the focus, of course, but in general lines is this) :-)
– hkotsubo
Above all, it is also a learning experience for those who answer. : ) @hkotsubo thanks for your attention.
– tvdias
@tvdias I considered hkotsubo’s answer as correct because in addition to answering the question asked, he explained a little better about what recursion is and the disadvantage of using this method. His reply was also very good, given the fact that he considered as something important the learning of the subject and not only the solution. But as the other answer became more didactic, I believe it would be better for other people who have similar problems, because it has the solution of the question and a broad approach to the subject.
– Feitosafelipe