One of the first novel ideas you learn in computer programming is the concept of recursion: functions that call themselves. It is a new idea to most and extremely powerful in the world of computers. It is also the point in the programming class where you figure out if you “get it” or if you should just stop now.

So let me explain the basic idea to those who don’t think in terms of functions or methods, or even know what they are. It is all about dividing a problem into a set of smaller problems. Imagine you are at the end of the line for Splash Mountain at Disneyland and they come tell you they need everyone’s phone number to give them a free ticket on a Disney cruise. But you don’t know everyone’s phone number! In fact, you can’t even see to the front of the line. How do you solve the problem?

You break it up into a smaller problem of course. You know your phone number right? And you know how to tell the person in front of you to do the same (smaller problem because that person has one less phone number (yours) they are responsible for). And if you do that enough times, pretty soon you are at the front of the line. Easy.

That was an extremely simple real world recursion example. They get harder and less tangible. The classic first example you encounter in programming is math factorials. As in, 7! = 7 x 6 x 5 x 4 x 3 x 2 x 1. This is perfectly suited for recursion because it can be easily broken into smaller problems. What is 7 factorial? Well it is 7 times 6 factorial. And what is 6 factorial? It is 6 times 5 factorial. And so on down the line. All you need to make sure is that you have a “base case” to stop on (so that you don’t keep calling the same thing to infinity and go into negative numbers), in this example 1! = 1.

However, there is much more to this classic example than meets the eye. Most programmers will stop there, but as it turns out, there are a ton of ways to actually solve this problem. I came across a ranting post on all the different things you might consider when coding your solution. Things like how big a number it supports, how much computer resources you want to consume, and how easily to switch your approach. It is an interesting foray into the mind of an experienced programmer – if you have ever coded up a way to calculate factorials check out the article.
 

---

 

Photo: fdecomite