Week 7 of CSC148: Recursion

I can't believe we are already 7 weeks into this semester, and week 7, known to many students as Reading Week, is where I focus on the topic of recursion. I've touched on recursion before, it would have been difficult to avoid it since it was a big part of assignment 1, and one of the larger overall topics of the course so far.

Put simply, recursion occurs in computer science when defining a function that calls itself somewhere in its own function definition. A function with this characteristic is aptly referred to as a recursive function. The goal of doing this is breaking a seemingly large, possibly even infinite task into its most basic steps. A good way of understanding how recursion approaches a problem is to contrast it with a style of programming we became familiar with in CSC108, iteration. A simple example of an iterative function would be a function that continues appending to a list while a condition is not met. Both iteration and recursion try to break problems down into smaller tasks, but as far as my understanding goes, iterative functions tend to explicitly declare when it has reached a specific end while recursive functions seem to be more focused on breaking down the problem into its most simple form--referred to as the base case. The base case is the true core of a recursive function in that calling a recursive function on the base case will always lead directly to the return statement. If a more complicated case is called into the recursive function, the goal is to break it down into the base case in as many steps as is required. This 'breaking down' occurs by checking if the base case if fulfilled, if it isn't, the input is modified in some way and the function is called again until either the base case has been reached or the input has been simplified so it is one step closer to it.

As an example of a recursive function, here is one from one of the labs on recursion that my lab partner Brian (check out his entry on recursion right here) and I wrote:

def find_num(SL: 'SearchList', n: int) -> bool:
    """
    Return True if n is in SL, otherwise False.
    """
    if n == SL[0]:
        return n == SL[0]
    elif n < SL[0] and SL[1]:
        return find_num(SL[1], n)
    elif n > SL[0] and SL[2]:
        return find_num(SL[2], n)
    else:
        return False

The point of this function is to recursively search a SearchList, an ADT we learned about in the lab. A SearchList has some interesting characteristics. First, a SearchList is either None or a python list of three elements. Element 0 is always an integer, element 1 is either a None or a SearchList containing integers smaller than element 0, and element 2 is either None or a SearchList containing integers larger than element 0. For example, a SearchList can look like this: [5, [2, [1, None, None], [3, None, None]], [6, None, None]].

Using these specific characteristics, the previous function was written to recursively scan a SearchList for a given integer n. The first if statement checks for the base case, which is the situation where the first element is the element we are looking for. This is a requirement for any recursive function, and is a good way of displaying how a function defines the simplest possible task. For example, calling find_num(SL, 9) on a SearchList defined as [9, None, None] would evaluate to True without calling itself again. An example of a more complex case is the SearchList [8, [2, None, None], None]. It is immediately apparent that this is not the base case since there is a nested SearchList as element two. When find_num is called on this SearchList for n = 2, the base case is checked and will evaluate to false. Next, elif n < SL[0] and SL[1] will be evaluated. n is less than SL[0], which is 8, and SL[1] will evaluate to True since it is not None, meaning there exists a nested SearchList for the function to check for the intended value. This is where recursion happens, inside this elif statement the function calls itself, this time with the nested SearchList in the parameter (this is indexed so it is always re-evaluated). In this second level, the function will once again check for the base case, and this time it will return True. This return will be carried up to the 'first level' of the function and will end the function call.

This might not be the simplest possible example but I believe it effectively shows every key feature of a recursive function: the check for the base case, the return statement(s) for when the function has or has not reached a base case, the function calling itself with a modified parameter, etc. Regardless of how many nested SearchLists there are, this function will continue to call itself until a base case has been found, no matter how 'deep' it must go. A lot of power in a relatively simple function like this seems to be recursions biggest strength and whenever a problem can be broken down into the same series of steps it is definitely a viable option.

Week 6 of CSC148: Assignment 1 pt. 2 and Trees

Last week I had ended my post off before I tackled the recursive bits of assignment 1. I correctly predicted it would be the hardest part of the assignment but in hindsight (like everything) it seems easy. As they say, hindsight is 20/20. Once I had figured out how to translate the mathematical equation for the minimum number of moves of a four stool version of the Tower of Hanoi into Python code, which wasn't too bad after Danny had offered some guidance in one of his lectures, I ran into a wall when it came to return the 'i' value that corresponded to each 'n' value, 'n' being the number of disks--or in this cases cheeses--in the game. I solved this by putting my recursive function inside another function so the tuples I was appending too weren't being wiped every time the function recursed. Looking back I could have used another tool recently brought up in class: namespaces, or more specifically, defining the scope of the list I was using to store the tuples outside of the function (i.e. global perhaps). When all of this was said and done, creating the recursive function to actually move the four cheeses was a breeze, once again due to the guidance offered by Danny and the TAs over Piazza. Overall, the assignment went great.

The latest concept to have come up in class was the use of tree structures to help visualize recursion. The 'paths' from node to node and the ideas of parent and children nodes all stemming from a root definitely redefined how I view recursion. I could see immediately why we were being taught this concept, it seems intuitive to me almost immediately. Understanding the code and the tree ADT as a whole is the next step for me right now in understanding the CSC148 course material, particularly now that my midterm studying is about to begin.

Week 5 of CSC148: Assignment 1 and Exceptions

