RecursionError:获取对象的str时超出了最大递归深度

Question

在这里看到这么多关于这个问题的例子,但是不能理清我的例子.

任何sugegstion将是欣赏,已经有他的recursiona dd无法修复它的headdake.

tree = {}

def populate_node(account):
    node = '%(LOGIN)s,%(server_id)s' % account
    tree[node]['login'] = account['LOGIN']
    tree[node]['email'] = account['EMAIL'].lower()
    tree[node]['server_id'] = account['server_id']

for account in accounts:
    node = '%(LOGIN)s,%(server_id)s' % account
    parent = None
    if account['AGENT_ACCOUNT']:
        parent = '%(AGENT_ACCOUNT)s,%(server_id)s' % account
    if node not in tree:
        tree[node] = {}
    populate_node(account)
    if parent:
        tree[node]['parent'] = parent
        if parent not in tree:
            tree[parent] = {
                'login': parent,
                'server_id': account['server_id'],
                'children': [node],
            }
        else:
            if 'children' not in tree[parent]:
                tree[parent]['children'] = [node]
            else:
                tree[parent]['children'].append(node)

def get_path(node, tree):
    parent = node.get('parent')
    node_login = str(str(node.get('login')) + ',' + str(node.get('server_id')))
    if not parent:
       return []
    elif parent == node_login:
       return [parent]
    path = get_path(tree[parent], tree)
    return [parent] + path


for k, v in tree.items():
      v['path'] = get_path(v, tree)
      v['level'] = len(v['path']) + (1 if v['login'] != v.get('parent') else 0)

默认情况下 :

tree = {}

节点是一个项目tree.

样本树:

tree = {
    '1987,mt4-demo-0': {
        'login': 1987,
        'email': 'email_1',
        'server_id': 'mt4-demo-0'
    },
    '16044,mt4-demo-0': {
        'login': 16044,
        'email': 'email_2',
        'server_id': 'mt4-demo-0'
    },
    '160877748,mt4-demo-0': {
        'login': 160877748,
        'email': 'email_3',
        'server_id': 'mt4-demo-0'
    }
}

并且在这个递归错误中得到了每一个

RecursionError: maximum recursion depth exceeded while getting the str of an object

Answer 1

您的代码假定您始终处理非循环有向图,但您的输入中至少有一个有向循环,其中一个AGENT_ACCOUNT引用直接或间接指向另一个帐户,而该帐户又有一个AGENT_ACCOUNT指向第一个帐户的值.

例如,if accounts设置为:

accounts = [
    {'LOGIN': 'foo', 'EMAIL': 'foo@bar.com', 'server_id': 'server 1',
     'AGENT_ACCOUNT': 'bar'},
    {'LOGIN': 'bar', 'EMAIL': 'bar@bar.com', 'server_id': 'server 1',
     'AGENT_ACCOUNT': 'foo'}]

然后tree变成:

{'bar,server 1': {'children': ['foo,server 1'],
                  'email': 'bar@bar.com',
                  'login': 'bar',
                  'parent': 'foo,server 1',
                  'server_id': 'server 1'},
 'foo,server 1': {'children': ['bar,server 1'],
                  'email': 'foo@bar.com',
                  'login': 'foo',
                  'parent': 'bar,server 1',
                  'server_id': 'server 1'}}

注意,foo有一个AGENT_ACCOUNT指向bar,并bar指回foo,形成一个循环.

然后,这将在这两个条目中的任何一个上产生无限递归错误:

>>> get_path(tree['bar,server 1'], tree)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 8, in get_path
  File "<stdin>", line 8, in get_path
  File "<stdin>", line 8, in get_path
  [Previous line repeated 994 more times]
  File "<stdin>", line 2, in get_path
RecursionError: maximum recursion depth exceeded while calling a Python object

您可以提前检测此类周期并退出并显示更清晰的错误消息:

def get_path(node, tree, seen=None):
    if seen is None:
        seen = set()
    parent = node.get('parent')
    if parent:
        if  parent in seen:
            raise ValueError(
                'Already handled {!r}, cycle detected. '
                'Check all of {}'.format(
                    parent, sorted(seen)))
        seen.add(parent)
    node_login = '{0[login]},{0[server_id]}'.format(node)  # cleaner method to generate the key
    if not parent:
        return []
    elif parent == node_login:
        return [parent]
    path = get_path(tree[parent], tree, seen)  # pass seen along to recursive calls
    return [parent] + path

现在运行此更新版本tree会产生:

>>> get_path(tree['bar,server 1'], tree)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 16, in get_path
  File "<stdin>", line 16, in get_path
  File "<stdin>", line 9, in get_path
ValueError: Already handled 'foo,server 1', cycle detected. Check all of ['bar,server 1', 'foo,server 1']fted by one space

我认为这样的周期是错误的.如果不是这样,只需将路径返回到该点if parent in seen: return [](因此忽略循环),但是您将拥有循环的每个成员的路径版本,每个路径都是下一个循环的旋转版本.

您应该真正修复您的帐户信息,并删除此类周期.如果您需要找到所有这些周期,您可以使用:

from collections import deque

def find_all_cycles(tree):
    visited, cycles, path = set(), [], []
    queue = deque(sorted(tree))
    while queue:
        key = queue.pop()
        if key in visited:
            continue
        visited.add(key)
        path.append(key)
        parent = tree[key].get('parent')
        if not parent:
            path = []
        elif parent in visited:
            # cycle detected!
            cycles.append(path + [parent])
            path = []
        else:
            queue.append(parent)
    return cycles