Week 11 : Reflections on Recursion

In weeks 4 and 5 my posts were mainly on the topic of recursion and my immediate fascination with it. Since that time I have had a lot more first hand experience with recursion through the assignments and labs, and my fascination has not been broken. I have read in other students slogs that even though they may have previously learnt about the concept of recursion they did not learn how to trace recursive functions. This was the same for me, I knew what recursion was and how to use it by I found it really confusing at times, especially when trying to understand a recursive function I did not write. With the method of tracing recursive functions taught in this course, I find now with practice I can look at a recursive function and understand what it is doing just as easily as one that uses loops.

In Jesse’s slog on recursion he talked about his initial thoughts on recursion and how recursive functions end, being as I was, initially confused on the topic. I like how in this course it is taught to first think about a base cause that would not need recursion. Doing this in a way makes you think about how the function is going to end before you even start the recursive body of the function. I believe this method of writing recursive functions, makes it much easier to tackle a new recursive function, taking away most of the thoughts of “I don’t know how to start this”.

Week 10 : Impressions of Week 9

               

                In week 9 we did not learn much as we had our second term test on the Wednesday. On Monday we reviewed binary search trees for the test which I covered in my week 8 slog. I found the test to be very fair as it covered all of the big concepts we have learned since the last test. We had done a lot of class work on binary trees and binary search trees and this was reflected by the amount of question on the subject on the test. When studying for the test I mostly just reviewed the slides from each class we had after the first test, making sure I understood and knew all of the information, but my main focus was redoing all of the labs on the topics present on the test. I find this to be the best way to study as by completing the labs you show yourself that you understand each topic very well. I also find it helpful to sometimes write out my lab answers on paper as that is how it will be on the test.

Week 9 : Impressions of Week 8

               In week 8 we learnt about the data structure linked lists. Just like trees, linked lists are made up of nodes which point to other nodes but in linked lists each node can only point to one other node, this node is called the next node. The first and last nodes in a linked list are kept track of in the linked list class and are named the front and back nodes or sometimes the head and tail, as seen in the image below.

                 When I first tackled the linked list lab I found it a little confusing and I was unable to get the first function in the lab to work as intended. Since this type of mutable and iterative data structure was new to me I knew that before trying any of the functions I had to play around with the class and draw lots of picture until I felt that I had a firm understanding of linked lists. Sure enough after I had done this I was able to complete all of the functions/methods without problem.

Week 8 : Impressions of Week 7

               In week 7 we learnt about the data structure called Trees, and more specifically binary trees. Trees are a way to store data, we also learnt that different position in a tree have different names. In the image to the right you will see a binary tree, each circled value in the tree is called a node and the top node, 8 in the tree to the right, is called the root. Trees in computer science are upside down to trees you would find in nature, so the nodes at the bottom with no children (children are nodes extending from other nodes), are called leafs. Trees can have as many children as given to them but the special type of tree called a binary tree can only have two children.

                Since nodes in binary trees can only have two children they have special names, right and left. There is also a special type of binary tree called a binary search tree, the tree mentioned earlier is actually a binary search tree. In binary search trees data in the left subtree of a node is less than the data in the node and data in the right subtree is greater than the data in the node. While learning about binary trees we also learnt about binary tree traversals.

                There are three ways we learnt to travers a binary tree, inorder, preorder and postorder. When traversing inorder you visit the left most unvisited tree, then the node itself then the right tree, always repeating this algorithm recursively, I remembered this by remembering the order of three letters, L, N, and R (LNR) L for left, N for node and R for right. One thing that I noticed when traversing a binary search tree inorder is that you visit the data in the tree in sorted order from least to greatest. When traversing the tree in preorder you first visit the node then the left node then the right node repeating this recursively with each node visited (NLR). With post order you first visit the leftmost node then the right node then the node itself, always repeating this algorithm with each node visited (LRN). The way I remember the algorithms is with the letter orders I have been putting in parentheses. The algorithm for inorder is LNR (left node, the parent node, right node) and I remember this because each combination has L before R and with inorder the ‘N’ is in-between ‘L’ and ‘R’. I remember preorder as the ‘N’ is before (pre) the L and R so NLR. I remember postorder as the ‘N’ is after (post) the L and R so LRN.  

Week 7 : Object-Oriented Programming

                Last time I posted about what we had learned about object-oriented programming up until that point, and I had stated that I found inheritance to be a very interesting and powerful. This power was very well shown in assignment 2 where we were able to wright game strategies that would work for multiple games (subtract square and tippy in this case), without any game specific code. Along with the power that comes with object-oriented programming in python, there may arise confusion on how to make inheritance work in the way you want it to.

                I find that the best way to overcome these confusions is to play around with the things that are confusing you until you have a thorough understanding of what is happening. The best way to do this is to create a very simple class and then make another class be a subclass of that class and then slowly add and test things so build your understanding. As an example I was confused about how to changes methods in the subclass but still retain the basic aspects of that method in the subclass, through this experimentation process I quickly found I could just use the original mothed in the new one (by using something like this SuperClass.methond()).