Count in recursive function

Asked

Viewed 505 times

2

I need to count how many times a comparison is true within a recursive function, but I don’t know how to do it, because any counting variable will be reset when starting the code.

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)

I need to count how many times lista[i] > x, without using a variable that is declared outside the function. No return i have tried several accounts (sums and products between function variables) that return me what I need, but without success.

python list recursion

  • 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.

  • 3

    @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.

  • 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.

  • 1

    @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.

  • 2

    @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) :-)

  • 1

    Above all, it is also a learning experience for those who answer. : ) @hkotsubo thanks for your attention.

  • 1

    @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.

Show 2 more comments

2 answers

4


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.

0

I always wonder if I should answer this kind of question. Because if I give the answer you will hardly learn to make recursion; and if I answer in a "generic" way, the answer simply should not be accepted and I can still be denied by not giving the answer to the problem.

I decided to answer with some tips and, bonus, I give the solution. If you really want to learn, I would say don’t look directly at the solution and try to do it yourself based on the days.

I have some "tricks" to solve this type of problem. The first is to think of the "base case" or "trivial answer". In this case we can assume that it would be when the list is empty, and should return 0. Next we must "solve" the problem and call the next step. For this case, would return 0 or 1 (as compared) and add to the next case and the next and the other, ... However, to make this "never-ending" sum is that we use recursion and we must ensure that our base case will stop recursion.

So, I have the solution below. Note that instead of removing the last element from the list, I recurred for the first element. Therefore, I can always read the index element 0, avoiding some unnecessary lines.

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)

The above code can be improved in many ways, but I believe I would miss some of your teaching. I believe that this is the way that facilitates reasoning and reading, facing the problem presented.

https://repl.it/repls/ScientificModestRoutine

  • The negative vote could be justified?

Browser other questions tagged python list recursion

You are not signed in. Login or sign up in order to post.