Basically, recursion is a programming strategy in which a particular problem is broken down into smaller sub-problems until the simplest possible solution is reached. There are three necessary components for a recursive problem to work; these include:
1) A base case. This is the simplest case possible to encounter in a recursive problem.
2) A recursive case. This is where the function calls itself.
3) A recursive case must be such that each call reduces the size of the problem, getting closer to the base case each time.
In programming, recursion can be achieved by having a function repeatedly call itself on an input - provided that each call reduces the size of the input itself. For example, say one wanted to calculate the product of two numbers, x=2 and y=3, without a multiplication sign. To approach the problem, we recall that xy is the same as adding the value x to itself y times. In other words, 2 x 3 is the same as 2 + 2 + 2.
Now, we write the recursive code (using the logic we have in the first paragraph), by analyzing the three points of recursion. In this case, the base case would be when y = 1; in other words we would return x. When y is greater than 1, we have the recursive case: we would want to add x to itself each time, while y decreased. The final code snippet for such would be:
def multiply(x, y):
if y == 1:
return x
else:
return x + multiply(x, y-1)
The result is that, as each iteration goes on, x would be added to itself until y reaches 1 in the recursive call; but by that time we would have added x y times, and that would be the final solution.
Recursion is an important tool, sometimes even easier to implement than the traditional iterative method, especially when we look at complex data structures such as binary trees, when we discover that the only way to traverse (or travel downwards) through a tree is by recursive calls on each node.
Ah, I have a lot of fond memories about recursion. In high school recursion was the one object that scared the heck out of my entire computer science class (save for a few people, Kashish and Ipsita) because they just simply could not understand the recursive process behind it. When we were first introduced to it in class, my teacher simply threw us into the formulation of a recursive problem - which was not helpful in any way, as he, despite being a great teacher and all, didn't really explain that well as to why the recursive process work. By the time the assignment for recursion had rolled in we were stumped (including me) and some people took the desperate measure of plagiarizing their work as a whole. Recursion was a problem.
Enter university, and the world of CSC148, where I was told that half of my code would have to be recursive. I had some fears about repeating the same frustration I had in high school with such a subject - until I met Danny Heap. After starting off the session with a lecture on tracing recursion, it soon dawned on me that the key to understanding recursion was code tracing; to understand how recursion worked in code, we needed to resolve the code ourselves as if we were the computer doing the problem. It makes sense; if we just tried to step into a recursive problem without understanding how a computer works on recursion, then we would end up in a deeper, more frustrating hole than we would have initially.
During the reading week, in preparation for assignment 2, I took it upon myself to do a couple of traditional recursion problems on my own, such as the factorial, palindrome, and math problems. For each problem, I would ask myself questions such as: "What is the base case?" "How would recursion work on each element of the problem?" "How can we reach the base case?" When I made a recursive call, before evaluating it I would trace the problem on my own to see whether the desired result would be achieved. Understanding how to trace recursion problems was the gold in the mine that helped me to comprehend recursive code solutions in class, labs, and in my personal coding endeavors.
Alas, thank you, Danny Heap, for making me a witness to the glories of writing recursive code.
Thursday, 26 February 2015
Saturday, 21 February 2015
Object-Oriented Programming (Week 5)
Object-oriented programming is, in my opinion, one of the most fundamental concepts to grasp in the field of computer programming. As starters, our only encounter with designing programs was by taking input, processing the data and output - all in one 'main' file. If we were to continue down this path, then large programs would become unnecessarily difficult, and rather disorganized, as the logic becomes more complicated. The question is: how does object-oriented programming play out in simplifying large projects?
First, we should take a look at object-oriented programming itself. At the core of object-oriented programming is the designing of classes - or rather, blueprints of objects. When we design a class, we should take into account what we are trying to emulate with this class, what data can we associate with it and what can such an implementation of this be used for. When we create an object in code, that is to say that we are merely declaring an instance of a class to be made. For example, we can have a class named Human that contains data about age, weight, name, height, and methods to emulate the person's speaking, walking, and interaction with other humans. When we create an instance of a Human, a Human object springs to life with its own set of data, and behaviors.
Another thing that can be used in object-oriented programming is the idea of inheritance. Say you have an Animal class, that has a method speak(). But what if you wanted that Animal to contain data specifically for one animal? Sure, you could reuse the same Animal code and rename it, but that would be tedious, no? This is where inheritance comes in; rather than do the above, you can have another class take in data and methods from another existing class, and modify/add to those features to make them specific for one group only.
Ultimately, how does object-oriented programming play out in designing needlessly large, complex programs? This is how I saw it. When I was a beginner in programming, I struggled with object-oriented programming and I told myself, "If I wanna design a large project I can just use the main interface and nothing else. Granted, while some early projects were successful (I made a Deal or No Deal game without the use of classes), the end result was confusing and all over the place.
However, I later encountered a Java beginner's book which helped me to realize that "object-oriented programming is much like designing the necessary components of a particular something (be it a car, slot machine or animal) and personalizing it with actions and values that pertain to it." It was rather helpful and it solidified my overall understanding of OOP as a whole, and I would never have any difficulty with the concepts again. Once I mastered object oriented programming, I decided to improve my Deal or No Deal game by representing each aspect of the game as its own object, and put those together to make a functional Deal or No Deal game. The end result: the code was more organized, more readable and professional than the previous cluster I had.
Thus, to answer my own question, object-oriented programming is useful for designing large projects because it allows you to create objects for each individual aspect of the program, and combine them together to create an organized, functional solution. Without object-oriented programming, sure, we can make large projects in one shot, but the result would be tedious and clustered / difficult to fix. Can you imagine trying to make a bank system without any objects? I wouldn't; in the end I wouldn't even be able to understand my own code, let alone others because the code would be all over the place.
First, we should take a look at object-oriented programming itself. At the core of object-oriented programming is the designing of classes - or rather, blueprints of objects. When we design a class, we should take into account what we are trying to emulate with this class, what data can we associate with it and what can such an implementation of this be used for. When we create an object in code, that is to say that we are merely declaring an instance of a class to be made. For example, we can have a class named Human that contains data about age, weight, name, height, and methods to emulate the person's speaking, walking, and interaction with other humans. When we create an instance of a Human, a Human object springs to life with its own set of data, and behaviors.
Another thing that can be used in object-oriented programming is the idea of inheritance. Say you have an Animal class, that has a method speak(). But what if you wanted that Animal to contain data specifically for one animal? Sure, you could reuse the same Animal code and rename it, but that would be tedious, no? This is where inheritance comes in; rather than do the above, you can have another class take in data and methods from another existing class, and modify/add to those features to make them specific for one group only.
Ultimately, how does object-oriented programming play out in designing needlessly large, complex programs? This is how I saw it. When I was a beginner in programming, I struggled with object-oriented programming and I told myself, "If I wanna design a large project I can just use the main interface and nothing else. Granted, while some early projects were successful (I made a Deal or No Deal game without the use of classes), the end result was confusing and all over the place.
However, I later encountered a Java beginner's book which helped me to realize that "object-oriented programming is much like designing the necessary components of a particular something (be it a car, slot machine or animal) and personalizing it with actions and values that pertain to it." It was rather helpful and it solidified my overall understanding of OOP as a whole, and I would never have any difficulty with the concepts again. Once I mastered object oriented programming, I decided to improve my Deal or No Deal game by representing each aspect of the game as its own object, and put those together to make a functional Deal or No Deal game. The end result: the code was more organized, more readable and professional than the previous cluster I had.
Thus, to answer my own question, object-oriented programming is useful for designing large projects because it allows you to create objects for each individual aspect of the program, and combine them together to create an organized, functional solution. Without object-oriented programming, sure, we can make large projects in one shot, but the result would be tedious and clustered / difficult to fix. Can you imagine trying to make a bank system without any objects? I wouldn't; in the end I wouldn't even be able to understand my own code, let alone others because the code would be all over the place.
Monday, 16 February 2015
Tracing Recursion (Week 4)
In high school, I remember the way we were introduced to recursion was through a comedic dictionary definition of recursion: "Recursion: See Recursion." XD
But now, in university, to get ourselves introduced to recursion, Danny Heap started off by introducing the idea behind recursion - which was to solve a problem by breaking the problem into smaller sets, and evaluating such from there on. It seemed a bit confusing at first, which was why Danny Heap showed us how recursion worked by tracing the steps involved in such.
Tracing recursion was not hard. In fact, the way they showed us this was 10 times easier than how they did in high school. I could remember in high school, none of my friends could understand the logic behind recursion, let alone 90% of my other classmates, because, despite my compsci teacher being great and all, we were just thrown into how to implement recursion without any background on how or why this worked. However, the way Danny Heap introduced us to recursive methods was clear, concise and, on top of all that, effective to grasp on your own. I had thought of recursion as a burden back in the past, but after Danny Heap's examples and ways of going around it I had never felt so excited about learning recursion before.
Granted, the recursion examples were simplistic, as we mostly performed recursion to do simple things such as getting the length of a list (with nested lists included), the sum of all elements in a list, and whatnot, yet the way they were explained to me was actually effective and well-performed. From what I understand, as we iterate through a series of elements, every time the recursive case was met, it would result in another method call on such an element until the base case was reached. From there, on each inner element the function would call itself until the base case was reached, where after that the recursion would settle itself, resulting in our final result. It was amazing, and I could confidently say that understanding the basics of recursion was one of the highlights of my week.
During our labs, we pretty much did the same thing again. The exercises were not that difficult, neither was the quiz; compared to the rest of the class I was able to finish my work early (after all, the work was not that much of a challenge) - maybe, after all this, recursion shouldn't be that bad after all, right? Only time will tell.
But now, in university, to get ourselves introduced to recursion, Danny Heap started off by introducing the idea behind recursion - which was to solve a problem by breaking the problem into smaller sets, and evaluating such from there on. It seemed a bit confusing at first, which was why Danny Heap showed us how recursion worked by tracing the steps involved in such.
Tracing recursion was not hard. In fact, the way they showed us this was 10 times easier than how they did in high school. I could remember in high school, none of my friends could understand the logic behind recursion, let alone 90% of my other classmates, because, despite my compsci teacher being great and all, we were just thrown into how to implement recursion without any background on how or why this worked. However, the way Danny Heap introduced us to recursive methods was clear, concise and, on top of all that, effective to grasp on your own. I had thought of recursion as a burden back in the past, but after Danny Heap's examples and ways of going around it I had never felt so excited about learning recursion before.
Granted, the recursion examples were simplistic, as we mostly performed recursion to do simple things such as getting the length of a list (with nested lists included), the sum of all elements in a list, and whatnot, yet the way they were explained to me was actually effective and well-performed. From what I understand, as we iterate through a series of elements, every time the recursive case was met, it would result in another method call on such an element until the base case was reached. From there, on each inner element the function would call itself until the base case was reached, where after that the recursion would settle itself, resulting in our final result. It was amazing, and I could confidently say that understanding the basics of recursion was one of the highlights of my week.
During our labs, we pretty much did the same thing again. The exercises were not that difficult, neither was the quiz; compared to the rest of the class I was able to finish my work early (after all, the work was not that much of a challenge) - maybe, after all this, recursion shouldn't be that bad after all, right? Only time will tell.
Thoughts On The First Few Weeks (Week 3)
The first few weeks of CSC148 went by with a blur, and quite frankly it wasn't all that difficult to understand. Our main topic was object oriented programming - mainly the basic idea behind OOP, how to implement it, and applications of such.
Object oriented programming was, as mentioned before, not too difficult to pick up and play with - probably because I had previous experience with such a topic. My first 'real' encounter with object-oriented programming was in Grade 10, when I self-taught myself Java, which, in all due respects, an object-oriented language. After a few lessons, the concept of object-oriented programming was no big deal and I immediately could understand the purpose of it all (whereas initially, using Python, I could not grasp the concept - and this was in Grade 9).
We started off by understanding what an object was in computer programming; simply put, a virtual instance of a real-world object. We covered ways to implement it - such as reading a description and manually picking out proper 'verbs' (which would be translated to methods) and 'data' (which would be translated to the object attributes) found in each object's description. For example, if we were given the description of a car below:
"A car can keep track of the amount of gas remaining, its total mileage, and number of passengers; furthermore we can use a car to drive n miles, add/remove passengers, or get a new paint job."
We could immediately say that the Car object would include data values for amount of gas remaining, total mileage, and passengers; its methods would be to drive, add/remove people and change color.
When it came to implementing the actual Python code, it was not too difficult; for the most part the code would consist of writing methods, variables and logical statements - things that we have, and should be familiar with from previous programming experience or CSC108. All in all, the first few weeks of CSC148 were simple enough to comprehend via oneself, or the lecturers/TAs in class.
Subscribe to:
Comments (Atom)