Trees

Well, now I realize that the photo of the tree from my previous post would have been better suited here. Oh well!

Conceptually, trees are not an incredibly difficult structure to grasp. From a young age most people have encountered a tree structure of some sort during their daily lives. Probably the most common and boring example is arithmetic expressions from math. Even if these are not thought of by the individual as a tree, they are in fact a type of tree.

Trees obviously come in many different forms, although I'm mainly interested in the computer science variety! Trees in computer science are used to represent structured collections of data. They can be thought of as an upside-down version of a real tree - with the roots at the top. Except, instead of having a vast system of roots, a computer science tree has only one root. From this root there can be any number of branches, each leading to another smaller tree.

The reason trees are so useful is their ability to link data together in a meaningful way. Consider a collection of names. Sure you can store all those names in a python dictionary or list, but if you store them using a tree structure, simply the way that they are organized will impart an extra form of implicit information.

Lets say you wanted to store all the names belonging to a particular family. You could contain them within a list, even have them in some kind of order, but you would essentially just have a list of names. On the other hand, if you store those names using a tree you could have say the great grandfather at the top; his children below that, and their children below that. Hopefully that makes some sort of intuitive sense, considering that this is type of tree is well known and refered to as a 'family tree'.

Of course this description and examples are only the most basic and simplified versions of trees, but hopefully they illustrate a clear image of what a Tree is.

Recursion and The Towers of Anne Hoy

This week, and some of the previous, have been about trying to wrap our heads around the idea of recursion and writing recursive functions. We have been shown a variety of ways that recursive strategy and thinking can be applied to problems that may seem complex at first glance.

Nature has be using recursion long before humans figured out what it was!

A tree grows by repeating the same basic process with slight variations.

When recursively programming, a base or general case is conceived. In other words, a problem is broken down into it's smallest possible chunk. Then an operation is performed on this chunk. The same operation is then performed again and again until the problem is solved. This way of deconstructing a problem can be very useful when trying to deal with a simple problem that has been scaled up. An example of this from our lectures would be finding how many lists are nested within a list. Finding how many lists are in one list is fairly easy, but the fact that it would be possible for each list to contain it's own list could make it difficult to count the amount of lists within other lists. This is where recursion can be a great asset. All that you have to be able to do is code the smallest version of the problem and the computer will do the rest for you.

At first I struggled with the concept of recursion but seeing a variety of examples has helped me to get a better grasp of how it works. I can confidently say that I do understand what it means when something is recursive. However, I have not had much practice with programming recursively and so I'm not yet sure how easily I will be able to apply what I've learned. Fortunately, the first assignment in the class should give me an oppurtunity to do just that.

The problem in assignment one is modelled after the towers of hanoi. A classic problem that involves moving ring shaped objects from one post to another without violating the rule that a larger ring can never be placed on top of a smaller one. Essentially, we have been asked to solve this problem except for with one more post than usual – 4 instead of 3. Since recursion has been such a hot topic I am assuming that it will be required to properly solve this. I'm still working on the starting section of the code and have not yet attempted to implement recursion but I will. I'll be posting my progress next week.

Photo credit: ©2008-2014 crazykitty82stock

Image source: http://crazykitty82stock.deviantart.com/art/tree-stock-83313306