Week #7 - Recursion

So at this point, I should explain that I was not aware that there had been assigned topics for each week (after coming out of CSC165 where we just wrote about the course in general each week, I assumed it was the same for this course, aside from the assigned topics for weeks 3, 7, and 11). Because of that, I can't exactly refer back to an earlier post, so I will instead just be writing an entirely new post about recursion and hoping with luck and/or the TAs on my side, this will be counted.

Recursion has always been one of my favorite parts of computer science, because I think it was the first time I began to see computer science as an actual science instead of just a fancy name for programming. Until then I saw computer programming as purely something functional, without really understanding how things like scientific theory could really be relevant to it. For once, I was very glad to be proven wrong.

A recursive function is, to put it simply, a function that calls itself. This is generally done when it is logistically easier to call the same function over and over again instead of writing a function that does the same thing multiple times within the function body. An important part of recursion is the idea of passing through values or arguments through a function multiple times, What's always helped me to understand this concept is those pictures-within-pictures, like this one: http://i.imgur.com/YnXn1.jpg When you think about it, the original picture is actually the smallest version of the picture, in the very center, and that value (the picture) is just passed through to the outer frames, which sort of recursively recreate the picture. In computer science, the smallest version of the picture might be the leaf of a tree data structure, or a single integer, and that's just passed through the layers of recursion multiple times. The difference between computer science and the picture example is that in computer science recursion, generally a change is made to the value every time it passes through the recursion.

This week focused on tracing recursion, an integral part to understanding how to write recursive functions, especially ones that involve passing through arguments. This is where we depart from the comparison to a picture within a picture, because in class we've primarily focused on examples of recursion that sort of gather multiple values together (as can be seen by the example we worked on class that summed lists together). The general concept is still applicable of course, with values being passed through and the recursion being called multiple times. I didn't find the tracing example too confusing, but of course being able to trace recursion is so much easier than having to sit down and write your own recursive function. That being said, the tracing was a great way to force yourself to visualize exactly what the function is doing, which will be very helpful in writing future recursive functions.