Menu
G'day,
I am trying to find the recursive depth of a function that trawls a dictionary and I'm a bit lost... Currently I have something like:
myDict = {'leve1_key1': {'level2_key1': {'level3_key1': {'level4_key_1': {'level5_key1': 'level5_value1'}}}}}
And I want to know just how nested the most nested dictionary is... so I do the following...
def dict_depth(d, depth):
for i in d.keys():
if type(d[i]) is dict:
newDict = d[i]
dict_depth(newDict, depth+1)
return depth
print dict_depth(myDict, 0)
Only problem is, the recursive loop only returns the return of the final value (0).
if I put in a print statement
for i in d.keys(): then I can at least print the highest value of recursion, but returning the value is a different matter...
I'm sure this is straightforward - I've just got jellybrain.
768
Python's default recursion limit is 1000, meaning that Python won't let a function call on itself more than 1000 times, which for most people is probably enough. The limit exists because allowing recursion to occur more than 1000 times doesn't exactly make for lightweight code.
With recursion We can design a function that will recursively call itself to check the values of the dictionary. As long as the inner element is evaluated to be a dictionary, the function will call itself and we will get the result for the depth of the dictionary.
The maximal number of nested calls (including the first one) is called recursion depth. In our case, it will be exactly n . The maximal recursion depth is limited by JavaScript engine. We can rely on it being 10000, some engines allow more, but 100000 is probably out of limit for the majority of them.
Dictionaries are mutable. Items are accessed by their position in a dictionary. A dictionary can contain any object type except another dictionary. Dictionaries can be nested to any depth.
Be sure to assign the result of the recursive call to depth. Also, as @amit says, consider using max so that you can handle dicts with multiple key value pairs (a treelike structure).
def dict_depth(d, depth=0):
if not isinstance(d, dict) or not d:
return depth
return max(dict_depth(v, depth+1) for k, v in d.iteritems())
>>> myDict = {'leve1_key1': {'level2_key1':
{'level3_key1': {'level4_key_1':
{'level5_key1': 'level5_value1'}}}}}
>>> dict_depth(myDict)
5
You should store the value retured from the recursive call, and return the max value found, otherwise - you are calling the recursive function without doing anything with the returned value! [and returning 0 as expected, since it was never changed]
def dict_depth(d, depth):
ret = depth
for i in d.keys():
if type(d[i]) is dict:
newDict = d[i]
ret = max(dict_depth(newDict, depth+1),ret) #finding max and storing it
return ret #returning the max found
MyDict = {'a': {'a1': {'a11': 5, 'a12':[{2:'a22'}], 'a13':{'a14':'a11'}}, 'a2': 6}, 'b':{7:{8:{9:{10:{11:'11'}}}}}, 'c': {'c1': 18, 'c2': 1}}
def find_depth(dep,val):
if isinstance(val,dict):
dep=dep+1
for j in val:
find_depth(dep,val[j])
temp_depth.append(dep)
dep=0
return max(temp_depth)
elif isinstance(val,list):
for k in val:
find_depth(dep,k)
max_depth={}
for i in MyDict:
dep=0
temp_depth=[]
max_depth.update({i:(find_depth(dep,MyDict[i]))})
print max_depth
Here is code works fine if even list also included.
26
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
