Python Recursive function to fetch data from dict

Question

I have created a recursive function to fetch the data from a dictionary. The dictionary consists of keys and each key has a list of keys and it goes on. So I need to fetch the flatten list of keys when I give a key input.

My Dict :

data = {"p": ["s1", "s2", "s3", "s4"],
        "s1": ["s1s1", "s1s2"],
        "s2": [],
        "s3": [],
        "s4": [],
        "s1s1": [],
        "s1s2": ["s1s2s1"],
        "s1s2s1": []
        }

My function :

def get_data(key):
    items = data[key]
    if items:
        for key in items:
            items += get_data(key)
    return items

when i call get_data("p") it returns

['s1', 's2', 's3', 's4', 's1s1', 's1s2', 's1s2s1', 's1s2s1']

But the expected output is :

['s1', 's2', 's3', 's4', 's1s1', 's1s2', 's1s2s1']

Thanks in advance for any help ...

Answer 1

The problem is in these lines -

for key in items:
    items += get_data(key)

Here you are modifying items as you're iterating over it. So in the last iteration, your items ends up getting with the same key multiple times; you can add a logging statement to see which key is being used to call get_data.

You want to obtain all the new items separately, and then update items after the iteration is done -

new_items = []
for key in items:
    new_items += get_data(key)
items += new_items