如何在Python中使用递归实现方法

Question

我尝试递归地实现这个方法。然而，几秒钟后，我得到了一个索引错误，比如“不能从空堆栈中弹出”。我如何纠正这个错误？从本质上讲，整个代码的要点（我没有包括）是创建一个迷宫并引导机器人通过它。你知道吗

空（未探测）单元格
EMPTY = 0

有障碍物的单元格
OBSTACLE = 1

路径上的单元格
ON_PATH = 2

已探索但不在路径上的单元格
EXPLORED = 3

机器人所在的单元格
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

Answer 1

因为只有在new\u location为None时才会调用pop，self.find\u下一步（）未返回任何。如果没有find\u next\u step（）的代码，就很难确定，但我的猜测是，robot已经遍历了所有路径，回到了起点（有一条空路径），因此.pop（）失败。你知道吗

无论如何，我建议这个错误确实发生在find\u next\u step（）的返回值中。你知道吗

这不是一个真正的答案，但我还没有代表评论，希望这有帮助；）

更新：

好吧，我现在有了更多的信息，但我仍然觉得离了解你的全貌还有很长的路要走。你知道吗

但是，如果SEARCH_ORDER中没有direction的空值，则find_next_step将返回None。（虽然我不知道方向是什么。SEARCH_ORDER大概是一个常数？（不是python的大用户）。你知道吗

不管怎样，当机器人探索或识别了find_next_step观察到的所有细胞时，情况大概就是这样。你知道吗

Answer 2

没有足够的应用程序来确定这一点，但我认为您的问题已经到了模式的末尾。当移动到最终位置时，再次调用solve（）。在这个循环中，你会得到新的位置是无，并开始向后移动，直到你到达第一个位置，你会得到错误，因为你不能弹出更多的位置从你的路径。你的检查，以打破递归循环不会被调用，直到一切解除。你知道吗

把你的支票换成这样。。。你知道吗

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