与循环引用相比，超出了最大递归深度

Question

我和学生一起制作了一个有限状态机的简单演示：

s2 = {}
s1 = {}
s1["0"] = s2
s1["1"] = s1
s2["0"] = s1
s2["1"] = s2
machine = {"start": s1, "accepting": [s1]}

def recognize(fsm, in_string):
    return do_recognize(fsm, fsm["start"], in_string)

def do_recognize(fsm, current, in_string):
    if len(in_string) == 0:
        return current in fsm["accepting"]

   return do_recognize(fsm, current[in_string[0]] ,
                 in_string[1:])

print (recognize(machine, "0"))

这台机器可以识别偶数个0的字符串，并且可以很好地处理“好”的字符串（例如“1”或“010”）。但是在一个像上面这样的“坏”字符串上，它得到 进入无限循环，然后在fsm中返回电流时堆栈溢出[“accepting”]。在

我能够确定问题在于两个州的比较。实际上，我只需编写s1==s2就可以生成完全相同的bug。但是s1==s1（良好状态）工作得很好。在

我对所发生的事情最好的猜测是，它正在做一个深入的比较，并试图跟踪s2中的所有引用，这些引用都是循环的。但是为什么它是不对称的（例如，为什么s1==s1没有同样的问题）？我怎样才能避免呢？在

Answer 1

这个问题与s1和s2之间的循环引用有关。在

这使得无法将s1与{}进行比较（就cmp()而言，这两个词典具有无限的深度）。考虑以下因素：

print s1 == s1 # immediately returns True, probably due to equal object ids
print s1 == s2 # RuntimeError: maximum recursion depth exceeded in cmp

这解释了s1 in fsm["accepting"]起作用，s2 in fsm["accepting"]中断的原因。在

解决这个问题的一个简单方法是更换

^{pr2}$

与

return id(current) in map(id, fsm["accepting"])

这将通过标识比较状态，而不是尝试按值比较两个无限深的字典。在