CODEWITHSUNDEEP
pythonrecursiontree
zeebrah
zeebrah

Reputation: 126

Recursive tree search stops too early

I'm fairly new both to Python and Recursion, so I might have failed to find some relevant question but I haven't seen this exact one. I have a task to find children count for each name in the following list:

parents = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'V', 'W', 'X', 'Y', 'Z']

I have the following graph structure with parents above and children below (both in dict and in graph diagram form). Each letter counts as its own child, so the minimal child count is one.

data = {'G': ['F'], 'A': [], 'B': ['A'], 'C': ['A'], 'D': ['B', 'C'], 'E': ['D'], 'F': ['D'], 'X': [], 'Y': ['X', 'A'], 'Z': ['X'], 'V': ['Z', 'Y'], 'W': ['V']}

     A   X
    /|\ / \
   B C Y   Z
    \|  \ /
     D   V
    / \   \
   E   F   W
        \
         G

I happen to know the right answers to the question

Node   Correct   My_answers
A       10          10
B       5           1          Incorrect
C       5           5
D       4           4
E       1           1
F       2           2
G       1           1
V       2           2
W       1           1
X       5           2          Incorrect
Y       3           3
Z       3           1          Incorrect

I've tried to split the solution into two different functions then print out the answers using a simple loop. is_parent() checks whether par is a parent if cld and if I'm not mistaken this implies that cld is a child of par. I've done it that way due to the input format. Then I have child_count() that just spits out the counter by iterating over all the names and checking whether given potential child (pot_child) has par as its parent. My suspicion is that I have a problem in is_parent() that spits out False before it extensively checked all the tree branches therefore leading to child count below true ones.

Here is complete code I wrote, data and parents are defined above.

def is_parent(cld, par, data):
    if cld == par:
        return True
    else:
        for par_2 in data[cld]:
            x = is_parent(par_2,par,data)
        if len(data[cld]) == 0:
            x = False
    return x
def child_count(par, data):
    cnt = 0
    for pot_child in data:  # for each potential child
        cnt += 1 if is_parent(pot_child, par, data) else 0
    return cnt


for parent in parents:
    print(parent,":",child_count(parent, data))

Sorry for overly long introduction to the question, but the essence of what I'm trying to ask is two-fold. First, is my general approach to the problem is suitable (two functions and then a loop), is there a faster, more readable alternative? Second, how do I prevent my recursive search algorithm from stopping the search too early (I've tried the visualizer but it stops after 1000 steps which is not enough for my algorithm)? How to make sure (in general) that recursive algorithm does not stop too early.

I would also greatly appreciate some free resources to get solidly acquainted with how to properly write recursion in Python

Thanks is advance!

Upvotes: 0

Views: 105

Answers (1)

VPfB
VPfB

Reputation: 17362

The error is here:

def is_parent(cld, par, data):
    if cld == par:
        return True
    else:
        for par_2 in data[cld]:
            x = is_parent(par_2,par,data) # <=== if x is True, return True!
            if x: break # <== quick fix
        if len(data[cld]) == 0:
            x = False
    return x

The login behind is simple. If one of the graph "branches" leads to the parent, the result is True regardless of other branches

After some cleanup:

def is_parent(cld, par, data):
    return cld == par or any(is_parent(par_2,par,data) for par_2 in data[cld])

The oriented graph must not contain loops. The title mentions a "tree", even if the example data is not strictly a tree, but it is loop free. If loops were allowed, a set of visited nodes would be needed to stop endless recursion.

(I'm sorry for not answering the question how to write recursive functions in general and what resources are recommended)

Upvotes: 1

Related Questions