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.

Answer 1

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.