Tag Archives: Recursion

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 something
  counter = counter + 1
}

Conditional

numberOfHeads = 0
while (numberOfHeads < 50) {
  flip a coin
  if (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 this
  call function B
  finally do this
  return
}

function B {
  do this some more
  return
}

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

do this
then do this
call function B
do this some more
return
finally 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.