A real use-case for using a recursion

3 mins
Published on 18 June 2020

I’ve never ever used a recursion, and I never thought I will. So far, loops were enough.

The Challenge

  1. Given a dict/list (object), let’s call it dashboard
  2. Search for dicts in dashboard which posses a given key, "expr" in my case
  3. Each time you find a dict with this key, add the value behind this key to a list and keep on searching through the dashboard
  4. The dashboard contains an unknown number of dicts and lists, which are nested, and you don’t really know the structure of this dashboard, it’s totally unknown before execution time

The data I was working on - Grafana Node-Exporter Dashboard - https://grafana.com/api/dashboards/1860/revisions/19/download (JSON file)

Solution

  1. I used json to import the file, and saved the file’s data in a variable called dashboard
  2. I found out that I need to write down tons of loops, which didn’t make sense, so I thought a recursion might be the solution for this one .. And it was!
  3. I called the function get_expressions but you can call it whatever you want

Here’s the code

import json

with open("node-exporter-full_rev19.json", "r") as file:
    dashboard = json.load(file)


def get_expressions(obj, search_key, my_list=[]):
    if isinstance(obj, list) and len(obj):
        for item in obj:
            get_expressions(item, search_key, my_list)
    elif isinstance(obj, dict):
        if search_key in obj and obj[search_key]:
            return my_list.append(obj[search_key])
        else:
            for key, value in obj.items():
                if (isinstance(value, list) or isinstance(value, dict)):
                    get_expressions(value, search_key, my_list)
    return my_list


result = get_expressions(dashboard, "expr")
pretty_result = json.dumps(result, indent=2, sort_keys=True)
print(pretty_result)
Output
[
...
"node_memory_Shmem_bytes{instance=~\"$node:$port\",job=~\"$job\"}",
"node_memory_ShmemHugePages_bytes{instance=~\"$node:$port\",job=~\"$job\"}",
"node_memory_SUnreclaim_bytes{instance=~\"$node:$port\",job=~\"$job\"}",
"node_memory_SReclaimable_bytes{instance=~\"$node:$port\",job=~\"$job\"}",
"node_memory_VmallocChunk_bytes{instance=~\"$node:$port\",job=~\"$job\"}",
"node_memory_VmallocTotal_bytes{instance=~\"$node:$port\",job=~\"$job\"}",
...
]

Explanation

  1. The function gets an object (dict/list/int/anything), and checks if it’s a non-empty list, and then for each item in this list it executes the same function (recursion)
  2. Once the call on obj is the dict type (elif), we check if search_key is in the dict, if it is, hooray, append to my_list (starts as an empty list) and return my_list (stop condition)
  3. (else in elif) if search_key is not in the dict, we need to go through ALL the keys in the dict (just like we did in the list), if a value in the dict is type of list or dict, execute the function again (recursion)
  4. Eventually return my_list which starts as an empty list by default, and finishes with the list of the values that we searched for (stop condition)

I hope this was clear enough … :)

Related Posts