Why does my recursive function return “None”?

Question

All,

I have a dictionary of lists of dictionaries in Python. This represents a parent-child relationship. Given a child, I would like to return the parent.

Here is my collection:

tree = { u'one' : [ { u'two' : [ { u'three' : [] }, { u'four' : [] } ] }, { u'five' : [ { u'six' : [] } ] } ] }

As you can see, "one" has children "two" and "five", "two" has children "three" and "four", "three" has no children, and so on.

The following code correctly works out the parent of a given child:

def find_parent(search_term,collection,parent=None):
  if isinstance(collection,dict):
    for key,value in collection.iteritems():
      if key.lower() == search_term.lower():
        print "the parent of %s is %s" % (key,parent)
        return parent
      if isinstance(value,list):
        for v in value:
          find_parent(search_term,v,key)

my_child = "two"
my_parent = find_parent(my_child,tree)

The print statement in that function always prints the correct values. But if I try to access my_parent, its value is always "None". Something must be going out of scope here. I just can't work out how to fix it.

Thanks.

Answer 1

You call find_parent(search_term,v,key) recursively but ignore the returned value. I suggest that you find a good Python IDE and learn to use its debugging functionality. This will greatly help you to track down logic errors such as this.

Answer 2

You need to return the recursive call value too:

if isinstance(value,list):
    for v in value:
        parent = find_parent(search_term,v,key)
        if parent is not None: return parent

Without the return you ignore, discard, the recursive search return value.

Demo with the return added:

>>> def find_parent(search_term,collection,parent=None):
...   if isinstance(collection,dict):
...     for key,value in collection.iteritems():
...       if key.lower() == search_term.lower():
...         print "the parent of %s is %s" % (key,parent)
...         return parent
...       if isinstance(value,list):
...         for v in value:
...           parent = find_parent(search_term,v,key)
...           if parent is not None: return parent
... 
>>> my_child = "two"
>>> tree = { u'one' : [ { u'two' : [ { u'three' : [] }, { u'four' : [] } ] }, { u'five' : [ { u'six' : [] } ] } ] }
>>> find_parent(my_child,tree)
the parent of two is one
u'one'