Question:
I created a recursive algorithm to count the number of times a certain number n appears in an ls list. It seemed to work if the ls list is quite small (between 10 and 100), but if it's big, like 1000, it doesn't seem to work anymore: it goes into 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:
In most programming languages, each function call needs a few bytes of the execution stack, and there is usually a maximum limit on the size of the stack. On a desktop computer these days this limit is usually in 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 increase the limit a little with sys.setrecursionlimit but in the end it's ideal to use a looping algorithm, which consumes a constant amount of memory, instead of the recursive algorithm, which consumes a stack amount directly proportional to the size of the input. In languages like Python it is better to use recursive algorithms only when the maximum stack consumption grows slower. For example, in many recursive algorithms the maximum stack size is proportional to the logarithm of the input size.
That said, there are some programming languages that ensure that recursive tail-position calls don't waste additional stack space.
A language that guarantees the optimization of tail recursion is Lua . In Lua we can write a count algorithm that never overflows 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 little bit because the recursive call on 1 + _count(...) is not in 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 crash the stack.