Recursion in Python? RuntimeError: maximum recursion depth exceeded while calling a Python object

Question

Possible Duplicate:
Maximum recursion depth?

I have another problem with my code. I'm wrtiting my first program in Vpython and I have to make a simulation of mixing two gases. First i had a problem with borders, but now when the balls(that represents the gas particles) stay within the borders there is sth different wrong. After a few seconds i get an error, which is shown below the source code of my function. Code:

def MovingTheBall(listOfBalls,position,numCell,flagOfExecution):
    flag = 0
    if flagOfExecution==0:
        positionTmp = position
    else:
        positionTmp = (position[0]+choice([-1,0,1]),position[1]+choice([-1,0,1]),0)
    for i in range( 0, len(listOfBalls) ):
        if positionTmp==listOfBalls[i].pos:
            flag=1


    if flag==1:
        return MovingTheBall(lista,(position[0]+choice([-1,0,1]),position[1]+choice([-1,0,1]),0),numCell,1)
    else:
        if positionTmp[0]==0 or positionTmp[0]>=numCell or positionTmp[0]<=-numCell or positionTmp[1]>=numCell or positionTmp[1]<=-numCell:
            return MovingTheBall(lista,(position[0]+choice([-1,0,1]),position[1]+choice([-1,0,1]),0),numCell,1)

        return positionTmp

the error is:

    return MovingTheBall(listOfBalls,(position[0]+choice([-1,0,1]),position[1]+choice([-1,0,1]),0),numCell,1)
  File "gaz.txt", line 138, in MovingTheBall
    return MovingTheBall(listOfBalls,(position[0]+choice([-1,0,1]),position[1]+choice([-1,0,1]),0),numCell,1)
  File "gaz.txt", line 138, in MovingTheBall
    return MovingTheBall(listOfBalls,(position[0]+choice([-1,0,1]),position[1]+choice([-1,0,1]),0),numCell,1)
  File "gaz.txt", line 138, in MovingTheBall
    return MovingTheBall(listOfBalls,(position[0]+choice([-1,0,1]),position[1]+choice([-1,0,1]),0),numCell,1)
  File "gaz.txt", line 138, in MovingTheBall
    return MovingTheBall(listOfBalls,(position[0]+choice([-1,0,1]),position[1]+choice([-1,0,1]),0),numCell,1)
  File "gaz.txt", line 138, in MovingTheBall
    return MovingTheBall(listOfBalls,(position[0]+choice([-1,0,1]),position[1]+choice([-1,0,1]),0),numCell,1)
  File "gaz.txt", line 130, in MovingTheBall
    if positionTmp==listOfBalls[i].pos:
RuntimeError: maximum recursion depth exceeded while calling a Python object

Can anybody think of a way to simplify my function?

I run the function it while loop:

while 1:
        rate(20)
        for i in range(0,len(self.listOfBalls)):
            self.listOfBalls[i].pos=poruszanie(self.listOfBalls,self.listOfBalls[i].pos,self.numCell,0)

Answer 1

Python lacks the tail recursion optimizations common in functional languages like lisp. In Python, recursion is limited to 999 calls (see sys.getrecursionlimit).

If 999 depth is more than you are expecting, check if the implementation lacks a condition that stops recursion, or if this test may be wrong for some cases.

I dare to say that in Python, pure recursive algorithm implementations are not correct/safe. A fib() implementation limited to 999 is not really correct. It is always possible to convert recursive into iterative, and doing so is trivial.

It is not reached often because in many recursive algorithms the depth tend to be logarithmic. If it is not the case with your algorithm and you expect recursion deeper than 999 calls you have two options:

1) You can change the recursion limit with sys.setrecursionlimit(n) until the maximum allowed for your platform:

sys.setrecursionlimit(limit):

Set the maximum depth of the Python interpreter stack to limit. This limit prevents infinite recursion from causing an overflow of the C stack and crashing Python.

The highest possible limit is platform-dependent. A user may need to set the limit higher when she has a program that requires deep recursion and a platform that supports a higher limit. This should be done with care, because a too-high limit can lead to a crash.

2) You can try to convert the algorithm from recursive to iterative. If recursion depth is bigger than allowed by your platform, it is the only way to fix the problem. There are step by step instructions on the Internet and it should be a straightforward operation for someone with some CS education. If you are having trouble with that, post a new question so we can help.