Maximum recursion depth exceeded in comparison in python?

Question

I'm trying to find each node distance from the starting node and the connections between the nodes is given in a dictionary

My code works well with small dictionary like this example but the problem with dictionaries with more than 20 nodes I got an error

    if child != parent and child not in my_list:
RecursionError: maximum recursion depth exceeded in comparison

I'm stuck here, can anyone help me?

My code

def compute_distance(node, dic, node_distance, count, parent, my_list):
    children = dic[node]
    node_distance[node].append(count)
    for child in children:
        if child != parent and child not in my_list:
            compute_distance(child, dic, node_distance, count + 1, node, children)
    node_distance_dic = {}
    node_distance_dic = {k: min(v) for k, v in node_distance.items()}
    return node_distance_dic

if __name__ == '__main__':
    starting_node = 9
    dic = {0: [1, 3], 1: [0, 3, 4], 2: [3, 5],
                3: [0, 1, 2, 4, 5, 6], 4: [1, 3, 6, 7],
                5: [2, 3, 6], 6: [3, 4, 5, 7, 8],
                7: [4, 6, 8, 9], 8: [6, 7, 9], 9: [7, 8]}  
    print(compute_distance(starting_node, dic, defaultdict(list), 0, 0, []))

Output(key = node, value = distance)

{0: 4, 1: 3, 2: 4, 3: 3, 4: 2, 5: 3, 6: 2, 7: 1, 8: 1, 9: 0}

This is because your recursion stack increases exponentially. Try using an iterative algorithm or some form of memoization. While this algorithm should be ok for a small amount like 20 nodes by increasing the stack depth, it won't be efficient for a bigger or more dense graph. — EvilTak, May 22 '16 at 15:19

T. Claverie · Accepted Answer · 2016-05-22T16:12:29.333

I guess my_list is here to keep track of the nodes already visited, but you never update it. Therefore, you should add the node you are processing in order not to call recursion on nodes that you already went through. Currently, your code goes in infinite loop as soon as there is a cycle in the graph. Plus, don't forget to pass it to the next level:

def compute_distance(node, dic, node_distance, count, parent, my_list):
    my_list.append(node)
    ...
    compute_distance(child, dic, node_distance, count + 1, node, my_list)
    ...

However, this method does not compute the shortest path from the starting node to every other, it just do a simple traversal of the graph (underlying algorithm is DFS).

In order to implement what you want, that is the min distance from the source to every other node, you should look into Breadth-First Search (commonly called BFS).

It will solve your problem in linear time.

I'm keeping truck by inserting children again in the 5 line – Joe May 22 '16 at 15:44 — Joe, May 22 '16 at 15:44
Because you use `children` as last argument on line 5. – T. Claverie May 22 '16 at 15:57 — T. Claverie, May 22 '16 at 15:57

Stefan Pochmann · Answer 2 · 2016-05-22T17:52:48.173

0

Doesn't really have anything to do with the graph size. You already have an infinite recursion even for this tiny graph:

dic = {0: [1, 3], 1: [2, 0], 2: [3, 1], 3: [0, 2]}
compute_distance(0, dic, defaultdict(list), 0, 0, [])

edited May 22 '16 at 17:52

answered May 22 '16 at 15:54

Stefan Pochmann

27,593
8
44
107

if there is a connection between 0:[1] then must be a connection between 1:[0] so the dic is {0:[1,3], 1:[0,2], 2:[1,3], 3:[0,2]} – Joe May 22 '16 at 16:01
Ah, right. Though that still already gets you the infinite recursion. And hmm, apparently I had already thought like that, as for directed graphs, **three** nodes suffice (`{0: [1], 1: [2], 2: [0]}`). – Stefan Pochmann May 22 '16 at 17:49

Maximum recursion depth exceeded in comparison in python?

2 Answers2