Struggles with A2 part 1: Specializing flexibly

In assignment 2 part 1 we were asked to design a classes or class to represent various regex trees. The three types of trees specified in this assignment were Bar("|"), Dot(".") and Star("*"). There are specific restrictions on the number of children given to these trees. Bar and Dot trees can have one or two children, while Star can only have one child.

Initially I decided to model regex trees using as single general RegexTree class. This class would take a root and a list of children. Depending on the given root the RegexTree would impose restrictions on the number of children. There are a number of benefits to this model, first of all all of the trees and subtrees in a regex tree would  the same class, in addition only one class needs to be written. However this design has poor flexibiltiy, and would make expanding the types of regex trees allowed difficult.

This approach would look something like this,

class RegexTree():
    def __init__(root,nodes):
        if root ==  '*'
            make sure number of nodes is equal to 1
        if root == "|"
            make sure number of nodes is equal to 1 or 2
        if root == "."
            make sure number of nodes is equal to 1 or 2
       self.root = root
       self.nodes = nodes

Another approach would be to design a very general regex class with no restrictions on the type of root and number of children. Then for every type of tree (Bar, Dot and Star) design a class that inherits the general regex tree class. This approach means writing four classes instead of one, and overriding the specific classes __repr__() methods. However, I believe this approach is superior to the single RegexTree class approach. Instead of one class specialized for the three tree types, this approach allows for easier expansion for any type of regex tree. The downside to this approach is writing more code and each tree is not the same class.

This approach would look like this,
class RegexTree():
     def __init__(root,nodes):
           self.root = root
           self.nodes = nodes

class BarTree(RegexTree):
    def __init__(nodes):
        root = "|"
        make sure number of nodes is 1 or 2
        super().__init__(root, nodes)
...Similar approach for Dot and Star trees

Both of these approaches have their pros and cons. The first approach is shorter, and all trees and subtrees would be the same class. However, the first approach does not allow for easy expansion of the types of trees. The second approach allows for easy expansion of the types of trees, simply add a new subclass of RegexTree. This approach requires more code, and does not have the benefit of all trees and subtrees being the same class.

For this part of the assignment I decided that the downsides of the second approach do not matter, and that it is the better approach. While all the trees and subtrees are not the same class, this doesn't matter because all of the trees are children of RegexTree, making equality checks and other operations easy. The only downside to this approach is having to write more code.

Week 7: Recursion

We are all familiar with recursion, wether we know it or not. Recursive structures are everywhere, from the food we eat, to a seashell. Recursion is the process of describing repeating items in a self-similar way (Wikipedia). Recursion frequently occurs in nature, and one example if a fern.

This fern, dubbed the Barnsley fern, is named the mathematician Michael Barnsley, who first discovered it. Each leaflet is a smaller version of the whole fern, and each sub-leaflet is a smaller version of the leaflet, and so on.

Recursion in Computer Science

In computer science there are certain problems that are best solved using a recursive solution. A recursive solution is one where the problem is reduced to a self-similar simpler form until a base case is reached.
For example, recursion is very useful when dealing with nested lists. If one wanted to sum up all the numbers in a nested list (ex. sum of [1,3,[1,[2,3]],5] = 15). The way most naturally think about this problem is recursive. We look at the list, and if its a number we add it to a sum, if the item is another list we add up all the items in that list, and add it to the sum. In this example the base case is when the item is a number. If the item of the list is another list, we reduce the problem to adding up the numbers in that sublist. However, if the item is a number we do not reduce the problem, we simply add it to the total.The way to write a method to do this in python is as follows.


This code constructs a list of integers using python comprehension, and takes the sum of the list. With the list [1,2,3] this function would create a list [1,2,3] and take the sum. If the list is nested, like [1,2,[3,4]] it would create a list [1,2, ... then it would take the sum of the nested list [3,4], and add it. The top list is now [1,2,7]. This is summed up for a final answer of 10.

Why use recursion?
Recursion can make solving some problems very easy. Often these problems deal with recursive data structures like nested lists, and is often simpler than a iterative solution. Some problems are very difficult to solve in a iterative fashion.

This code demonstrates the problem with solving a general case nested list. Unless one is sure of the depth of the list, an iterative solution is very difficult. Recursion can be difficult to understand at times, however it is an extremely powerful tool for solving problems.