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.
