CSC148 February 29th 2015 Writing Recursion

In this post, I will be writing about object-oriented programming as well as writing recursion, to make up for the blog post that i forgot to write during reading week.

Object-oriented programming is a term that i first heard of near the end of CSC108, as we began learning about writing our own classes.  At that time, my understanding of OOP is simply what my professor had taught me, a way of programming that focuses on objects.  I learned after doing some research that OOP is focused on objects rather than actions, and data rather than logic.  In this model, objects are well defined data structures that can be manipulated through methods, and objects can also interact with each other through methods.  Programs that are built on OOP are essentially objects that interact with one another though logical functions.  Python is a common type of OOP language, as are C++ and Java.

In Python, objects are defined by their class, which may be inherited from another class.  These classes may be modified versions of generic data structures such as lists, and in turn they may be modified into objects such as queues and stacks.  Classes not only represent objects through different data structures and attributes, but also include ways of how these objects can be manipulated.  For example, a class that represents a circle may have methods that adjusts the radius of the circle, as well as tell whether or not two circle objects are the same.  Classes can even represent complex objects such as chess, and different chess strategies.  With creativity, i believe a great deal of both real and abstract objects can be defined by Python classes.

Now onto recursive functions.  The focus of the last two weeks of 148 was the writing of recursive functions.  As i have mentioned in a previous post, the process of writing recursive function is really similar to induction to me.  First i have to find a base case, which in most recursive functions is the basic output on a simple object.  Then, the recursion will repeat a certain process over and over until it reaches the base cases, and then it will perform a boolean function on the base cases.  However, in the last lab, i practiced writing more complicated recursive functions that involved if statements.  Though i was able to figure out how to implement the 4 practice functions, i feel like i still havent grasped the intuition of recursion yet.

CSC148 February 9th 2015

The highlight of last week's CSC148 is the first midterm of this semester.  Having gone to Danny's lecture for 165 last semester, I had a pretty good idea of what I should be expecting, and i was very nervous before the test because truthfully i feel like i haven't learned a whole lot of new stuff since the beginning of this semester.  As i recall, the first 165 midterm was a simple, yet difficult test to me, and i didn't do particularly well on it either.  After reading over the lecture slides as well as the lab handouts multiple times, i felt like i had a good grasp of what will be tested, mainly writing classes and subclasses, and a bit of recursion tracing as well.  The test itself was surprisingly simple, and did not require much "smart" thinking.  Practice from assignment one on writing classes and subclasses certainly helped me feel at home as i worked through questions 1 and 3 on the test.  The recursion tracing bit was also pretty simple, as long as i took the time to write out the steps instead of being lazy and trying to cut corners.  However after writing the test, i realise that i misunderstood a method in the first question, which many cost me a fair bit of points.  The method that Professor Heap intended us to write was one which stores information passed in as arguments into an object attribute.  When i read the question, i thought that i was required to also prompt the user to give an answer as part of the method, and so my code was unnecessarily long.  The lesson that i have learned from this is to read each question description thoroughly, and never assume i know what i am asked to do and skip reading the latter part of the question.

CSC 148 February 1st 2015: Recursion

During this week's lecture, i learned about recursion: what it is, how it looks like in code, and how to trace and understand it.  When the professor opened with the example question of how we can add up integers in an arbitrarily nested list, i thought the solution would be using some sort of while loop, and that recursion was simply repeating the same action many times until the desired result is obtained.  However, instead of using loops, the solution to the problem was a function that calls itself in its body.  At first i thought, will this really work?  Wouldn't Professor Heap just get some sort of name error saying that the function name is undefined?  But it worked, and the idea of a function calling itself confused me to no end.  The only similar thing that i have seen was when Professor Heap introduced the idea of uncomputable problems using halt and naval gaze, and that example was a very confusing one already.  However, after working through some tracing exercise for the example function, i realized that tracing function calls on simple to complicated arguments really helped me understand how the function itself works.  For example, with the problem of finding the sum of integers in arbitrarily nested lists, i started with example calls on ints, then a single list, and then a list of depth 2, and so on, and i found that tracing recursion is much like expanding out a compact mathematical equation.  Starting with the function call on the argument, recursion causes the function to be called on each element of the iterable argument, and then on each element of those, and so on, similar to expanding functions such as (x-3)^3.

During the lab this week, i did some more tracing exercises, and i found that by tracing, i could more or less figure out the gist of a function, however i think that if i were to use tracing to figure out the purpose of a function, i need to come up with relevant examples, for example passing in strings to a function thats meant to work on ints and lists wont achieve much.  Just when i thought recursion was a pretty simple idea, i got stumped on the last exercise of the lab, which was to write the body of a recursive function.  At this point, i knew that i should include an if statement to essentially separate the arguments of the function into two types, one where object type that the function is intended to work on, and the other where basically every other object type is filtered.  The tricky part was implementing the recursion.  The function that i needed to write is supposed to find the maximum length of a list in the argument and return that number as an int.  I knew that i had to work with len() and max(), however i was stuck on which process i should repeat(with recursion).  I knew that i needed to find the length of every list in the argument, and somehow use the max() function to compare them to each other, but there are also other objects such as ints in the argument, and when trying to pass an int to len(), i get an error.  Furthermore, int isn't an iterable object, so i cannot use list comprehension to build new lists with len().  I tried to think about the very basics of this problem.  The recursive part will repeat that section of the code on every list in the argument, but how do i go deeper and look at each element of the list?  In the end i ran out of time before i had to complete my quizz.

At the end of the tutorial, i gave up and asked my T.A. on the possible solutions of this problem, and she showed me a much simpler and different method of implementing this function.  Instead of creating a list where each element is an int that represented the length of each list in the argument, i can simply use the max function to compare the length of the outmost list to the length of every list nested inside of it.  After thinking about it more at home, i finally came up the solution:

return max( [len(L)] + [length(x) for x in L])