How to perform recursion in python dictionary

Question

I have a dictionary which I would like to use to create a tree. The idea is to get the value of the index specified, append it to a list. Use this value as index in the next item of the dictionary and the process repeats until when we get a None

My dictionary

dict = {
         'A' : 'AF',
         'BF': 'B',
         'AF': 'Z',
         'Z' : None,
         'B' : 'B'
       }

I can loop through the dict and get the first value, but I can't a better way of loop recursively through the dict.

Note x is my index parameter I would like to specify.i.e A,BF,AF,Z or B

def tree(x,dict):
   result = []
   for value in dict:
      result.append(value)
    #stuck somewhere here. 
    #I would like to use this value as an index again and pick next value. 
    #Do this until I have no further relation

   #print final results in a list
   print result

When tree(x,dict) is called, take x = 'A' the expected result should be:

['A','AF','Z']

Thank you for your assistance and contribution.

Not a must but I have performance in mind too. I might have to read a very large dictionary data set. — felix cheruiyot, Mar 23 '13 at 12:56

jamylak · Accepted Answer · 2013-03-23T13:02:59.723

The non-recursive version is much faster but there's one that looks nice

>>> def tree(D, x):
        if x is None: 
            return []
        else: 
            return [x] + tree(D, D[x])


>>> tree(D, 'A')
['A', 'AF', 'Z']

Or as a one-liner:

def tree(D, x):
    return [] if x is None else [x] + tree(D, D[x])

This will have quadratic runtime since it adds two lists each time, although if you want performance you would just use .append and then it would be much more practical to just use a loop anyway.

score 0 · Answer 2 · answered Mar 23 '13 at 12:50

0

def tree(x,dict):
    old_value = x
    while True:
        value = dict.get(old_value)
        if not value:
            break
        result.append(value)
    print result

answered Mar 23 '13 at 12:50

wRAR

25,009
4
84
97

Thanks for this.Let me go for the recursive one, it fits my requirements well. I have learned something from this. Thanks wRAR – felix cheruiyot Mar 23 '13 at 13:14

El Bert · Answer 3 · 2021-12-29T23:06:20.830

You could also try a recursive generator:

# This will loop "forever"
data = {                                                                        
  'A' : 'AF',                                                          
  'BF': 'B',                                                           
  'AF': 'Z',                                                           
  'Z' : None,                                                          
  'B' : 'B'                                                            
}                                                                      
                                                                                                                                                   
def tree(key):                                                                  
  value = data.get(key)                                                         
  yield key                                                                     
  if value is not None:                                                         
    for value in tree(value):                                                   
      yield value                                                               
                                                                            
for value in tree("A"):                                                         
  # Do something with the value

EDIT: the suggested approach above fails to detect cycles and will loop until maximum recursion depth is reached.

The recursive approach below keeps track of visited nodes to detect cycles and exits if so. The most comprehensible description of how to find cycles is from this answer:

data = {
  'A' : 'AF',
  'BF': 'B',
  'AF': 'Z',
  'Z' : None,
  'B' : 'B'
}

def visit_graph(graph, node, visited_nodes):
    print "\tcurrent node: ", node, "\tvisited nodes: ", visited_nodes
    # None means we have reached a node that doesn't have any children
    if node is None:
        return visited_nodes
    # The current node has already been seen, the graph has a cycle we must exit
    if node in visited_nodes:
        raise Exception("graph contains a cycle")
    # Add the current node to the list of visited node to avoid cycles
    visited_nodes.append(node)
    # Recursively call the method with the child node of the current node
    return visit_graph(graph, graph.get(node), visited_nodes)


# "A" does not generate any cycle
print visit_graph(data, "A", [])

# Starting at "B" or "BF" will generate cycles
try:
    print visit_graph(data, "B", [])
except Exception, e:
    print e

try:
    print visit_graph(data, "BF", [])
except Exception, e:
    print e

How to perform recursion in python dictionary

3 Answers3