Sunday Serious Series: Argh Recursion!

So, I just finished an assignment for CSC240, and there is one question that took me more than 4 hours to completely figure out. It is kind of silly, but the source of difficulty is simply recursion NOT being used, and hence I find my motivation to write about recursion and finish this long overdue post.

So what is recursion, specifically in computer science? Recursion is a way to view a problem or object in terms of components that are similar to the original subject of interest, and then the whole thing is reduced to recursive steps and/or base cases. For example, it can be finding the greatest common divider of two numbers using Euclid's algorithm, or a particular implementation of tree data type - linked tree. Frequently this is compared to the other way to do things, the iterative way. These two ways are equally powerful in their ability to handle things (you can loop over the numbers to find the greatest common divider, and tree can be done as nested list), but, as usual, one way is better than other in different scenarios.

The first thing to look out for when using recursion is correctness. Usually, when the problem and object is handled recursively, the correctness is simply tied to induction proofs. If a proof of correctness is required, to me it seems very natural to find a recursive algorithm or definition, since proving correctness for iteration can be a huge pain - you need to come up with invariant for the loop to show it is correct and that is what makes me working so long for the CSC240 assignment. Although proof of termination is more difficult in recursion when there is no base case to reduce to (Euclid's algorithm for GCD is a good example), the work saved here by adapting iteration is, in my opinion, slightly less than the extra work in proving correctness.

The second thing to be careful about in recursion is the amount of information to characterize the question or object. A lot of times what is required is not sufficient for a recursion and more information is needed to actually consider the subject recursively. I myself find this come up especially often when solving problem of mutable objects in OOP, since not only the basic induction has to be handled, dividing objects into smaller component for recursion also requires some more information to specific the operation. A wrapper-helper approach is often accompanying to separate the concerns, and sometimes help reducing computational resources taken up as in memoization.

In general, well-written recursions are easy to read and understand, and it is quite plausible that using it more often will make it even better - something that I don't think iteration has going for it.