Creating a nested (resursive) dictionary in python

Question

For a config validation schema I need to have a nested dictionary which repeats itself. For example assume we have the following dictionary:

{
    "conf1": "x",
    "conf2": "x",
}

Now I want to have a key conf3 which contains the existing dictionary recursively for a maximum amount of iterations (i.e. 3 times) So the final result needs to look like this:

{
    "conf1": "x",
    "conf2": "x",
    "conf3": {
        "conf1": "x",
        "conf2": "x",
        "conf3": {
            "conf1": "x",
            "conf2": "x",
        }
    }
}

I tried to write a recursive function, but with this solution conf3 is repeated indefinitely

def build_nested_configuration_schema(schema: dict, iteration: int = 0) -> dict:
    iteration += 1
    if iteration == 3:
        return schema
    schema.update({"conf3": build_nested_configuration_schema(schema, iteration)})
    return schema

new_config = build_nested_configuration_schema({"conf1": "x", "conf2": "x"})

Your `iteration` variable is never incremented in your code, except once at the start of the function. You want to increment it once one iteration is done. — kelyen, Jan 05 '22 at 19:20
The issue is you are using the restated schema value for return. So instead of the values being unique, the value of conf3 is a pointer to the same values. Ideally you can use the copy package and instead of using schema, use a copy of the schema. — pypalms, Jan 05 '22 at 19:28

pypalms · Accepted Answer · 2022-01-05T19:34:26.090

1

Based on my comment, using the copy package will disconnect the pointer reference as your example results in.

import copy
def build_nested_configuration_schema(schema: dict, iteration: int = 0) -> dict:
    internal_schema = copy.copy(schema)
    iteration += 1
    if iteration == 3:
        return internal_schema
    schema.update({"conf3": build_nested_configuration_schema(internal_schema, iteration)})
    return schema

new_config = build_nested_configuration_schema({"conf1": "x", "conf2": "x"})
print(new_config)

Prints

{'conf1': 'x', 'conf2': 'x', 'conf3': {'conf1': 'x', 'conf2': 'x', 'conf3': {'conf1': 'x', 'conf2': 'x'}}}

The main reason this happens is with recursion, python will end up using the value in the method call as a pointer to a value, rather than a separate stored value. That is why your method does return, and does not hit a recursion max limit. The value of conf3 ends up being {conf1: x, conf2: x, conf3: } which is why debugging will show you a never ending stream of conf3 values. The copy method will work, and there may be more pythonic ways to work around the issue, but this will work if the runtime memory is not being tightly managed.

edited Jan 05 '22 at 19:34

answered Jan 05 '22 at 19:31

pypalms

461
4
12

Thanks for your answer. At the same time I figured something similar myself. Only changed the schema parameter from the recursive call to `schema.copy()` – Bram Gerritsen Jan 05 '22 at 19:32
What would be the advantage of using the copy package instead of `copy` function which is available on dictionary types? – Bram Gerritsen Jan 05 '22 at 19:36
Yep that is another option for using copy of the dictionary object itself. I don't know if it would work well for complex dictionaries where it has multiple layers of keys, and I've used deepcopy is needed in some cases. – pypalms Jan 05 '22 at 19:36
1

Thanks a lot for your extensive answer! will mark yours as accepted answer. – Bram Gerritsen Jan 05 '22 at 19:38
@BramGerritsen the copy from the dictionary itself will be a reference to the value, basically making another pointer to the value in memory. This is basically what copy from the copy library does as well. The main benefit would be in the complex dictionaries, where a deepcopy is allocating an entirely new memory space for the full dictionary value. This can be very helpful if you need to make modifications to nested sets and need to keep the original data intact - here is a nice explanation: https://stackoverflow.com/a/3975388/9722265 – pypalms Jan 05 '22 at 19:40

score 0 · Answer 2 · answered Jan 05 '22 at 19:35

My solution. As pypalms correctly indicates we need to make a copy of schema.

def build_nested_configuration_schema(schema: dict, iteration: int = 0) -> dict:
    iteration += 1
    if iteration == 3:
        return schema
    schema.update({"conf3": build_nested_configuration_schema(schema.copy(), iteration)})
    return schema

score 0 · Answer 3 · answered Jan 05 '22 at 19:42

This solution uses the originally provided schema as a template and does not require recursion.

def build_nested_configuration_schema(schema: dict) -> dict:
    maxNesting = 3
    
    result = schema.copy()
    current = result
    
    for i in range(maxNesting - 1):
        next = schema.copy()
        current['conf3'] = next
        current = next

    return result

new_config = build_nested_configuration_schema({"conf1": "x", "conf2": "x"})

print(new_config)

Also a nice solution! Always many solutions to a similar problem. Thanks for your contribution. — Bram Gerritsen, Jan 05 '22 at 20:12

Creating a nested (resursive) dictionary in python

3 Answers3