python - 递归错误 : maximum recursion depth exceeded while getting the str of an object

Question

在这里查看了很多关于这个问题的例子，但我无法为我的例子解决这个问题。

任何建议将不胜感激，我已经对这种递归感到头疼了。

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 = {
    '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

您的代码假定您始终处理 acyclic directed graph , 但您的输入至少有一个 directed cycle其中，一个 AGENT_ACCOUNT 引用直接或间接指向另一个帐户，而该帐户又具有指向第一个帐户的 AGENT_ACCOUNT 值。

例如，如果 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'}]

然后树变成:

{'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