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