# Save descendence in family tree with a recursive function in Python

I have a dictionary of a family tree with the name of the child as the key and their dad's and mom's name in a list as the value.

``````d = {
'Kevin': ('Tom', 'Marge'),
'Marge': ('John', 'Mary'),
'Elle': ('Tom', 'Marge'),
'Seth': ('Tom', 'Marge'),
'Mary': ('Carl', 'Elena'),
'Tom': ('Joseph', 'Alice'),
'Alice': ('Rob', 'Amy'),
'John': ('James', 'Elena'),
'James': ('Nick', 'Maria') }
``````

I need to write a recursive function so that it returns True when there is a descendence between two people. If there is a descendance, it has to print out the chain of relations, i.e:

``````>>> print("Is there a lineage?", lineage('Amy', 'Kevin', d))
Amy
Alice
Tom
Kevin
Is there a lineage? True
``````

Otherwise if there isn't one:

``````>>> print("Is there a lineage?", lineage('Mary', 'Alice', d))
Is there a lineage? False
``````

This is what I've got so far. It seems to return True or False consistantly, but I'm having troubles figuring out how to save the path between the two people.

``````line = []

def lineage(parent, child, d):

try:
if parent in d[child]:
line.append(parent)
else:
try:
except:
lineage(parent, mom, d)

return True

except:
return False
``````

I'm new to recursion, so any ideas or help on how to approach this are much appreciated.

• I made your function return the path, instead of `True`, when a path exists.
• I recommend avoiding `try / except` here.

It is true that trying to access `d[child]` without checking that `child` is in `d` might result in an Exception. However, this is the base-case of your recursion; your code will be easier to understand if the base case is clearly identified with an explicit `if` at the beginning of your function, rather than with an obscure "some Exception happened" with no explanation at the end of your function.

``````def lineage(parent, child, d):
if parent == child:
return [child]
elif child not in d:
return False
else:
else:
path_via_mom = lineage(parent, mom, d)
if path_via_mom:
path_via_mom.append(child)
return path_via_mom
else:
return False
``````

Here is a shorter, equivalent version, relying on the specific behaviour of logical operator `or` in python:

``````def lineage(parent, child, d):
if parent == child:
return [child]
elif child not in d:
return False
else:
``````>>> lineage('Amy', 'Kevin', d)