Recursion Explained with the Flood Fill Algorithm (and Zombies and Cats)

This is a programming tutorial for beginner and intermediate programmers who want to learn what recursion is. The programming language used for the examples is Python, but you can probably follow along if you know programming in some other language such as PHP or JavaScript. There’s a lot more information about recursion on the Wikipedia article: http://en.wikipedia.org/wiki/Recursion_(computer_science) But this guide is meant to be a more practical guide to show how handy recursion is.

The source code of everything in this article can be downloaded here: floodfill_src.zip

Consider the Lazy Zombie

This is a cat:

This is a normal human:

This is a normal human who has been turned into an ungodly, flesh-eating zombie of the undead:

Zombies are lazy and will only bite things that are next to them. Humans that are bitten will then turn into zombies:

There is an interesting recursive principle here, because the humans that have turned into zombies will start to bite other humans that are next to them, which will make more zombies, who bite more adjacent humans, which will make more zombies, and so on and so on in a chain reaction:

Zombies don’t bite cats though. (Well, they do, but a zombie-bitten cat won’t turn into a zombie.) If you put a zombie next to a cat, you’ll just end up with a zombie and a cat:

So as long as there is a cat between the human and the lazy zombie, the human is safe:

The same cannot be said of any humans who don’t have a cat between them and a zombie:

So not only does this simple lazy-zombie principle cause a chain reaction of zombies, it also causes this chain reaction to stop when a cat is encountered. (Public Service Announcement: In the event of a zombie apocalypse, please locate your local crazy cat person for safety and shelter.)

Let’s make a two dimensional field of humans, cats, and zombies like this:

All we need is one starting zombie, and you’ll see the infection spread until the entire human population is zombified. But there’s hope. If there is an enclosed ring of cats blocking the initial zombie, then humanity is (slightly) saved. (In our example, zombies don’t bite diagonally.)

But if there is a gap in the cats, then the entire population is doomed:

This whole zombie thing is an elaborate and silly analogy for the flood fill algorithm.

The Basics: Recursive Calls and Base Cases

A recursive function is simply a function that calls itself. Here’s the simplest possible recursive function:

def foo():

foo()

The foo() function does nothing but call itself. The function doesn’t do anything useful (well, it will crash your program. That’s kind of like being useful.) A recursive function’s function call to itself is a recursive call.

Here’s a program that calls this pointless recursive function:

def foo():

    foo()

foo()

You can download it here: stackoverflow.py If you run this program, you’ll get this error message: “RuntimeError: maximum recursion depth exceeded” (This is called a “stack overflow” and is explained later.) Stack overflows happen when a recursive function doesn’t have a base case (explained next).

Here’s a relatively more useful recursive function:

def countdown(n):

print(n)

if n == 0: # this is the base case

return # return, instead of making more recursive calls

countdown(n - 1) # the recursive call

countdown(10)

Page 1 of 5 | Next page