Week 7: Getting back into the SLOG game

(Alternate title: Recursion is Recursion is Recursion II)

Note to TA: I would like this summary to be marked.

Reading Week went by extremely fast. Well, at least I was able to enjoy the comfort of my bed more often because I normally would have to be up at around 8am to get ready for school. With the due date of Assignment 2 (and assignments from other courses) looming, it's business as usual. We'll finish this assignment in due time, though.

How I feel at the moment

More concepts are being thrown at us week after week in CSC148. It's not at the same difficulty level as CSC108. That doesn't mean I can't look back at concepts from CSC108 (e.g. classes, Function Design Recipe) to help me understand what in the world is going on in CSC148 and, in particular, this assignment. Worksheets are being distributed each week for us to practice writing code on paper, much like CSC108. (Here's a personal action plan: I'm going to organize all my CSC148 worksheets in one place so I can look at them later. I have a bad habit of misplacing papers.)

Moving on then. In this post, I would like to summarize recursion with more detail this time.

To start this summary off, here's a dictionary definition of recursion:

It's used in linguistics too? Whoa!

In computer science, we solve complicated problems by creating methods to break down these problems into smaller problems. These methods are defined in terms of themselves. In other words, a recursive method is literally a "method within a method within a method..."

Circle of Life: Computer Science Edition

There are two easy steps to write recursive methods:

1. Identify the base case. This can be solved without recursion
2. Identify the general case. This is where the recursion takes place.

These steps somewhat remind me of proving by induction in MAT137. There, I would start with the base case, then move on to the induction step. In Python, this would take on the form of an if statement. Here's an example of a recursive function from one of the labs (with examples provided in the docstring) that contains an if statement:

def nested_concat(L):
    """ (list or str) -> str

    Return L if it's a str. Otherwise, if L is a possibly nested             list of str, return the concatenation of str elements of L. 
    
    >>> nested_concat('two')
    'two'
    >>> nested_concat(['one', 'two', 'three'])
    'onetwothree'
    """

    if isinstance(L, str): # base case; no recursion required
       return L
    else: # L is a possibly nested list of str
       return ''.join([nested_concat(x) for x in L])

In the Python shell, we would get the exact same results that we expected.

There's also a way to trace recursion on paper.

The first example involving a string, 'two', is very simple and will look like this:

nested_concat('two') --> 'two' # 'two' is a str

The second example requires some more steps:

