Create a nested dictionary using recursion Python

Question

I'm trying to wrap my head around how recursion works, particularly how you can break it down into sub parts and work on that while maintaining that it all belongs to one overall part, if that makes any sense.

So for example: if I am given a list like [1,2,3,4,5] and I want to write a function that continuously creates a dictionary within a dictionary with each element in the list being the key; the output being like this - {1:{2:{3:{4:{5:{}}}}}}.

I know it can be done with a simple for loop but the point is I want to learn how recursion works. Here is what I tried and I know it's probably pretty far off. :(

data = [1,2,3,4,5]
split_order = dict()

def split(data, split_order):
  if len(data) == 0:
      return split_order
  else:
      attr = data[0]
      new_data = data[1:]
      split_order[attr] = dict()
      split_order[attr] = split(new_data, split_order[attr])

Patrick Haugh · Accepted Answer · 2018-09-16 00:15:26Z

4

You're not returning anything in your else clause. You also don't need to pass split_order into your function:

def split(data):
    if data:
        head, *tail = data  # This is a nicer way of doing head, tail = data[0], data[1:]
        return {head: split(tail)}
    else:
        return {}

answered Sep 16, 2018 at 0:15

Patrick Haugh

61.3k13 gold badges94 silver badges101 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

not_a_bot_no_really_82353 · Accepted Answer · 2018-09-16 00:32:20Z

2

To understood recursion is difficult. So to make it a little simpler I simplified the code (I removed the second parameter, you do not need it):

def split(data):
  if len(data) == 0:
      return data #trivial case, we have no element therefore we return empty list
  else: #if we have elements
      first_value = data[0] #we take the first value
      data = {first_value : split(data[1:])} #data[1:] will return a list with every value but the first value
      return data #this is called after the last recursion is called

If you call it with split[1,2,3,4,5] it returns {1: {2: {3: {4: {5: []}}}}}

Let's see what we have. We have the part that breaks the recursion, this is often called the anchor (at least in my language). We simply check if the data is empty. You did that part as well.

The second part will extract the first value and call the split but with a shorter list. Usually this part will work on the provided data and then call itself. It is advantageous if the data (list) is constantly getting smaller so that the anchor can be called at some time in the future. So usually you remove one or more items.

If we step trough the code we can see what the recusion is calling. If our input is [1,2,3] we call: split([1,2,3]) -> split([2,3]) -> split([3]) -> split() Only after the last call is done we start to return the values (in this order): [] -> {3: []} -> {2: {3: []}} -> {1: {2: {3: []}}}

edited Sep 16, 2018 at 0:32

answered Sep 16, 2018 at 0:19

not_a_bot_no_really_82353

6197 silver badges20 bronze badges

1 Comment

not_a_bot_no_really_82353 Over a year ago

Little note for the math interested people, a recursion can be compared to the mathematical induction. The base case is the anchor, the induction step the body.

Collectives™ on Stack Overflow

Create a nested dictionary using recursion Python

2 Answers 2

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related