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.

Binary Trees and Intuition

This week I was particularly interested in the use of binary trees for the purpose of organizing information. I think there is still a tendency, even amongst people born in the information age, to look at computer programming as an enigmatic and inaccessible activity. However, this week's study of binary trees reminded me that the computer is a human invention that, as such, is often fundamentally grounded in common human experience, not esoteric computational jargon. A binary tree's use of roots, branches, and leaves is clearly reflective of the natural world, and therefore requires little thinking to at least conceptually understand. In light of this, I think binary trees are a great example of the approachability of computer science. Perhaps, this and similarly intuitive concepts can be used to convince people with computer-phobia that programming is not as enigmatic as many people think.

I'd also like to give a shout out to CaroneCSC148 for his/her post on trees. It provides information on tree traversal: inorder, preorder, and postorder. Great job!

Binary Code

 As students of computer science, our work tends to strive for utilitarian value-- We want our code to have a clear and useful purpose. In doing this, however, we often obscure or overlook what is going on behind-the-scenes in a programming language, and focus solely on how we can use a programming language to a productive end. However, in doing so I think we necessarily lose sight of some of the simple wonders of computer science: the application of binary code.

In this week's lab, we learned about ways in which binary code can represent numerical values other than 1 and 0. For instance, "10" represents "2," "11" represents "3," and "100" represents "4." In learning this, I was amazed, again, by the fact that all information, however complex, can be represented via two characters: "1" and "0". We can teach computers to complete myriad tasks with these two simple values. But how, then, did we first teach computers to handle binary code? If there was no linguistic foundation, i.e. the kind that binary code provides for all other programming languages, how did we teach computers to learn how to interpret simple code? How did we make something, i.e. binary code, out of nothing?

I'd also like to take a moment to recognize Denise Jiang's post on recursion. She provides a great analogy for a recursive function without a base case: two parallel mirrors.

Classes and Teachers, Subclasses and Students

In this week's lab, we focused on class inheritance: we created class Motorized and subclasses Car and Motorcycle. In designing the lab's classes and subclasses, I was particularly interested in the manipulatability and reproducibility of classes via subclasses.

The natural world is defined by scarcity of all material objects. This idea is what allows the laws of supply and demand to function. But, can the same be said of immaterial properties, such as ideas? Surely human thought as an abstract concept is something every human being can enjoy endlessly, within the span of his or her life. Moreover, human thought can be reproduced via teaching; if I have a unique thought, I can share it with other individuals, so that we all possess that thought. Unlike material goods, conveying a thought does not involve a forfeiting of it, as would be the case in giving a material good to someone. Keeping this idea in mind, I would like to compare Classes to teachers and Subclasses to students. A Class contains a unique, original idea. However, it can share that idea with subclasses without having to give up its original idea. Rather, it disseminates its ideas to multiple subclasses, which can then manipulate this idea, to a point, to perform operations slightly different from those performed by the original class. The parallel between classes and teachers demonstrates one of the merits, as well as dangers, of computer programming: the ability to endlessly reproduce and share information at next to no material cost.

For more info on classes and subclasses, you might want to check out Forest Li's post on the topic. He does a great job of explaining the fundamental principles of classes and subclasses. He also takes the time to provide some examples.

Additionally, if you're still interested in exploring the topic of object-oriented programming, I suggest checking out GR's week three post. GR does a great job of explaining the concept technically via Pythonic terms. He/she also provides some useful comparisons for people who are not yet comfortable with technical jargon.