Week 4 - Part 2:  Recursion, recursion, more recursion, and....turtles?

I got slightly confused at when we were supposed to write our week 3/4 slog entries so I ended up making two week 4 posts; so after this one I'll have covered everything until Jan 31st.

This week we delved into recursive functions with slightly more detail than we did previously.  In both this week's lectures, we did a recursion example in each.  The first was another recursive function involving nested lists and list comprehensions.  In the second, we were introduced to the ancient art of turtle drawing to help illustrate the different steps in the recursive function that was shown.

There really wasn't any spectacularly new content in the first example.  I think that Danny was just trying to emphasize how- when we trace recursive functions -  it's important to know when to 'stop' tracing. Ie, when we traced the behaviour of the function with a singly nested list, we could use that information when we traced a double/triple/etc nested list.  Just for future reference, here's the function from the course website:

Notice the + [0] in the list comprehension - it's to prevent an error when L is an empty list (you cannot take the max of an empty list).

The second example used turtles to visually trace what happens during a recursive function, which I actually found super helpful (since I'm a very visual learner).  Once again, here's the code:

If I set the level to 3, the turtles start drawing the following:

Notice that whenever a new branch is drawn, the following 'sub branch' to be drawn is always red; hence the function does not draw a three branched star from largest to smallest after each iteration of the for loop, but it starts at the tip of each vertex.

Because of fractal drawings, recursive functions have now become much more interesting/easy to understand since I can now see what's happening as the function executes.  I hope Danny uses more visuals like these in the future.

Since there was relatively little completely new content this week, this slog entry will be quite a bit shorter than my previous ones, which I think my TA (or whoever's marking this) will greatly appreciate.

Week 4 - Intro to Recursion, Exceptions, Inheritance

Note that when I say this slog is based on 'week 4', I'm referring to 'Everything that happened in class after we covered basic classes/OOP'.


Before I delve into the broader topics of recursion, exceptions, and inheritance, I'm going to make note of Python's set notation, which I hadn't heard of in CSC108.  Sets are similar to lists, in that they hold several objects, and like dicts, they are also unordered.  However sets, unlike lists and dicts, are collections of unique elements only.  They're denoted with {}.  Consider the following piece of code:

Here, we create the two lists L1 (numbers from 1-4) and L2 (even numbers).  Say we wanted to find the elements that weren't in L2 but were in L1 (odd numbers).  However, like the error says, python doesn't support subtraction between lists.  However, when we convert both L1 and L2 to sets (S1 and S2 respectively), we can perform this operation.  To turn the resulting set back to a list, all we would have to do is enter the code list(S1-S2)instead of just S1-S2.  However since sets only contain unique collections, we may loose some information in operations such as the one above.  Consider the following code as continuation from the above:

In the result, we loose the information that L2 actually had two 3's in it, since S2 would only have the elements {1, 2, 3} (unique objects), so just be careful when using sets.
As a last thought, finding common values in sets can be done in the single line of code set(S1).intersection(set(S2)).


In recent weeks, we were also introduced to the idea of recursion using list comprehensions.  List comprehensions were actually covered quite awhile ago in CSC148, but they're quite simple so I'll just add a blurb about it here:

• The format of a list comprehension is: [expression for i in iterables]
• Where the expression is a function/method (ie sum(i), math.sqrt(i), str(i), etc)
• 'iterables' refers to a list, dict, or tuples.
• List comprehensions do not modify the original iterable; they create a new iterable

So back to recursion; we were introduced to the process by a problem Danny posted - suppose we wanted to find the sum of all the numbers in a list.  This seemed really easy (and since we're all lazy efficient Pythonistas (and yes apparently that is actually a thing), we're going to use the builtin sum function).  However, what if some of the numbers in the list were also in another list?

Danny showed the solution to be the following piece of code (taken from the CSC148 W14 webpage):

*

The code checks if the item x in the list L is an instance of type list, then performs the builtin python sum function to that list.  If the item x in L isn't a list (the program assumes it's an int in this case), it adds the int to the sum.

Consider L = [1, 2, [3, 4, [5], 6], 7].  If it's passed through the above line, the first two elements of the list are added to the sum normally since it fails the isinstance(x, list)condition.  However, the third element in the list, [3, 4, [5], 6], passes that condition.  So, the list is passed through the sum_list function which is called from within itself, so that the individual integers can be added to the sum.  This can be done in however many layers there are sub lists.  

In my head, I liken this recursiveness to using the chain rule in differentiation. Consider the following:

If we were to differentiate the above function, we'd have to 'peel the onion' per say.  f(x) is made up of 3 composite functions in the form of g(h(s(x))).  Like the above example with list L, we have to peel away the layers of f(x) until we're left with just the variable x (int values in the sum_list function).  Lets try to run f(x) through the following pseudo code:

First, f(x) is put through the isinstance(x, composite_function)expression which returns True, so the 'outer layer', in this case the 2sin() is differentiated and added to a product of the differentiated layers.  This keeps occurring until all the layers have been differentiated until we reach the 'bare' variable x. (Note: For anyone taking MAT135 or any other math course, don't even try to use this to do your problem sets. You will fail. Epically.) 

Even though we've only been introduced to recursion it already feels decently complicated, but I figure it's only going to get more confusing from here on out with more complex implementation and/or problems to solve with it.  Good luck, future me.

Another topic of discussion in the past couple of weeks was how to handle exceptions in python.  The code for it is actually really simple.  Consider the following code:

Which may return an output that looks like this if an error is raised:

All in all, exceptions might be the easiest concept/thing to implement I've learned in python in a long while.


The last broad concept we learned was inheritance in classes, ie subclasses, which is a pretty simple concept with similarly simple implementation (for now).  

When we create a new Class, we can create a Subclass that inherits all the attributes of its Parent Class, which we can edit if we wish to in the subclass without affecting the parent class.  To do this, we use class NewSubClass(ParentClass).  I've actually used a subclass in this slog entry previously; aren't I forward thinking haha no.  In the class derpyError, I used Exception as the argument, which actually made derpyError a subclass of the parent class Exception.

So there was nothing completely brain shattering this week, but I'm starting to see more complicated expansions of the above concepts emerging in the horizon, like always, we'll have to see.

Week 3 - Object Oriented Programing (OOP)

For the past three weeks of the course, we've been focusing on OOP, more specifically creating classes and writing methods for them.  Even though we did briefly cover classes in CSC108, they were explained with much more detail in CSC148  In addition to this I think that revisiting the concept the concept after a break helped me understand it better.

One new concept that was introduced from the very start of 148 was the idea of creating classes and methods from a paragraph of plain English, instead of being instructed to 'create the class ____ with the following methods...etc'.  Even though this practise seemed quite easy during lecture it became more difficult during the labs where the class names were based on non-nouns.

For my own future reference, lets dive into what was taught about OOP:

First of all, what is an object? Essentially an object is any sort of entity having an identity, type, and value (which may include some number of attributes).  OOP is centred around the fact that programmers can create/define classes of objects so that any object of that class is characterized by a defined set of attributes.

To help me explain better, consider this piece of code for the class Point:

The __init__ method is a special method that creates/initializes the class when you create it.  The first argument of the __init__ method is always self (it could be some other random name, since it would still serve the same function, but the programming community would probably have you hanged deeply frown at you for doing so).  Self is the argument of the class that refers to itself.  For example, consider the __str__ method.  The method is supposed to return the 'point' in the notation that we usually see in math class:

Notice that the method __str__ only takes the argument self'; this is because the __str__ method 'is applied' to only the object itself.

The class Point has two instance variables (variables that are defined inside a method and only belong to one instance of a class), x, and y.  These two class variables can also be used in any method created within the class.  The lines self.x = x and self.y = y simply say that each object of the class Point has a property x and a property y which are defined as the first and second variables when an instance of the class is created in the shell (ex: p = Point(2,3) where x = 2 and y = 3)

In the second week of class, we were also briefly introduced to Abstract Data Types (ADTs), some of which (lists and dicts) we were already quite familiar with.  We were introduced to the class of Stack.  Stacks are essentially the same as lists, however the user can only access/manipulate the most recently added item.

OOP adds a lot of flexibility to how we can manipulate objects in Python, and so far it isn't too mind blowing, however I'm apprehensive of applications of classes where I won't understand exactly what the class is supposed to be (ie how to start working on a problem).  However that issue heavily depends on the problem itself so I'll just have to wait and see.