nested_concat(['one', 'two', 'three']) --> ''.join([nested_concat(x) for x in ['one', 'two', 'three'])
--> ''.join(['one', 'two', 'three']) # traced nested_concat(str) before
--> 'onetwothree' # 'one' + 'two' + 'three'

This page, which was previously assigned as supplementary reading, can help others understand recursion and provides numerous examples, some of which involve graphics.

Jesse's post on recursion is a funny read, and he gets the point across. (That post also made me hungry.) Also, I really enjoyed reading Chris's insights on recursion. I liked his examples of recursion, and that has inspired me to create my own examples of recursive functions and other stuff to practice and get better at Python (because I'm still not very good at programming yet *cries*)!

I would like to wish the best of luck on A2! Also, feedback is greatly appreciated.

Thank you so much for reading! Cheers!

Week 6: OOPs, I did it again

Here's another glimpse of my not-so-fascinating programmer life: object-oriented programming and my familiarity with the whole shebang.

The term "object-oriented programming," or OOP for the acronym-inclined, is something that I have been familiar with since learning Java in my grade 11 computer science class. It's a key concept in computer science, with the main focus being objects, of course!

I revisited this concept last semester in CSC108 as well as at the beginning of CSC148 while reviewing classes. Prof. Heap asked us to do a complementary exercise that involved object-oriented programming.

With that, we all took out a sheet of paper and designed a class using the following approach:

1. Find the most important noun. This will be the class name.
2. Find the most important attributes of that noun (or less important nouns).
3. Find the operations for the noun to carry out (or verbs).

This approach can be considered linguistic, as we're dealing with nouns and verbs from a natural language (English) and putting it all together into a programming language (in our case, Python).

Here's a diagram for those who love looking at visuals (like me):

We had a few seconds to do it. I organized a sort of outline for this approach on my paper but was unable to identify the three parts in time. Eventually we took it up. (I would have liked a bit more time, personally, because I'm still not a proficient programmer yet and I'm a slowpoke.)

I'm familiar with Prof. Heap's teaching approach of having us complete exercises in a short period of time, but at the moment, it still would take me a while to solve these types of problems. When we take it up, however, I realize, "Of course. That's what is supposed to happen. Why didn't I think of that before?" To solve these types of problems within his given time frames (e.g. a minute), I'll do some review at home before coming to lecture. That's something I should have done in CSC165, but my course load was a bit too much for me to handle with five courses. Well, it's not too late, right? Then again, I have office hours to look forward to if I still don't get something. I will continue that approach so I can at least match my success in CSC165. (CS major, I'll see you soon.)

Anyway, I'll wrap this entry up by summarizing what I know about object-oriented programming.

We start with a class. A class is the most important object of any program. Using the approach that Prof. Heap provided, we start with #1, which is essentially the first line of our program. Here's a generalization:

class YourClassHere:
      """Your docstring goes here."""
      # to be continued...

At this point, our program is at a clean slate. Now, we want to implement steps #2 and #3 from our approach. How do we go about this? We need methods. Methods are functions defined within a class. Some important methods are: __init__, __eq__, __repr__, and __str__. We can also add our own methods, too.

Let's add on to our little generalization above.

class YourClassHere:
      """Your docstring for your class goes here."""

      # always start with __init__ to initialize your class!
      
      def method1(self, ...)
          """ (YourClassHere, ...) --> ...
           
          Your docstring for method1 goes here.
          """ 
          # body of method1
          # initialize variables, add loops, etc.

      def method2(self, ...)
          """ (YourClassHere, ...) --> ...

          Your docstring for method2 goes here.
          """
          # again, add body here
     
      # you get the idea

Another idea in object-oriented programming is inheritance. 

Here's the answer: Inheritance is the act of creating a subclass as an extension of the original class. The methods from the original are inherited onto the subclass. 

Let's inherit our class from above, YourClassHere.

class YourSubclassHere(YourClassHere)
      """Inherited from class YourClassHere..."""
      # inherit methods

In Assignment 1, we applied inheritance to our game_view program. We had general classes where the user could access the games made available to them, and specific classes for our game, "Subtract Square." Generally, inheritance is greatly applied when there is a general class and specific classes are needed as extensions.

The following diagram can add to our generalization of inheritance, too. The vehicle is the general class and the bike is the specific class (specific means of transportation that we are looking at). "Pedal," "trike," and "motor" are all subclasses inherited from the "bike" class. It's similar to the "Gameview" and "Subtract Square" classes from Assignment 1.

I think that sums up object-oriented programming. As well, this post also sums up object-oriented programming nicely, so feel free to check it out!

As always, feel free to leave a comment. I would love to hear any feedback from you.

Happy Reading Week, everyone! See you on the flip side!

Week 5: Recursion is recursion is recursion

....is recursion. Need I say more?

Last week, we constructed our knowledge on recursion. We looked at tracing recursion on nested lists. I found it to be like simple math.

How does this work? Well, let's say we have a list. Consider this list: [3, 5, 7, 9]. Now, we want to trace recursion on this list of ours. It's a list of four elements consisting of type int.

We can trace recursion in many different ways. One example that Professor Heap showed us in class is the sum_list function, which returns the sum of the elements if a list, L, or 1 if it's not a list. Here's what the function looks like in Python (complete with docstrings and all). I'll trace sum_list on our given list.

def sum_list(L):
    """ (list or int) -> int

    Return L if it's an int, or sum of the numbers in a possibly             nested list.
    
    >>> sum_list(34)
    34
    >>> sum_list([2, 7, 1])
    10
    >>> sum_list([2, 6, [3, 8, [5, 3]], 3)
    30
    """
    if isinstance(L, list): # isinstance checks whether L is list
       return sum([sum_list(x) for x in L)
    else: # L is an int
       return L

Going back to our list, [3, 5, 7, 9], we can trace it like so:

sum_list([3, 5, 7, 9]) --> sum([sum_list(x) for x in [3, 5, 7, 9]])
--> sum([sum_list(3), sum_list(5), sum_list(7), sum_list(9)])
--> sum([3, 5, 7, 9])
--> 24

Ta-da! We got the sum of all the elements in our list, which is 24. (Let's celebrate by drinking some hot chocolate.)

An even simpler call is on an int, say, 56. (You can even do this with crazy large numbers, like 243432423532523.) We'll just get 56 back because it's an int. But we can still trace this call (although it's literally just one line) like we did to the list above and add some comments:

sum_list(56) --> 56
# 56 is not a list
# as stated in our docstring, return 56

I had my test on Wednesday morning. It was only three questions. It wasn't terribly hard. (My MAT137 test was, though.) I'm hoping it went well. (Fingers crossed. I won't fret if I get a low mark, unlike what I did in CSC165 last semester. Haha! That is funny now.) The lab exercise on recursion wasn't as hard as the first two labs, either. The quiz followed suit. 

I'll also be adding blogs on my blogroll to your right, so you can read other people's SLOGs that I have garnered inspiration from.

Thank you for reading! Until next time!