随机游走问题（逃避递归）

Question

作为练习，并且为了给我心里想的一个更复杂、更大的项目做准备，我用Turtle模块写了一个随机游走的脚本。我知道其实有更简单的方法可以实现随机游走，而不需要去找相邻的坐标，但我觉得这对我后面的实现是必要的。

我遇到的问题是，在getnext()这个函数里，Python达到了最大递归深度，因为它发现自己已经访问过所有相邻的单元格。我不太确定如果发生这种情况，我该如何跳出这个循环，继续正常进行。

import turtle
import random




class cell(object):
def __init__(self, pos, visited = False):
    self.xCoord = pos[0]
    self.yCoord = pos[1]
    self.visited = visited
    self.neigh = []
    self.neighbors = self.getneighbors()

def getneighbors(self):
    for j in (-1, 0, 1):
        for i in (-1, 0, 1):
            self.neigh.append((self.xCoord+i, self.yCoord+j))



def getnext():
   nextindex = random.randint(0, len(c.neigh)-1)
   nextcoordt = c.neigh[nextindex]
   nextcoord = list(c.neigh[nextindex])
   if nextcoordt in coords:
       getnext()
   else:
      turtle.goto(nextcoord[0], nextcoord[1])



coords = {} 

turtle.setup(width =200, height = 200, startx = 0, starty = 0)
turtle.trace = False

for i in range(1000):
    c = cell(list(turtle.pos()))
    coords[turtle.pos()] = (c)
    getnext()

另外，这实际上是我第一次真正应用面向对象编程（OOP），我在想这样使用它是否合适。

非常感谢！

Answer 1

如果你的随机漫步发现自己已经访问过每一个相邻的格子，它就会一直循环下去。因为你使用了递归，这样很快就会超过最大递归限制。

我相信这个可以用面向对象编程的方式来写，但问题主要出在你使用递归的方式，而不是cell类是否有用。例如，我把你的代码简化成线性运行的方式。具体的改动有：

• 去掉(0, 0)这个方向，因为它不会让你向前移动。（这可以根据你的目标选择，看看你是否认为“原地不动”是一个有效的移动。）
• 使用random.choice()来随机选择下一个移动的方向。
• 去掉递归，改为通过将方向向量加到当前位置来计算下一个坐标。简单的循环就可以了。
• 不检查下一个位置是否在最近的历史位置中，因为返回到之前的格子在随机移动中是完全有效的。

代码：

import itertools
import random
import turtle

# change step size if you like
STEP = 1
PTS = [-STEP, 0, STEP]
DIRS = [(x, y) for x in PTS for y in PTS if x or y]

turtle.setup(width=400, height=400, startx=0, starty=0)
turtle.trace = False
pos = turtle.pos()

for i in range(1000):
    px, py = turtle.pos()
    # direction of next move
    xd, yd = random.choice(DIRS)
    # set pos to current pos + direction vector
    turtle.goto(px + xd, py + yd)