Hey there!
Today, I feel like I am a computer scientist! Today, you will read about recursion. Recursion? Again? Really? Yes, I know the recursion sections of some of my posts seem to be just rewrites of the other, but if you didn't notice, for every entry on recursion, I provide more information as I understand it more.
This will likely be the first and last entry going in-depth about this, as I can confidently tell you that I now understand how recursion works (wow, I must be awesome)! Alright, let's begin.
What is Recursion?
Recursion is when you call a function or a method inside itself (in simple terms). The purpose of this varies, from 'unwrapping' a nested list to perform functions on its elements. It's rather easy to analyse a recursive method or function, but occasionally difficult to come up with your own to solve a problem because it's counter-intuitive. If I told you to create a method that prints the string "spam", n amount of times, where n is some natural number, then you will probably use some sort of loop that involves n as a terminating condition. You will write something similar to the following:
However, this method can be written using recursion:
In the above example, we have completely avoided any loops without ruining the functionality. When you are working with larger-scaled data types (such as nested lists), you can in most cases significantly decrease the number of lines of code when iterating over them by using the above method. The above example is simplistic, so the change in the number of lines between the two examples is negligible.
Problems
Recursion does have its own set of problems. For example, it does take an ample amount of time to come up with recursive methods for seemingly large functions, and so, developers usually tend to avoid them. With recursion comes the RuntimeError due to incorrectly designed recursive methods. It is raised as a safeguard to prevent a stack overflow, preventing the Python interpreter from tracing a recursive call after a certain amount of times. You can change the amount of times of recursion tracing depth if you would like (the developers of Python assume that we are all smart and kind people), but note that if this safeguard was not there or prevented, then your program may cause a segmentation fault (accessing read-only memory illegally), meaning that your program will crash, and in extreme cases, your computer will too. In order to prevent this problem, I suggest that you create a robust method on paper and test it thoroughly. Make sure you understand how a function works in the first place before you attempt to remake it. Remember, it isn't necessary to make a function recursive. Stick to my motto: "Do not fix what isn't broken - unless the professor says so."
I'm glad that I understand recursion now, and I hope you also have an idea of what it is as well. I'll see you next week!
Bye for now!
Friday, February 28, 2014
Thursday, February 13, 2014
Week 6 - Tree Traversals, Recursion with the Tree ADT
Hi there! This week's post is going to be about traversing the tree data structure. When I think about the tree data structure, I think about a more detailed version how you may draw a tree as a young child, or a family tree diagram. You would start with a leaf and then put two 'branches' below it, with each branches containing another leaf that has two branches (it doesn't have to be just two branches, it can vary). In computer science, we say that a node (like a leaf in real life) is something that contains a value and possibly some labels pointing to its children (similar to a leaf having branches with other leaves attached to the end of them). The superseding node of a given node, if it exists, is known as the root, or the parent node. You can think of the tree ADT as a series of smaller sub-trees connected to each other such that there are no paths that form loops (or cycles).
There's a lot more terminology that I can go through, but I believe that it wouldn't be difficult to understand what I'm about to explain: the tree abstract data type (ADT). Every node in a tree has a cargo, which contains some sort of data, and labels or links to other nodes. Sometimes, other nodes can be the roots of other trees - nested trees. We've also learned about methods of traversing trees - pre-order and in-order traversal. When traversing a tree of integers to find a sum of all of them, we could use recursion by using 0 as the base case if there isn't a tree on the left or the right of any given tree node. For example, given a method called sum, and some TreeNode class that has instance variables, left, right and cargo; we can find the summation of all of the cargo given that the cargo of each node is some integer. We add sum(tree.left), sum(tree.right) with the tree's cargo given the base case that if the tree is None, we return 0. Whenever you are done traversing the tree completely on the left with sum(tree.left), you are left with '0 + 0 + tree.cargo' where tree.cargo is some integer. And you keep returning it to the recursive caller, so the effect is that you keep adding tree.cargo for every tree (interesting, right)?
I feel that we are now becoming more like computer scientists. I could only imagine that we are approaching searching algorithms to ADTs, such as depth-first search - this course will only become more interesting...
Until next time,
GR
There's a lot more terminology that I can go through, but I believe that it wouldn't be difficult to understand what I'm about to explain: the tree abstract data type (ADT). Every node in a tree has a cargo, which contains some sort of data, and labels or links to other nodes. Sometimes, other nodes can be the roots of other trees - nested trees. We've also learned about methods of traversing trees - pre-order and in-order traversal. When traversing a tree of integers to find a sum of all of them, we could use recursion by using 0 as the base case if there isn't a tree on the left or the right of any given tree node. For example, given a method called sum, and some TreeNode class that has instance variables, left, right and cargo; we can find the summation of all of the cargo given that the cargo of each node is some integer. We add sum(tree.left), sum(tree.right) with the tree's cargo given the base case that if the tree is None, we return 0. Whenever you are done traversing the tree completely on the left with sum(tree.left), you are left with '0 + 0 + tree.cargo' where tree.cargo is some integer. And you keep returning it to the recursive caller, so the effect is that you keep adding tree.cargo for every tree (interesting, right)?
I feel that we are now becoming more like computer scientists. I could only imagine that we are approaching searching algorithms to ADTs, such as depth-first search - this course will only become more interesting...
Until next time,
GR
Thursday, February 6, 2014
Week 5 - Recursion Continued, Namespaces, Scopes, and Unit Testing
Hey there! I do have some good news for those who might care about my life: I have a rather large assignment due next week and I've just barely started it, even though it was assigned a week ago - there goes the spare time that I don't have!
This week, we have learned about scopes and namespaces. Our lecturer has done this by placing 'spam' strings by changing the value of a variable called 'spam' via the different scopes, which are local, non-local, and global. Local variables are usually created and accessed within the first 'occurrence' of a method header and its return value. Non-local variables are usually created and accessed within a superclass or the top most method if there are nested methods. Global variables are usually defined outside a method and it's made accessible to all methods defined in a class or in a Python file. I find this quite easy to understand, and it's self explanatory if you have practiced with it enough.
We have went deeper into testing our modules. We were re-introduced to unittest (assuming most of us came from CSC108), except to much further detail. We were made aware that there is a module called 'doctest', and in this module, there is a function called 'testmod', which will test all methods'/functions' docstring examples to see if we get the expected results. Instead of always relying on docstring examples to help us, there is a unittest module that we could use to test out a class. In order to use it, we have to use the TestCase class found inside the unittest module. Once we inherit this class, we write methods that will load up an instance of a class, and then we write code for each and every method or function and we have to see if we get an expected result. This is done by making an assertion, otherwise known as the keyword in Python, 'assert'. An assertion takes in a boolean statement then raises an exception which implies that we haven't written some method correctly. This class is useful if you wish to analyze a method thoroughly, step-by-step, however I personally find in most cases, we write 'small' programs, so the 'doctest' module usually suffices.
We have also touched up on our first assignment, the Tower of Anne Hoi (similar to the Tower of Hanoi), where a person is expected to move cheese blocks sequentially from stand to stand until you form a 'tower' where the cheese blocks go from smallest to largest from top to bottom. It was mainly just to show us recursion techniques in the program, but I do find this assignment to be a bit intimidating, or rather simply time consuming.
This will wrap up my blogging for this week, hopefully I can get this assignment done, especially with exams coming up as well in the same week!
This week, we have learned about scopes and namespaces. Our lecturer has done this by placing 'spam' strings by changing the value of a variable called 'spam' via the different scopes, which are local, non-local, and global. Local variables are usually created and accessed within the first 'occurrence' of a method header and its return value. Non-local variables are usually created and accessed within a superclass or the top most method if there are nested methods. Global variables are usually defined outside a method and it's made accessible to all methods defined in a class or in a Python file. I find this quite easy to understand, and it's self explanatory if you have practiced with it enough.
We have went deeper into testing our modules. We were re-introduced to unittest (assuming most of us came from CSC108), except to much further detail. We were made aware that there is a module called 'doctest', and in this module, there is a function called 'testmod', which will test all methods'/functions' docstring examples to see if we get the expected results. Instead of always relying on docstring examples to help us, there is a unittest module that we could use to test out a class. In order to use it, we have to use the TestCase class found inside the unittest module. Once we inherit this class, we write methods that will load up an instance of a class, and then we write code for each and every method or function and we have to see if we get an expected result. This is done by making an assertion, otherwise known as the keyword in Python, 'assert'. An assertion takes in a boolean statement then raises an exception which implies that we haven't written some method correctly. This class is useful if you wish to analyze a method thoroughly, step-by-step, however I personally find in most cases, we write 'small' programs, so the 'doctest' module usually suffices.
We have also touched up on our first assignment, the Tower of Anne Hoi (similar to the Tower of Hanoi), where a person is expected to move cheese blocks sequentially from stand to stand until you form a 'tower' where the cheese blocks go from smallest to largest from top to bottom. It was mainly just to show us recursion techniques in the program, but I do find this assignment to be a bit intimidating, or rather simply time consuming.
This will wrap up my blogging for this week, hopefully I can get this assignment done, especially with exams coming up as well in the same week!
Week 4 - Recursion on nested lists, code/algorithm testing
Hey there! It's been a while since I've made a post, so here it is! I will feature a double post today to make up for last week (for last week and this week).
Week four has been a huge step up from week three, as now I feel as if the class is heading more towards the algorithm direction of computer science rather than software engineering.
When designing a method or a function, it's a good idea to test out your methods rigorously. From what I remember from CSC108, which is considered as an "optional" prerequisite course, we have learned the function design recipe, and from that 'recipe', it dictates that we should come up with examples after you come up with the method header and type contracts. I found this rather counter-intuitive at first, as I had previous experience programming prior to the start of my post-secondary education, so I usually become lazy and just go on ahead with the coding. That only led me to problems. However, the examples that were given in class weren't that difficult to follow, and I did find it to be 'common sense'. To thoroughly test a method, you would need to come up with what I like to call, counterexamples. In other words, you have to come up with some sort of parameter inputs where it can possibly break your method. I find this to be the hardest part of designing any method or function, as I usually get a hunch that my code is almost always 'broken' in some form.
The main topic of the lecture was recursion. In Week 3, we have just lightly touched up on it. This week, we have went deeper into it. Recalling previous experience from my high school days, I remember the topic of recursion as the most disliked concept in my computer science class. Recalling from my previous post, recursion in a nutshell is calling a method or function inside itself repeatedly until a desired value is achieved. I think that this is the most challenging concept to master. I imagine that Euclid's greatest common denominator recursive algorithm took him months just to come up with it - it's quite a bit of an exaggeration of course, but I hope you understand what I mean. Tracing recursive methods are not as bad as creating them. They're actually quite easy to follow, as you can simply use your understanding of Python to understand what's happening at every step.
Reading Flexy's SLOG for week 4 (link below), he or she says that most CSC148 students haven't encountered recursive functions prior to the start of the course. I do believe that this is almost irrelevant, as I am almost certain that people with experience for recursive functions still have trouble with creating their own. As my lecturer pointed out, most programmers actually do not use recursion - I imagine it's because of the difficulty of creating one.
I think this will wrap up my Week 4 thoughts.
Here's a link to Flexy's SLOG: http://flexographyslog.blogspot.ca/
Week four has been a huge step up from week three, as now I feel as if the class is heading more towards the algorithm direction of computer science rather than software engineering.
When designing a method or a function, it's a good idea to test out your methods rigorously. From what I remember from CSC108, which is considered as an "optional" prerequisite course, we have learned the function design recipe, and from that 'recipe', it dictates that we should come up with examples after you come up with the method header and type contracts. I found this rather counter-intuitive at first, as I had previous experience programming prior to the start of my post-secondary education, so I usually become lazy and just go on ahead with the coding. That only led me to problems. However, the examples that were given in class weren't that difficult to follow, and I did find it to be 'common sense'. To thoroughly test a method, you would need to come up with what I like to call, counterexamples. In other words, you have to come up with some sort of parameter inputs where it can possibly break your method. I find this to be the hardest part of designing any method or function, as I usually get a hunch that my code is almost always 'broken' in some form.
The main topic of the lecture was recursion. In Week 3, we have just lightly touched up on it. This week, we have went deeper into it. Recalling previous experience from my high school days, I remember the topic of recursion as the most disliked concept in my computer science class. Recalling from my previous post, recursion in a nutshell is calling a method or function inside itself repeatedly until a desired value is achieved. I think that this is the most challenging concept to master. I imagine that Euclid's greatest common denominator recursive algorithm took him months just to come up with it - it's quite a bit of an exaggeration of course, but I hope you understand what I mean. Tracing recursive methods are not as bad as creating them. They're actually quite easy to follow, as you can simply use your understanding of Python to understand what's happening at every step.
Reading Flexy's SLOG for week 4 (link below), he or she says that most CSC148 students haven't encountered recursive functions prior to the start of the course. I do believe that this is almost irrelevant, as I am almost certain that people with experience for recursive functions still have trouble with creating their own. As my lecturer pointed out, most programmers actually do not use recursion - I imagine it's because of the difficulty of creating one.
I think this will wrap up my Week 4 thoughts.
Here's a link to Flexy's SLOG: http://flexographyslog.blogspot.ca/
Subscribe to:
Posts (Atom)