How to keep looping within a python dictionary to search for values?

Question

parent = {'Amy':'Ben', 'May':'Tom', 'Tom':'Ben',
 'Ben':'Howard', 'Howard':'George', 'Frank':'Amy',
 'Joe':'Bill', 'Bill':'Mary', 'Mary':'Philip', 'Simon':'Bill',
 'Zoe':'Mary'}

This is the parent dictionary mentioned in the question. My task is to:

find out whether the 2 names inputted are ancestors. For example, Amy's parent is Ben, Ben's parent is Howard, so Howard and Amy are related as ancestors.

Below is my code:

    def is_ancestor(name1,name2,pdict):
        for name in pdict:
            parent = pdict.get(name2)
            parent2 = pdict.get(parent)
            if(name1 == parent2):
                return True
            else:
                return False

This will work for the example case i mentioned above. But what if the question is 'Amy' and 'Howard'? It should return True as 'Amy' parent is 'Tom', Tom parent is Ben and Ben parent is Howard. So amy and howard are ancestors. But my code will stop after getting tom and ben. how to keep it looping till i meet with a correct answer?

Below is the exact Question:

Person A is an (indirect) ancestor of Person B if Person B is considered to be one of the many descendants of Person A.

In the example ancestry tree given above, Howard is an ancestor of Amy, but Amy is not an ancestor of Tom.

And that person himself is NOT his own ancestor. Your task is to write a function,
is_ancestor(name1,name2,pdict), that takes in three arguments.

The first two arguments are the names of people (strings), while the third argument is
the parent dictionary mentioned above.

The function should return the boolean value ‘True’ if the first person in the argument list is an ancestor of the second person,

and ‘False’ if the first person in the argument list is not an
ancestor of the second person.

Answer 1

Here is your answer using recursion:

def is_ancestor(name1, name2, pdict):

    try:
        if pdict[name1] == name2:
            return True
        else:
            return is_ancestor(pdict[name1], name2, pdict)
    except KeyError:
        return False

First it checks if it has found a direct ancestor, if not, checks the next generation by recursing over the same function. The KeyError exception gets triggered if the ancestor is not found, indicating that name2 is not an ancestor of name1.

Answer 2

You can use recursion instead of a loop.

def is_ancestor(name1, name2, pdict):
    parent = pdict.get(name2, None)
    if not parent:
        return False
    elif parent == name1:
        return True
    else:
        return is_ancestor(name1, parent, pdict)

parents = {'Amy':'Ben', 'May':'Tom', 'Tom':'Ben',
 'Ben':'Howard', 'Howard':'George', 'Frank':'Amy',
 'Joe':'Bill', 'Bill':'Mary', 'Mary':'Philip', 'Simon':'Bill',
 'Zoe':'Mary'}

print(is_ancestor("Amy", "Ben", parents))
print(is_ancestor("Ben", "Amy", parents))
print(is_ancestor("Howard", "Amy", parents))

The function gets the parent of name2. If no parent is found, we've reached the base case and we return False. Otherwise, we check to see if the parent found is the one we're looking for. If it is we return True. If not, we look to see if that person's parent is the ancestor we're looking for. This will keep recursing until we either reach the ancestor we're looking for, or we hit a person with no parent in the dictionary.