22

I have another problem with my code. I'm writing 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)
Henry Ecker
  • 34,399
  • 18
  • 41
  • 57
Emil Smęt
  • 819
  • 3
  • 13
  • 28
  • 1
    Besides the point maybe, but in general it's good practice to have English names for variables and functions. You never know who might read you code - like Stackoverflow users, for example :-) – Kim Hansson Jan 08 '13 at 19:21
  • It might help if you explain your thought process on what this code is intended to do. Perhaps English variable names will be sufficient, but perhaps not. – jgritty Jan 08 '13 at 19:27
  • I've edited the post, can you help me now? As you've probably noticed english is not my first language. – Emil Smęt Jan 08 '13 at 19:35
  • As a side note, your `for i in range(0,len(listOfBalls))` block could be re-written as: `flag = any(positionTmp==i.pos for i in listOfBalls)` – mgilson Jan 08 '13 at 19:55

4 Answers4

45

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.

Paulo Scardine
  • 73,447
  • 11
  • 124
  • 153
  • 1
    I've read about that, and i found on this website a few errors with the same name, but the question is not what is an error, but how to fix it, or to simplify the code. I've also tried to enlarge the stack import sys sys.setrecursionlimit(10000) – Emil Smęt Jan 08 '13 at 19:49
  • 2
    Sorry, I found your code hard to follow and can't point where it is wrong. Answer updated with advice on how to solve your problem, either check why you are not stopping the recursion or change for a non-recursive approach (there are general techniques to convert a recursive implementation into a non-recursive). – Paulo Scardine Jan 08 '13 at 19:59
  • Np. I've changed the recursion to iteration.I'll post the answer below. – Emil Smęt Jan 08 '13 at 20:09
  • 3
    I don't agree that changing recursive algorithms to iterative algorithms is trivial. – Ely Jan 09 '16 at 08:00
  • @Elyasin see http://blog.moertel.com/posts/2013-05-11-recursive-to-iterative.html – Paulo Scardine Jan 09 '16 at 22:47
  • Thank you Paulo. However, many examples are more academic. I've seen recursive functions that are not trivial to change to iterative functions. – Ely Jan 09 '16 at 22:59
  • I think every recursive algorithm that is tail-recursive is trivial to implement as iterative. If they are not tail-recursive they possibly are not optimal even in functional languages. Of course I may be wrong so I would appreciate to try a few recursive algorithms you think are challenging to translate. – Paulo Scardine Mar 13 '18 at 15:50
10

I've changed the recursion to iteration. 

def MovingTheBall(listOfBalls,position,numCell):
while 1:
    stop=1
    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:
            stop=0
    if stop==1:
        if (positionTmp[0]==0 or positionTmp[0]>=numCell or positionTmp[0]<=-numCell or positionTmp[1]>=numCell or positionTmp[1]<=-numCell):
            stop=0
        else:
            return positionTmp

Works good :D

Emil Smęt
  • 819
  • 3
  • 13
  • 28
  • Congratulations, this solution more pythonic. – Paulo Scardine Jan 08 '13 at 20:53
  • 1
    i got the same error. what do you mean by iteration vs recursion? can you explain to me how i could make [this script](https://codepen.io/tOkyO1/pen/rqmppz?editors=0010) iterative instead of recursive? – oldboy Oct 10 '18 at 22:24
7

The error is a stack overflow. That should ring a bell on this site, right? It occurs because a call to poruszanie results in another call to poruszanie, incrementing the recursion depth by 1. The second call results in another call to the same function. That happens over and over again, each time incrementing the recursion depth.

Now, the usable resources of a program are limited. Each function call takes a certain amount of space on top of what is called the stack. If the maximum stack height is reached, you get a stack overflow error.

pvoosten
  • 3,247
  • 27
  • 43
  • i got the same error but have no idea how i could make [this script](https://codepen.io/tOkyO1/pen/rqmppz?editors=0010) iterative instead of recursive... any ideas? – oldboy Oct 10 '18 at 22:26
  • i guess i could first retrieve all the diff page links and then iterate through those – oldboy Oct 10 '18 at 22:31
  • You could use tail recursion, as explained in [this answer](https://stackoverflow.com/a/37010/158702) – pvoosten Oct 11 '18 at 12:04
  • 1
    yeah apparently python doesnt support tail recursion according to that answer – oldboy Oct 12 '18 at 07:17
3

That's the error you get when a function makes too many recursive calls to itself. It might be doing this because the base case is never met (and therefore it gets stuck in an infinite loop) or just by making an large number of calls to itself. You could replace the recursive calls with while loops.

mojzu
  • 39
  • 1