CODEWITHSUNDEEP
pythondictionaryrecursion
Joe
Joe

Reputation: 223

Maximum recursion depth exceeded in comparison in python?

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? enter image description here

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}

Upvotes: 3

Views: 1332

Answers (2)

Stefan Pochmann
Stefan Pochmann

Reputation: 28606

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, [])

Upvotes: 0

T. Claverie
T. Claverie

Reputation: 12246

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.

Upvotes: 1

Related Questions