How to detect last call of a recursive function?

Question

I have a list of complex dictionaries like this:

data = [
  {
    "l_1_k": 1,
    "l_1_ch": [
      {
        "l_2_k": 2,
        "l_2_ch": [...more levels]
      },
      {
        "l_2_k": 3,
        "l_2_ch": [...more levels]
      }
    ]
  },
  ...more items
]

I'm trying to flatten this structure to a list of rows like this:

list = [
  { "l_1_k": 1, "l_2_k": 2, ... },
  { "l_1_k": 1, "l_2_k": 3, ... },
]

I need this list to build a pandas data frame.

So, I'm doing a recursion for each nesting level, and at the last level I'm trying to append to rows list.

def build_dict(d, row_dict, rows):
    # d is the data dictionary at each nesting level
    # row_dict is the final row dictionary
    # rows is the final list of rows
    for key, value in d.items():
        if not isinstance(value, list):
            row_dict[key] = value
        else:
            for child in value:
                build_dict(child, row_dict, rows)
    rows.append(row_dict) # <- How to detect the last recursion and call the append

I'm calling this function like this:

rows = []
for row in data:
    build_dict(d=row, row_dict={}, rows=rows)

My question is how to detect the last call of this recursive function if I do not know how many nesting levels there are. With the current code, the row is duplicated at each nesting level.

Or, is there a better approach to obtain the final result?

Correct me if I am wrong, but you want to "append" the rows at the *deepest* level, correct? Or am I misunderstanding? E.g. do you want to keep recursing until you cannot go deeper then append, or do you want to append just before quitting the function? Also, can you provide a full sample data so I can do some tests on it? — Zaid Al Shattle, Oct 22 '21 at 14:19
That's correct. I need to append when at the deepest level. So, the final list will contain a separate row for each children at that final level. — Igor Moraru, Oct 22 '21 at 14:21
The main issue I have in mind is that you cannot know the deepest level until you finished iterating, I will think about it for a few minutes, but I do believe there will be a need for multiple functions to really know that, either that or some pre-processing. — Zaid Al Shattle, Oct 22 '21 at 14:30

score 2 · Accepted Answer · edited Oct 22 '21 at 15:10

After looking up some ideas, the solution I have in mind is this:

Declare the following function, taken from here:

def find_depth(d):
    if isinstance(d, dict):
        return 1 + (max(map(find_depth, d.values())) if d else 0)
    return 0

In your function, increment every time you go deeper as follows:

def build_dict(d, row_dict, rows, depth=0):
    # depth = 1 for the beginning
    for key, value in d.items():
        if not isinstance(value, list):
            row_dict[key] = value
        else:
            for child in value:
                build_dict(child, row_dict, rows, depth + 1)

Finally, test if you reach the maximum depth, if so, at the end of your function you can append it. You will need to add an extra variable which you will call:

def build_dict(d, row_dict, rows, max_depth, depth=0):
    # depth = 1 for the beginning
    for key, value in d.items():
        if not isinstance(value, list):
            row_dict[key] = value
        else:
            for child in value:
                build_dict(child, row_dict, rows,max_depth, depth + 1)
    if depth == max_depth:
        rows.append(row_dict)

Call the function as:

    build_dict(d=row, row_dict={}, rows=rows, max_depth=find_depth(data))

Do keep in mind since I don't have a data-set I can use, there might be a syntax error or two in there, but the approach should be fine.

Oh, wow! Thank you very much for your answer. It worked like a charm. I had only to pass the `row` instead of `data` to `find_dept`, since my data is a list, and to increase the `max_depth` by 1. Thank you for your time! — Igor Moraru, Oct 22 '21 at 15:02
you forgot to update the `find_depth` in the recursive call in the declaration — cards, Oct 22 '21 at 15:09
Ah yes, my bad @cards. I had to change the function name since I was already using the word depth, but forgot to edit the recursive call. Thanks! — Zaid Al Shattle, Oct 22 '21 at 15:11

LucG · Answer 2 · 2021-10-22T15:03:59.963

I don't think it is good practice to try to play with mutable default argument in function prototype.

Also, I think that the function in the recursion loop should never be aware of the level it is in. That's the point of the recursion. Instead, you need to think about what the function should return, and when it should exit the recursion loop to climb back to the zeroth level. On the climb back, higher level function calls handle the return value of lower level function calls.

Here is the code that I think will work. I am not sure it is optimal, in term of computing time.

edit: fixed return list of dicts instead of dict only

def build_dict(d):
    """
    returns a list when there is no lowerlevel list of dicts.
    """
    lst = []

    for key, value in d.items():
        if not isinstance(value, list):
            lst.append([{key: value}])
        else:
            lst_lower_levels = []
            for child in value:
                lst_lower_levels.extend(build_dict(child))

            new_lst = []
            for elm in lst:
                for elm_ll in lst_lower_levels:
                    lst_of_dct = elm + elm_ll
                    new_lst.append([{k: v for d in lst_of_dct for k, v in d.items()}])
            lst = new_lst
    return lst

rows = []
for row in data:
    rows.extend(build_dict(d=row))

How to detect last call of a recursive function?

2 Answers2