I'm getting close to the end of assignment one, which incidentally is where it gets very challenging. The TOAHModel and ConsoleController modules weren't too hard to complete, in fact it was easy enough to have a little fun while doing it. I went a little further than required with ConsoleController and added a function that checks if the user has won the game, rather than make it an entirely manual experience. I did this so there is some redeeming quality to playing around with the TOAH game in the console while I figure out how to complete the hardest step, number five. This is where recursion pops up in the assignment, and from what I have glanced over and heard about in class it is no easy form of recursion. The assignment handout gives us a nice recursive formula to guide is in the right direction (picking the value of i that results in the least number of moves to complete a four stool version of the game). I imagine I must implement the code given to us in class for the three stool version of the game at some point.

One of the best things we have learnt so far in my opinion is how exceptions are raised and can subsequently be handled. No more annoying exceptions popping up left and right when we don't want them to! I used a couple of try/except statements in the assignment so far and it's made my life a lot easier. Not only can I stop specific (or general) exceptions from showing up, but I can totally change what happens when a specific one is raised. This is definitely something I will use a lot in my programming.

Now time to try and tackle that recursive formula for assignment one...

Week 4 of CSC148: Exercise 2, Recursion and Turtles

A lot of concepts were covered this week. Exercise 2 was basically testing us on if we understand inheritance and how Python errors operate. These ideas were linked through object creations, since custom errors are defined in classes, classes being where the ideas of inheritance apply. After doing some reading I found the assignment quite simple and straight-forward. My biggest issue right now is perfecting my style. I'm still finding myself checking style guides frequently to make sure I've got the right amount of spaces somewhere or making sure I've written the type contract out properly. Descriptions are a bit of an annoyance right now, as well.

As far as recursion goes, on a conceptual level it doesn't seem too hard to wrap my head around. On the surface it's quite simple--a function that calls itself within its own function definition. The examples used so far on lists have been quite well explained by Danny, where we've been shown how to sum all the numbers in a list that contains sub-lists. I'm looking forward to starting the first assignment shortly so I can play around with recursion first-hand. Same goes for list comprehensions (or any comprehensions, really), I'd like to get in the habit of using those more often. The fractals Danny was creating with recursive functions and the Turtle module were quite interesting. I am a visual learner and those examples really helped make recursion "click" for me.

The labs this week were straight-forward but a little frustrating. Everything went smoothly except for the testing parts of lab. This is probably my biggest weakness right now, using unittest efficiently.

Week 3 of CSC148: My Experience with Object-Oriented Programming

Welcome to my courSe bLOG, appropriately referred to as a SLOG. Here, I will focus on both general and perhaps not-so-general subjects I happen to feel like writing about throughout the course of the 12 weeks that make up CSC148. As a hopeful computer science major, CSC148 is the keystone of my first year of studies for both personal and academic reasons. I'm excited to finally apply some of that Python programming I was taught in CSC108 to new areas. In many ways, the first 3 weeks of CSC148 have been quite refreshing. It seems like rather than learn complex new ideas that make our lives more difficult, the concepts we are learning are meant to make our lives easier. I only realize now how much of what we learnt in CSC108 was the long way, or in some cases, the incorrect way of doing many things. I'm looking forward to applying many of these concepts, familiarizing myself with them, and applying them in my Python programming! One thing that has helped with this so far is the lab time, where we are forced to discuss and implement these ideas. On the subject of labs, if you are looking for another perspective on CSC148 check out my lab partner Brian's blog here.

For this first post on my SLOG, the focus will be on object-oriented programming (OOP). Talking about OOP is interesting for a variety of reasons. When I've been asked to explain the positives and negatives of something, or just describe it in general, I'm used to understanding how that thing fits into the overall scheme of things. With the case of OOP, this is not the situation. OOP is the only style of programming I am familiar with, since Python, an OOP language is the only real programming language I have learnt. Based on this fact alone though, it seems like OOP is quite dominant in the field of programming languages, with Python, Java, C++, Ruby, PHP and many more very popular and widely-adopted languages falling into this category of "object-oriented". The easiest way to approach a description of OOP is to describe the concept of an "object"--the central focus of OOP. Well, an object in programming is much like an object in real life. A real-life object has attributes (known in the programming speak as data fields) and they have sometimes have a function (known as a method). Take a fork for example, it has attributes like its weight, its shape (probably the most important attribute), etc. It also has a purpose, its method, which is to aid the user eat their food. These objects, sometimes referred to as types, form the basis of an OOP language like Python, where classes are used to define an object.

Object-oriented programming seeks to lessen the semantic gap between the programmer and the user. This means it aims to reduce the number of differences between the structure of a typical users natural language and the programming language itself. This is done to serve the three main goals of OOP (from Wikipedia):

• Increased understanding.
• Ease of maintenance.
• Ease of evolution.

Increased understanding of code is always important because it will serve to reduce the number of errors, and increase the efficiency and speed of the coding itself. Especially when the same code is being worked on by a large number of people. Easier maintenance follows the same logic. Ease of evolution is also a very important goal of OOP. Since code often exists out in the world for a long period of time, it has to withstand changes in technology, changes in the people that work on it, and even changes in the way the programming language itself is used. Using objects, things that are fundamentally easier to understood is the best way of maximizing all of these goals.