Recursion Explained
Posted on April 28, 2014
This is the first in a series of posts with a specific, targeted audience, which means there’s going to be a relatively wide variation in level-of-explanation. Some of the posts are going to very clearly be me-writing-for-someone-who-already-knows-lots-of-relevant-information, and some (like today’s) will be me-writing-for-someone-who-wouldn’t-normally-read-this-blog. Anyway, today’s topic is what recursion is and why we should care. If you already think recursion is important, this post’ll be pretty surface-y and review-heavy. So, let’s get started, shall we?
Recursive-Xzibit thinks Recursive-Xzibit thinks Recursive-Xzbit thinks … that recursion is fun
So yeah, recursion. The basic idea is something that acts on itself, or something with multiple different levels. And oh, the places you can go with self reference!
The most recent/significant pop-cultural example I can think of is the movie Inception, where dreams could occur within dreams within dreams, and what happened in one level would bleed down into all the levels below it (e.g. when gravity stopped in the hotel because the truck they were dreaming in was falling off a bridge).
Recursion comes in a few different classes, and I’ve yet to hear any good terms to differentiate them, so I’m going to make some up:
The most recent/significant pop-cultural example I can think of is the movie Inception, where dreams could occur within dreams within dreams, and what happened in one level would bleed down into all the levels below it (e.g. when gravity stopped in the hotel because the truck they were dreaming in was falling off a bridge).
Recursion comes in a few different classes, and I’ve yet to hear any good terms to differentiate them, so I’m going to make some up:
- Unidirectional recursion
- Feedback only goes in only one direction
- Example 1: The Fibonacci Sequence (each element is the sum of the previous two elements, the first few are (0, 1, 1, 2, 3, 5, 8, 13, 21…)) - the later parts of the list are completely unimportant in figuring out the first few
- Example 2: Sorting a list (using quicksort) - one simple and efficient way to sort a list is a monotonic recursion - you pick the first number off the list, split the rest of it in two by putting all the numbers smaller than the first one on one side and bigger on the other, then sort each of those sublists
- Bidirectional recursion
- Feedback can go in either direction
- Example: Inception - the environment you’re dreaming in influences the dream, but the events within the dreams have lasting influence in the outside world (e.g. planting an idea in someone’s head, taking useful information, etc)
- Example 2: INT - this graph is sorta strange. It’s constructed entirely out of smaller versions of itself - any single point contains the whole graph. The lower levels are exactly the same as the higher ones. Cool, right?
- Mutual recursion
- Two things that are defined, each one in terms of the other
- This one’s generally a bit more complicated than the other two
- One set of good examples can be found in Hofstadter Sequences - specifically, the Figure-Figure sequence
- It’s pretty neatly defined in terms of itself and its complement (the set of all numbers not in the sequence)
- The first number of the sequence ((R(0)), if you will) is (1)
- The first number not in the sequence (Let’s call it (S(0))) is (2)
- The rest of the sequence is defined (R(n) = R(n-1) + S(n-1))
- So, for example, (R(1) = R(0) + S(0) = 3), and (R(2) = R(1) + S(1) = (R(0) + S(0)) + S(1) = (2+1) + S(1) = 3 + S(1) = 3 + 4 = 7)
- Let’s write out another one just for kicks:
- (R(3) = R(2) + S(2) = (R(1) + S(1)) + S(2))
- (= ((R(0)+S(0))+S(1))+S(2) = (3+4)+5 = 12)
So, why should we care exactly? Why does this fancy “recursion” thing even matter? Well, it’s by far the most elegant (and sometimes the only) way to define all those things up there, but let’s say you didn’t care about any of those. Why recursion?
Well, given that the target audience here is into music theory, let’s start with the immediately relevant example: fugues. Fugues are recursive - you start from a relatively well defined structure, then modify it according to various rules and weave the modifications together, and, if you know what you’re doing, beautiful music comes out.
Convinced you care yet? No? What was that? “More examples”? Great.
Well, recursion is useful in understanding language. I’d go into it, but Guy Steele did a presentation on this a while ago, and it’s one of my favourite talks on the internet, so I’ll link to that instead.
That brings me to my next point pretty nicely actually - recursion is extremely important in programming.
I’ll summarize a bit, but recursion-in-programming really deserves its own post
A relatively common idiom is to define a base case and a way to reduce anything else to said base case. We saw a few examples of that earlier, with the Fibonacci and Figure-Figure sequences - we defined (F(0)), (S(0)), and (R(0)), then gave rules for computing the rest of the sequences in terms of the first element.
But, to take a more programming-y example, let’s say you’ve got some operation (we’ll call it f) and you want to apply it to each element of a list. How would you go about that?
Well, you’d probably start by applying the operation to the first result of the list, then start again with the rest of the list, until you’ve f’d every element.
So, we’ve seen that recursion gives us pretty ways to define seemingly messy things, but the discussion is still incomplete. Why?
Simple.
I haven’t pulled out the pretty colors.
A discussion of recursion always has to end with fractals, so we’ll start with a joke, then follow up with a pretty picture:
I recently saw someone post a question on Quora, “What’s the prettiest image ever found by zooming in on the Mandelbrot set?” - The best answer was, of course, “The Mandelbrot set”.
The Mandelbrot set is defined by doing some funky things with complex numbers, and the trick is that it ends up containing infinitely many smaller versions of itself - Just about anywhere along the boundary, if you zoom in enough, you’ll find a (often very slightly deformed) copy of the whole set.
So, without further ado, pretty colors
