Using recursion to count the number of times a number appears in a list

Question

Using recursion to count the number of times a number appears in a list

Navigation

#1 by (2 votes)

3

I have created a recursive algorithm to count the number of times a certain n appears in a ls list. It seems to work if the ls list is quite small (between 10 and 100), but if it is large, type 1000, it does not seem to work anymore: it enters an infinite recursion ...

Can anyone understand why?

def _count(n, ls, index):
    if index < len(ls):
        if ls[index] == n:
            return 1 + _count(n, ls, index + 1)
        else:
            return _count(n, ls, index + 1)
    return 0


def count(n, ls):
    """Counts how many times n appears in the list or tuple ls."""
    return _count(n, ls, 0)


if __name__ == "__main__":
    from random import randint

    for i in range(10):
        ls = [randint(0, 10) for _ in range(1000)]  # modifica 1000 para 100 para funcionar
        print("List:", ls)

        r = randint(0, 10)
        print("Counting number:", r)

        c = count(r, ls)
        print("Counted:", c)

        if c != ls.count(r):
            raise Exception("Something is wrong with the implementation of count...!")

python python-3.x count contador

asked by anonymous 01.01.2016 / 01:27

1 answer

Is there any difference between codes A and B below? How to create fields dynamically when selecting a value in the checkbox?

score 2 · Accepted Answer

In most programming languages, each function call needs a few bytes of the execution stack and there is usually a maximum limit for the stack size. On a Desktop computer these days this limit is usually in the hundreds of thousands of calls but in Python the limit is quite low on purpose:

> import sys
> sys.getrecursionlimit()
1000

You can slightly increase the limit with sys.setrecursionlimit but in the end it is ideal to use a looping algorithm that consumes a constant amount of memory, rather than the recursive algorithm, which consumes a directly proportional stack amount to the size of the entrance. In languages like Python it is better to use recursive algorithms only when the maximum stack consumption grows slower. For example, many in many recursive algorithms the maximum stack size is proportional to the log size of the input.

That said, there are some programming languages that ensure that recursive calls in tail position do not waste space on the stack.

A language that ensures optimization of tail recursion is Moon . In Lua we can write a count algorithm that never bursts the stack.

function _count(x, xs, i, nfound)
    if i <= #xs then
        if xs[i] == x then
            return _count(x, xs, i+1, nfound+1)
        else
            return _count(x, xs, i+1, nfound)
        end
    else
        return nfound
    end
end

function count(x, xs)
    return _count(x, xs, 1, 0) -- Em Lua os índices começam em 1
end

I had to change your algorithm a bit because the recursive call in 1 + _count(...) is not in the tail position. But the important thing I wanted to show is that in some languages it is possible to write recursive algorithms that do not pop the stack.