Week 7: More Recursion

I think that the most important and most focused on concept of CSC148 has so far been recursion. This is a powerful way of approaching programming which I was not previously aware of. However, I think that recursion is an intuitive concept which everyone can grasp. In computer science specifically, recursion is when a function or method calls itself in order to achieve a task. Recursive functions generally have a base case which tell them what to do when a certain point in the execution has been reached and recursion is no longer necessary (as to prevent infinite recursion). A simple way of understanding recursion is to look at an visual example of it, such as the one I provided below. In very basic terms, something that is recursive contains itself within itself.

Recursion is so useful because of how flexible it allows code and functions to be. In the nested depth and sum list examples we worked on in class, the functions took the nesting depth and sum of the list, regardless of how many nested lists there were. Without recursion, these functions would only work for certain configurations of lists and nested lists. Some functions or formulas cannot exist without recursion, as seen in the first assignment, where the formula for the minimum amount of moves called itself, as well as in the function which solved a three stool Hannoi game. Recursion also saves time; writing a base case and a general case is much less time consuming than thinking of every possible input or combination. Trees and linked lists (as seen this week) are ADTs which are recursive, so certain methods written for these data types naturally involve recursion and cannot be properly used without it.

I now feel that I understand recursion fairly well. The term test written this week seemed to not be overwhelming for me, and I also started the second assignment, but am somewhat confused about how to approach it. The linked list examples that we went over in class made sense to me and I saw how they are recursive in nature.

Recursion explained through a demotivational poster.

http://img.photobucket.com/albums/v394/civilwarman/recursion.jpg

Week 6: Trees

This week we mainly discussed trees (an abstract data type) and designed methods to work with the trees and their data. The example we did in last weeks lab (with the SearchList) makes more sense; I found that seeing just the nested list representation of a tree was not as useful to me as a graphic or the __repr__ representation for a Tree object that we coded in class. A tree basically is a hierarchical data structure with a “parent” node (the origin node at the very top is called the root node) on top with children (maximum of two children in the binary trees we looked at), and those children may have children as well. The parents/children are connected with edges, and each node (parent or child) can have a value/label associated with it. There is only one unique path between nodes and the height of the tree is the maximum number of edges between the root node and the bottommost one. The traversal methods that we coded were confusing to me at first, but I found out that these methods simply return the data within the tree in a certain order (preorder or postorder).

There is clearly an abundant use of recursion when working with trees, so the examples that we worked on in class helped me practice writing more recursive code. The readings posted on the website also made me realize the uses of trees. I finally finished the first assignment, with the recursive methods to solve the four stool Hanoi problem working at last. Also, my GUI also works properly now. I managed to code the bonus problem, and hopefully I did that right (the tests pass). The assignment was a challenge but it was an interesting problem and it helped me understand recursion better. I've also looked over past term tests and am beginning to review the course material more thoroughly. 

 

Graphic representation of a tree data structure. 

http://www.powayusd.com/pusdtbes/images/tree_example.gif

Week 5: Hanoi Recursion and Scope

This week we went through a 3 stool recursive Tower of Hanoi solution, as well as going over scope. The Hanoi algorithm we went through really helped me understand the problem and I started working on a 4 stool recursive solution, which works somewhat so far, but getting it to work properly is proving to be fairly difficult. It also reminded me of that scene in Rise of Planet of the Apes when that ape was solving the problem. I think Danny was right when he said that the last 10% of the problem takes 90% of the the work; I'm done basically everything else for the first assignment. I feel fairly confident after another recursive example and the lab we did this week.

As my lab partner CrustyBlogger notes, the labs in this class are significantly more difficult than the ones in CSC108. The labs do help me learn the material and our lab partnership is an efficient one, and this week with the addition of Infernvs to our group, we were elevated to the status of dream team. Infernvs notes in his SLOG that the concept of OOP is a “trivially simple concept to explain”, which I agree with. His analysis of the Sierpinski triangle was pretty intense and went way over my head. I found I understood the scope concept fairly well because I have come across this idea before while learning Java. The prefix global allows a variable/function to be accessed throughout the class/file and nonlocal allows for access exclusively in the module (function). I already see the potential uses of this and I may implement it into my A1 code.

 

                         Hanoi is so simple an ape can solve it.               (http://static1.wikia.nocookie.net/__cb20120530021256/planetoftheapes/images/6/61/Bright_Eyes_2.jpg)