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: