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...