A couple of months ago, President Obama wrote his first lines of code as part of the “Hour of Code” program for National Computer Science week. You can check out his experience here and take a crack at the hour of code yourself at this site. In that spirit, I thought I’d take today to teach you one of the main concepts of programming, recursion.

Recursive logic is something that almost all programmers struggle with at first, and is a source of continued humor. In the glossaries of many computer science book the definition given for recursion is:

Recursion see *recursion*.

By the end of this post I hope you’ll not only get the joke, but get the concept as well. This is one of the most powerful, elegant ways to code, and it is simple enough that your five year old has already used it.

Recursive algorithms are made up of two parts, a repeated action (or function) and a base case. In programming one way we do a repeated action is a loop. This can be for a fixed amount of time, or until a certain condition is met.

**Fixed**

counter = 0 while (counter < 100) {do somethingcounter = counter + 1}

**Conditional**

numberOfHeads = 0 while (numberOfHeads < 50) {flip a coinif (heads) {numberOfHeads = numberOfHeads + 1}}

In this example the fixed loop will run 100 times and stop, the conditional loop will run until heads turns up 50 times. The loop repeats everything (in italics) until the while condition is met.

A few quick definitions before we get started. A *function* is a set of instructions executed in linear (top-down) fashion. It can *call* (run) other functions. Those called functions run a set of instructions, then *return* to the function that called them, continuing execution of the calling function after the line where the other function was called.

Examples help:

function A { do this then do thiscallfunction B finally do thisreturn}

function B { do this some morereturn}

When function A is run the order of execution would be:

do this then do thiscallfunction B do this some morereturnfinally do this

Now let’s take our coin flipping example and write it as a recursive algorithm. Again a recursive algorithm has both a repeated action and a base case. The repeated action is flipping the coin, and the base case is when we’ve gotten 50 heads.

function flippingCoins(numberOfHeads) { flip a coin if(heads) { numberOfHeads = numberOfHeads + 1 }if(numberOfHeads = 50){ // Base Case stop flipping } else {call flippingCoins(numberOfHeads)// Recursive Call } return }

The base case (highlighted in **bold**) is when we get 50 heads. Instead of looping back to the top we call the function from inside itself. For own coin flip example, this doesn’t seem to make much of a difference and looks like a lot more code for a simple loop. But in other cases, this recursive call has a stacking effect. Instead of repeating the same action over and over (like flipping a coin) each recursive call has an effect on the step above it.

Let’s take a look at another example:

function foldPaper(numberOfFolds) { fold paper in half numberOfFolds = numberOfFolds + 1 if(numberOfFolds = 4) { make cuts } else { call foldPaper(numberOfFolds) } Unfold Paper return }

This function takes a sheet of paper, folds it in half four times, makes some cuts, then unfolds the paper. Our base case is after we’ve made four folds, and our recursive call is to fold paper. We’ve added one more step to this function which is to unfold the half of paper we just folded at the end of the function.

So our first step is to start with a full sheet of paper:

Then fold it in half (adding 1 to the number of folds).

Since we’ve only made 1 fold our base case is not met so we call our function again. Now we’re not starting with a full sheet of paper, since our first function call folded the paper in half, so when we repeat the fold, the paper is now folded in quarters.

So far we’ve made 2 folds, so our base case is still not met, so we call the foldPaper function again. As before, the foldPaper function starts by folding the paper in half.

Now we’ve made three folds, we still haven’t met our base case yet, so we call foldPaper one more time.

After four folds our paper is folded into sixteenth’s and we’ve met our base case. So now we can make a few cuts.

After we make the cuts we unfold the paper once and start at the place where the previous function called us.

After the function call to foldPaper returns we unfold the paper again.

And again.

And again.

Remember, functions execute top to bottom. Here’s what our full function call would look like.

Call foldPaper fold paper in half Call foldPaper fold paper in half Call foldPaper fold paper in half Call foldPaper fold paper in half cut paper unfold paper return to foldPaper unfold paper return to foldPaper unfold paper return to foldPaper unfold paper end

The cuts were only made once but had an effect based on the number of times the paper was folded. If the paper was folded one less, or one more times, the resulting image would have been different, and each fold had an effect on the first one. And the unfold paper step had to happen for us to be able to see that image, but only after the cuts had been made.

If this had been a loop it would have been like that coin flip, folding a full sheet of paper in half each time. We’d never see the smaller and more intricate patterns.

Hopefully now you’ve got some basic understanding of what recursion can do or at least how it works. If you understand this, then you’re well on your way to becoming a great programmer.