How to implement a method recursively in Python

Question

I am trying to implement this method recursively. However, after a few seconds I get an Index Error sayings "Can't pop from empty stack." How can I correct this? Essentially, the point of the entire code (which I have not included) is to create a maze and guide a robot through it.

empty (unexplored) cell
EMPTY = 0

cell with an obstacle
OBSTACLE = 1

cell that is on the path
ON_PATH = 2

cell that has been explored, but is not on the path
EXPLORED = 3

cell the robot is in
ROBOT = 4

def solve(self, location):  

    eventType, done = None, False
    self.maze[location[0]][location[1]] = ROBOT  
    if self.mode == GRAPHICAL_FULL:  
        self.display_init()  
        self.draw_maze()  
    elif self.mode == GRAPHICAL_LIMITED:  
        self.display_init()  
        self.update_maze()  
    while eventType != QUIT and not done:  
        if self.mode == GRAPHICAL_FULL or self.mode == GRAPHICAL_LIMITED:  
            for event in pygame.event.get():  
                eventType = event.type
        new_location = self.find_next_step() 
        if new_location is None:  
            # Mark the current location as a dead end  
            self.maze[location[0]][location[1]] = EXPLORED  
            # pop the next cell off the path stack (go back one space)  
            location = self.path.pop()
            self.maze[location[0]][location[1]] = ROBOT
            self.solve(location)   
        else:  
            self.maze[location[0]][location[1]] = ON_PATH  
            self.path.push(location)  
            location = new_location
            self.solve(location)
        if self.mode == GRAPHICAL_FULL or self.mode == GRAPHICAL_LIMITED:  
            self.clock.tick(self.framerate)  
            self.update_maze()  
            self.screen.blit(self.background, (0,0))  
            pygame.display.flip()  
        if (self.maze[0][0] == EXPLORED or
            location == (self.dimension['x']-1, self.dimension['y']-1)):  
            self.path.push(location)  
            done = True
    return self.path


def find_next_step(self):  
    # Search for a place to go  
    for direction in SEARCH_ORDER:  
        new_location = (self.location[0] + direction['x'],  
                        self.location[1] + direction['y'])  
        if (0 <= new_location[0] < self.dimension['x'] and
            0 <= new_location[1] < self.dimension['y'] and
            self.maze[new_location[0]][new_location[1]] == EMPTY):  
            self.maze[new_location[0]][new_location[1]] = ROBOT  
            return new_location  
    return None

When the method is written without recursion, the robot completes the maze — user3277598
– user3277598, Commented Feb 11, 2014 at 20:02
Recursive calls from within an event loop? Are you sure this is what you want to do? — Hyperboreus
– Hyperboreus, Commented Feb 11, 2014 at 20:04
The way I'm reading this, you'll set eventType to QUIT inside the for loop and then proceed with the recursive call anyway. Is this what you really want? — chrisaycock
– chrisaycock, Commented Feb 11, 2014 at 20:06

clov3rly · Accepted Answer · 2014-02-11 22:34:46Z

As pop is only called if new_location is None, self.find_next_step() has returned none. Without the code for find_next_step(), its hard to be certain, but my guess is that the robot has traversed all paths, is back at the start (with an empty path), and thus .pop() fails.

Anyway, I'd suggest the error really occurs in the return value from find_next_step().

This isn't really an answer, but I don't have the rep to comment yet, hope this helps ;)

Update:

Well, I now have more information, but I still feel a long way from grasping your whole picture.

However, it appears that find_next_step will return None if there are no empty values of direction in SEARCH_ORDER. (although I don't know what direction looks like. SEARCH_ORDER is presumably a constant? (Not a big python user)).

Anyway, that will presumably be the case when the robot has explored or otherwise identified all the cells that find_next_step looks at.

Paul Becotte · Accepted Answer · 2014-02-12 01:38:53Z

0

There isn't enough of the application for this to be definitive, but I think your problem is at the end of the pattern. When you move into the final location, you call solve() again. On this loop, you'll get new_location is None and start moving back until you get to the first location, and you get the error because you can't pop anymore locations from your path. Your check to break the recursion loop doesn't get called until after everything unwinds.

Move your check for "done" in something like this...

location = new_location
if not done:
    self.solve(location)

answered Feb 12, 2014 at 1:38

Paul Becotte

9,9973 gold badges36 silver badges43 bronze badges

Collectives™ on Stack Overflow

How to implement a method recursively in Python

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related