CODEWITHSUNDEEP
pythondjangoinfinite-recursion
Alex P.
Alex P.

Reputation: 47

Recursive function to calculate the children of a parent

I have a set of data that looks like this:

If I try to calculate the whole tree for Person1, the max recursion will be exceeded and the program will terminate in an error. The expected result would be Person1 -> [Person2, Person3, Person4], so basically in the case the the calculation has to be repeated for an element that is already in the list, this has to be ignored. Do you have an idea, how could I solve this problem?

My function looks something like this:

def compute_children(self):
    children = []
    children.extend(self.child)
    for child in children:
        temp = child.compute_children()
        if 0 < len(temp):
            children.extend(temp)
    return children

Upvotes: 1

Views: 610

Answers (1)

Lajos Arpad
Lajos Arpad

Reputation: 76601

A very simple solution would be to create a collection containing your starting node when you call compute_children for the first time and before the loop that you have, add all the children to the collection, ignoring any child that has already found its way into the collection.

In graph-theory this kind of approach is usually referred to as coloring, that is, you store what nodes were already visited somehow, so in the future you will not revisit the same nodes if a cycle is present.

Upvotes: 1

Related Questions