Recursion

Over the past few weeks, we have spent a considerable amount of time studying recursion. Recursion allows programmers to compensate for unpredictably nested ADTs, such as lists, tuples, or dictionaries. Any of these three types of objects are capable of having nested values, which a for loop, at least from what we have learned so far, is incapable of collecting data from in an efficient manner. Recursive data structures always have at least two definitions, of which one is circular. For example, we can define a nested string list as: a) a nested string list or b) strings. In this case, a is the circular definition because it defines a nested string list as a nested string list. Keeping this in mind, if we wanted to, say, count the number of strings in a nested string list, a recursive function would refer to these two definitions to count strings until it reads every nested string list within the original list. If it met definition b it would add +1 to an accumulator variable. In the end, the function will return the accumulator variable. If it met definition a it would enter the next nested string list, perform the recursive function, and add it's output to the accumulator variable at the level above. The accumulator variable at the top level at the function, i.e. outside all of the nested string lists of x depth, will eventually equal the sum of the outputs of every recursion performed.

So far in lecture, we have mainly covered recursion over nested lists. For the sake of practice, this week I wrote a function that counts the number of nested dictionaries within a dictionary. It accounts for the possibility of dictionaries being nested within dictionaries and/or lists. If you're interested, or have any suggestions for how I can improve my code, please let me know!

def num_dictionaries(o: object) -> int:
    """Return number of dictionaries in o.
    """

    total_dicts = 0

    if o == {}:
        return 1
    elif isinstance(o, dict):
        for key in list(o.keys()):
            if isinstance(o[key], dict):
                total_dicts += num_dictionaries(o[key]) + 1
            elif isinstance(o[key], list):
                total_dicts += num_dictionaries(o[key])
            else:
                total_dicts += 0
    elif isinstance(o, list):
        for item in o:
            if isinstance(item, dict):
                total_dicts += num_dictionaries(item) + 1
            elif isinstance(item, list):
                for subitem in item:
                    total_dicts += num_dictionaries(subitem)
            else:
                total_dicts += 0
    else:
        total_dicts += 0

    return total_dicts

I'd also like to take this opportunity to thank http://lambda--x.blogspot.ca/ for the words of support in his/her post: http://lambda--x.blogspot.ca/2014/02/meta-recursion.html! I have also enjoyed reading your slog. I appreciate the amount of work that you put into it. Your posts, such as the one above, have exposed me to ideas that we don't encounter in-class, and have made me value CSC148H's slogging community.