Recursion

There are a few principles in computer science that never fail to astonish me, one being recursion.  I was intrigued from the first time I heard Professor Heap mention the concept.   The reason I found it fascinating is because I had not expected the existence of a sneaky method as such that so cleverly uses the idea of a problem within a problem.  Recursion is the term given to the method used to solve one bigger problem by systematically approaching the solutions of smaller instances of that problem.   In other words, recursion occurs when a function calls itself a number of times until it reaches the solution it seeks.  One may think of this approach as a close relative of mathematical induction.  The beauty of this method is that it follows our own way of thinking; we like to break problems into smaller, more manageable parts.

A key to designing a successful recursive method is to include a base case; a condition to stop recursion hence preventing it from going to infinity.  Using the following example, it is easy to understand that function “get_factorial” uses itself to return the n factorial of consecutive numbers until it reaches the number 0, which is the termination condition.

 Having used the principle myself, I can say that there are both positives and negatives to this approach.  Recursion is often a preference by many programmers as it makes code clearer, simpler and more “elegant”.  Although recursion may be easier to handle, especially with transversing trees from the human end, I find that it is generally slower and takes more stacks and hence memory than more standard means of computing.  All in all, it seems that the nature of the problem eventually determines the most ideal method of computing.

Trees, labs and prep for midterm

I found this week's lab crucial to the understanding of the material covered thus far.  The problems really helped me revise for the midterm coming up in less than two weeks.  I noticed I was a bit weak with the principle of ADT.  I am going to repeat the examples we've covered thus far in class, and maybe drop by office hours before it's reading week!

Tracing the problem

This week has been no walk in the park!  I am a little ashamed to say that I was having some trouble understanding basic concepts in this course, like tracing.  At times, I would simply stare at the slides during lectures, trying to comprehend what is being said.

It has been a milestone for me to actually seek help this week, mostly because I tend to like doing things on my own.  I headed over to the Help Centre after trying to spin my head around an example we did in class, and I am glad I did.  As it turns out, tracing in recursion is not very different from the tracing we used to do in CSC108, and as the TA pointed, practice helps in this case.  I have spent the entire weekend, without exaggeration, working on various examples some of which were covered in class, and some new ones I found online.  In all honesty, I have had so much practice that I can proudly say that tracing has become almost second nature to me!