Playing with Snakes
>
∧
<

Chapter 11: Recursion: Calling yourself

To understand recursion, you must first understand recursion. -Anon
If you already know what recursion is, just remember the answer. Otherwise, find someone who is standing closer to Douglas Hofstadter than you are; then ask him or her what recursion is. - Andrew Plotkin.

Recursion is one of the traditional scary topics of computer science. Scary like stumbling across a velociraptor on Valentine's Day, after he was just dumped by his velociraptor girlfriend? No, not really. Scary like seeing me in the morning before I've had a cup of coffee? Close.

So let's explore recursion without any computers first.

picture

Our heroes are in the foreground, but there's a picture of them in the background, which features another picture of them in the background, which features another picture of them in the... Well, you get the idea.

Here's another one. There's a pretty neat organization out there called GNU that had a name which is a recursive acronym. The acronym is part of the definition of the acronym. GNU stands for GNU's Not Unix. Of course, the GNU in the definition stands for GNU's Not Unix, and that GNU stands for GNU's Not Unix, and so on.

PHP does something similar. PHP stands for PHP Hypertext Processor, and the PHP in the definition stands for PHP Hypertext Processor, and so on once again.

Finding a Sum

This may be one time (these times will become more frequent), when it makes more sense to just look at a program. Let's write a simple one that we've done a whole bunch of time. Let's find the sum of a list. Here's our old program.

<sidebar>

If you're really awesome at Python, you could also find the sum this way:

  1. reduce(lambda x,y:x+y,ourList)
  2.  

reduce recursively does a function (in this case the function is anonymous, meaning it has no name) on a list. It's neat, but any real Python person would just tell you to use Python's built in sum function.

</sidebar>
  1. def sum(ourList):
  2.   total = 0
  3.   for i in ourList:
  4.     total+=i
  5.   return total
  6.  

We can rewrite that program recursively. Rather than talk you through it, try reading it first:

  1. def recursiveSum(ourList):
  2.   if len(ourList) == 1:
  3.     return ourList[0]
  4.   else:
  5.     return ourList[0] + recursiveSum(ourList[1:])
  6.  

Here's how I read it. If our list has only one number in it, then the sum is that number. Otherwise, take the first number and add it to the sum of the rest of the numbers.

But what happens with the sum of the rest of the numbers? Well, Python will take ourList[1:] and give it to recursiveSum. Good old recursiveSum will take the first number of the new list (the second number of the original list) and add it to the sum of the rest of the list, and then return that sum to the original function.

So, to play that all out. Let's run through a sample. If our list was [7,5,3] and we wanted to find the sum, we'd do this:

  1. recursiveSum([7,5,3])
  2.  

Since the list has more than one number in it, we skip the if statement and do the else. So this function is going to return ourList[0] + recurisveSum(ourList[1:]). So for this program, that looks like this:

  1. return 7 + recursiveSum([5,3])
  2.  

But Python first needs to determine a value for recursiveSum([5,3]). So it calls the function again, this time leaving out the first number of the list. That second function call is going to look like this:

  1. return 5 + recursiveSum([3])
  2.  

The final function call is the easiest. recursiveSum([3]) will simply return 3, as the sum of 3 is 3. So let's substitute each of these values in. I'm putting some extra parenthesis in to make it easier to see what values come from which function calls.

  1. return 7 + (5 + (3))
  2.  

Calculating Fibonacci Numbers

Fibonacci Numbers are one of the classic introductory exercises when learning recursion. To make Fibonacci numbers, you start with 0 and 1 and add them together. Then take the sum and add it to the second of the original numbers. Then take the new sum and add it to our first sum, and so on. So you get a sequence like this:

0,1,1,2,3,5,8,13,21

You should probably give this a try first, then take a look at my answer.

  1. def fib(number):
  2.   if number == 0:
  3.     return 0
  4.   elif number == 1:
  5.     return 1
  6.   else:
  7.     return fib(number-1) + fib(number-2)
  8.  
<sidebar>

Python actually has a maximum recursive depth, to avoid letting recursion run out of control. If for some reason you need more depth (this is rare), you can change the limit with sys.setrecursionlimit.

