Week 7 - Recursion

Recently, there was a popular movie starring some very famous people called Inception. I’m not going to talk about that at all because it’s super obvious and it’s been done to death.

Now, recursion is a little unsettling at first. How can we have a definition that references itself? The Oxford English dictionary would never define “pointless exercise” as “an exercise which has no point”. Our intuition tells us that we need to enlist the help of some outside information to produce a workable definition. Not so with recursion. All we need is a base case, or terminating condition, which prevents us from going too far down the recursive rabbit-hole.

Admittedly, it takes something akin to a leap of faith to write that first self-referencing function. And the first time it works it’s a little bit magical. But with a little bit of tracing it’s not so hard to understand how recursive solutions work, and that recursive solutions are both powerful and elegant. This stems from the fact that many of the problems we face in computer science are inherently composed of similar nested sub-problems that can be reduced to base cases. The tool we used when confronted with these repetitive problems in the past was iteration, which is only a tenable solution when confronted with reasonably shallow nesting and predictable conditions. When the nesting becomes more complex and branching, an iterative solution becomes prohibitively complex, and recursion is much more favourable. In the case of binary trees, for instance, a recursive solution allows us to traverse the data therein without knowing exactly how deep the nesting goes, as iteration would. See What's Gabbening for an exciting and enlightening picture of such a tree.  As long as a recursive function has a correct base case at which it terminates, it could perform operations on an almost infinitely branching tree, with computer power being the only limiting factor.

Recursion has so profoundly changed my worldview that I’m even using it when I don’t have to. For instance in this week’s lab involving linked lists I proudly flaunted my recursive solution, only to find that apparently there was a non-recursive solution that was easier to implement.  I’m still a little indignant. 

Anyway, I’m going to repeat this joke here because probably no one saw it a few weeks ago. I think it’s classic.

What’s Benoit B. Mandelbrot’s middle name?

Benoit B. Mandelbrot.