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

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"])

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

Answer 2

比较字典时，字典中的每个项（键/值对）也会进行比较，因此，如果在字典之间有循环引用，其中循环引用涉及相同的键，则在比较它们时，将得到此最大递归深度超出错误：

例如，如果您有s1 == {'0': s2}和s2 == {'0': s1}，那么尝试s1 == s2将导致以下比较，这说明了递归是如何发生的：

s1 == s2  > s1['0'] == s2['0']  > s2 == s1  > s2['0'] == s1['0']  > s1 == s2  > ...

像s1 in [s2]或s2 in [s1]这样的包含测试也会导致这种相等性比较，这就是为什么它会出现在current in fsm["accepting"]的代码中。在

您可以通过使用标识比较而不是相等比较来解决此递归问题，只需将current in fsm["accepting"]替换为以下内容：

^{pr2}$

更好的解决方案可能是不使用循环引用，方法是让状态引用标识符而不是对象本身，例如，可以使用如下结构：

states = {"s1": {"0": "s2", "1": "s1"},
          "s2": {"0": "s1", "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, states[current][in_string[0]], in_string[1:])