</sidebar>

So here, we clearly see if statements for our base cases - 0 and 1. We also see the rest of the definition - a Fibonacci number is the two previous Fibonacci numbers added together. Identifying your base cases is a very important first step in recursion. If you don't do it properly, or at all, then your recursive function will run forever.

A more graphical example

Most of the examples we've looked at so far are either trivially easy, or woefully inefficient. But recursion is used in the real world all the time. One really common recursive algorithm is called flood-fill. You can think of it as a paint bucket.

There's an image format called bitmap that defines an image as a map of bits (obviously). This means that there's a grid of things called pixels, which each have one color. Here's an example.

picture

It's a pretty house, but I've always wanted a nicer roof. Maybe a bright red one, to alert other survivors of the zombie apocalypse that I'm still alive. Let's write a function to recolor our roof.

This first thing we need to do is pick a coordinate system for our bitmap. With almost all graphics, the top left corner of the image is 0,0. We'll follow the same convention.

picture

So our plan is going to be to click on a part of our house's roof and change the color to red. So, another way to look at that would be to say we're going to change the clickedColor to the targetColor. We'll also know two more things - the X and the Y that we're looking at.

So now we've defined our basic vocabulary, so we can look at our base situations. Two of those situations deal with the color we're looking at. If the color at X,Y is not the clickedColor, then we should stop changing colors. Similarly, if the color at X,Y is already the targetColor, then we should stop changing colors. The last base case is when we're off the edge of the image - when X or Y is less than 0 or greater than the width or height of the image.

So, let's look at our code so far:

  1. def floodfill(X, Y, targetColor, clickedColor):
  2.   if X or Y is off the edge of the image:
  3.     return
  4.   elif X,Y is targetColor:
  5.     return
  6.   elif X,Y is not clickedColor:
  7.     return
  8.  

Beyond our three base conditions, there's one other option - we need to be changing the color. In that case, we'll set the current X,Y to our targetColor and then call floodfill on each adjacent square.

  1. def floodfill(X, Y, targetColor, clickedColor):
  2.   if X or Y is off the edge of the image:
  3.     return
  4.   elif X,Y is targetColor:
  5.     return
  6.   elif X,Y is not clickedColor:
  7.     return  
  8.   X,Y = targetColor #setting X,Y to our targetColor
  9.   floodfill(x-1,y,targetColor,clickedColor) #to the left
  10.   floodfill(x+1,y,targetColor,clickedColor) #to the right
  11.   floodfill(x,y-1,targetColor,clickedColor) #up
  12.   floodfill(x,y+1,targetColor,clickedColor) #down
  13.   return
  14.  

While that isn't exactly functional Python, it's a good description of our entire algorithm. Some would call it pseudocode. Let's walk through what happens when we click. I'll click on cell 5,2. This is function call number 1.

First we check our if statements - none of them are true. So we immediately set 5,2 to our target color. That gives us this:

picture

Next line down of our algorithm says to call floodfill on the left. So we start a new function. This is functional call number 2. It sees the if statements are false, so it recolors cell 4,2.

picture

Once again, we continue calling floodfill on the left. This is a 3rd function call, which we call on 3,2.

picture

So here's where things get weird. We've just finished recoloring, so we once again call floodfill to the left. This is our 4th function call, on 2,2. But this time we hit an if statement. The color at 2,2 is not equal to our clickedColor, so our function returns. We go back to our 3rd function call. The next line down, we call to the right. This would be function call number 5, back on 4,2.

Ah! But the color of cell 4,2 is already targetColor. So we go back to the 3rd function call. Now we look up for function call 6 (not clickedColor) and then down for number 7 (also not clickedColor). So our 3rd function call is finally able to return. That takes us back to our 2nd function call, which is now able to look right for call number 8 (already targetColor). But then it makes a new function call 9 on the cell above - cell 4,1. It colors that one red. Then we continue with call 9, looking left, then right, then right again, etc.

picture

This process seems terribly slow, but actually happens pretty quick. It also carries the advantage of being able to color any shape.

picture

This website will be taken offline before the end of 2011