Week 7: My Summary of Recursion

As I mentioned in my recursion-tracing slog, the act of tracing recursive methods was quite simple. However, like anything else in CSC165 during the first semester and in this class, the first step to writing my own recursive function was quite difficult and I had no idea what the instructor was talking about. I sat down to really crack down on this problem. I first really read through the slides and examples that we went over in class and in the lab and tried to look for patterns. Functions are said to be recursive if they call themselves within their implementation to create repeating calls. Although the same process could be represented iteratively (i.e. with for and while loops), the instructor told us that for some problems, recursive functions are more concise and elegant, while loops can get long and complex pretty quickly.

The general pattern for more recursive functions is that they have two cases (sometimes three). The first case is known as the “base case”. This is for when even though the function might be recursive, the object might be simple enough to not require recursion. An if… expression is needed to check for that case. For a case that might be more complicated to deal with than the base case, an else… expression must be used. Ideally, this expression would reduce all the elements of the argument to the base case by iterating them through each element and calling on the same function (i.e. itself); hence, recursion. This is better explained using an example. Imagine if you want to find the number of all the elements in the list L = [1, 2, [3, 4], 5] with function element_amount(L). For a list, the base case would be a single integer element (e.g. 1) or just have the if statement check if it is not a list. It would return 1 because there is only one number. The more complex case would be invoked if the function was called on the list. Inside the else statement, we would have something like “sum([element_amount(x) for x in L])”. We’re breaking L into each element and putting them each into the element_amount function. This is with the hopes of inducing a base case for all of the elements, the sum of which will yield the number of elements in L.

To sum up, recursion is a way of finding solutions to a problem by breaking it down into smaller parts first and build up to a final solution with solutions of the smaller parts. What distinguishes this problem-solving method from the iterative way of problem-solving is that recursive functions are allowed to call themselves within their implementation. To succeed in implementing recursion, one must remember to break down the function into two cases: the first case being the base case that deals with a problem simple enough to yield a solution without requiring further recursion and the general case being the more complex case where the recursion call needs to take place. Recursion is a great way to solve problems because it makes the problem cleaner and breaks them down into more manageable means, which always leads to less headaches and working solutions!

Week 6: My Summary of Object-Oriented Programming Concepts

           The majority of the semester, except for this week and last week when we first dipped our toes with recursion, consisted of learning exactly what object-oriented programming is. If I were a betting man I would say that the expectation of this course is that we are able to fully understand and be able to explain what object-oriented programming, or “OOP” for short, is. Here is my best shot at it.

           The name of it is pretty self-explanatory. OOP is a type of programming process that revolves around devising procedures using objects as the information to solve real-life problems. Whenever the instructor threw around big words such as “Abstract Data Types” or “methods”, I reminded myself of the actual “Object-Oriented” part of the OOP name. What are objects? They are basically chunks of data you can store, manipulate, and extract. They can be Python built-in data types, such as integers, strings, and Boolean values, or you could even make your own. These are called Abstract Data Types, or “ADTs” for short. These store the intended meaning of the data it stores and what to do with them. Each ADT is organized as a “class”, which contains and neatly organizes “methods”. These are functions that can either report some property of the object the class represents, or mutate it. This all seemed super complicated to me at first because just the terms and concepts seemed super abstract. I fixed this by diving into analyzing examples, which the instructor was more than generous about. One of the examples was a Point object. A “Point” has coordinates, which has to be initialized first (I will explain later how that works). We also want its distance from the origin. A class would provide these services, both initializing the coordinates and returning its distance from the origin, through the methods that it houses. Not so hard to understand anymore, eh? Of course, we can get into much more detail with __eq__ and ___repr__ special methods and how to call upon the methods to use their services but the fundamental idea is that the classes and methods all revolve around how to perform operations with and/or on the main object that they were created to do, hence OOP.

           Inheritance, though, is a concept worth mentioning and the explanation of OOP would not be complete without it. Sometimes, we have an object that is kind of like one thing but is more specific. For example, a square and a triangle are shapes but they are more specific in that they are specific shapes. They share general attributes but determining them might require operations specific to their needs. The solution here is to create a parent class Shape and still implement methods. Then we can call Square and Triangle “subclasses”, which means that they inherit the methods but when we program the subclasses, we can override the inherited methods and add new methods that are only for that subclass. The endgame is that programmers are able to fully customize each class while doing minimal work if possible. Sounds like a perfect deal to me.

           Hopefully my explanation of OOP was clear enough for my classmates to understand. I know this stuff will come up on the final exam so I definitely look forward to coming back to this entry to review OOP concepts. I feel I can do quite a few things with this knowledge. As a matter of fact, my group (with Lukas and Jovan) did quite well in the first assignment, which dealt with practicing OOP so I think I’m set. I now look forward to more recursion to add to my toolbox along with OOP.

Week 5: My Impressions of Tracing Recursion from Week 4

           Boy, was I worried about recursion! My second-year friends and guys who I know took this course last semester built up quite the hype for me. The way I understand recursive functions is that it is a repeated application of a function within that same particular function. What I initially thought was why not just use for and while loops in the function when executing repeating operations. Well, I do know from learning about running time and efficiency in CSC165 that loops have n^2 running time, hence are not the most efficient way to go. My conjecture is that recursive functions are used because they are more efficient since I believe they are only n running time.

           Week 4 mainly just consisted of becoming introduced to the idea of recursion and being familiar with tracing them. It was not unlike the back in 108 when we were asked to determine the output of a function except obviously the difficulty did escalate with examples in this course. The functions primarily dealt with determining sums of the elements in the lists and the depth of some nested lists. The level of difficulty for me depended on what the functions were asking me to do. The functions determining sums of the elements were straight forward but for some reason and I can’t quite put a finger on it, but determining the depth of nested lists felt awkward. However, all in all, I felt that as long I read the code carefully both at first and every time I used the function, I could produce results that were accurate to the specifications of the functions. The instructor took it slow with the first tracing example, holding our hands through each operation in the function. That instilled in me the need to take things slow and be vigilant with each step. However, I realized last week in the lab that taking extremes with that will result in unnecessary tedium. The challenge for me now is to find that balance between being too tedious and being careless and rash when tracing recursion.

           If anything is the calm before the storm, this is it. Although tracing was not difficult, I am sure building recursive functions will be. I tried it by myself with the lab exercise and I struggled with it. Hopefully in the coming weeks the instructor shows us the methods and even some tricks to master creating recursive functions. I can’t wait!