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

Question

I created a recursive algorithm to count the number of times a certain number n appears in a list ls. It seemed to work if the list ls is quite small (between 10 and 100), but if it’s big, like 1000, it doesn’t 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...!")

Answer 1

In most programming languages, each function call needs a few bytes of the runstack and in general there is a maximum limit to the stack size. On a desktop computer today that limit is usually on the order of 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 ultimately the ideal is to use a loop algorithm, which consumes a constant amount of memory, rather than the recursive algorithm, which consumes a stack amount directly proportional to the size of the input. In languages like Python it is best to use recursive algorithms only when maximum stack consumption grows slower. For example, many in many recursive algorithms the maximum stack size is proportional to the logarithm of the input size.

---

That being said, there are some programming languages that ensure that recursive calls in tail position do not waste additional 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 its algorithm a bit because the recursive call on 1 + _count(...) is not in tail position. But the important thing that I wanted to show is that in some languages it is possible to write recursive algorithms that do not burst the stack.