pythonsearchrecursiondictionary

# Finding a key recursively in a dictionary

I'm trying to write a very simple function to recursively search through a possibly nested (in the most extreme cases ten levels deep) Python dictionary and return the first value it finds from the given key.

I cannot understand why my code doesn't work for nested dictionaries.

``````def _finditem(obj, key):
if key in obj: return obj[key]
for k, v in obj.items():
if isinstance(v,dict):
_finditem(v, key)

print _finditem({"B":{"A":2}},"A")
``````

It returns `None`.

It does work, however, for `_finditem({"B":1,"A":2},"A")`, returning `2`.

I'm sure it's a simple mistake but I cannot find it. I feel like there already might be something for this in the standard library or `collections`, but I can't find that either.

If you are looking for a general explanation of what is wrong with code like this, the canonical is Why does my recursive function return None?. The answers here are mostly specific to the task of searching in a nested dictionary.

Solution

• when you recurse, you need to `return` the result of `_finditem`

``````def _finditem(obj, key):
if key in obj: return obj[key]
for k, v in obj.items():
if isinstance(v,dict):
return _finditem(v, key)  #added return statement
``````

To fix the actual algorithm, you need to realize that `_finditem` returns `None` if it didn't find anything, so you need to check that explicitly to prevent an early return:

``````def _finditem(obj, key):
if key in obj: return obj[key]
for k, v in obj.items():
if isinstance(v,dict):
item = _finditem(v, key)
if item is not None:
return item
``````

Of course, that will fail if you have `None` values in any of your dictionaries. In that case, you could set up a sentinel `object()` for this function and return that in the case that you don't find anything -- Then you can check against the `sentinel` to know if you found something or not.