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

You can download this program here: simplerecursion.py. When you run this program, the countdown() function is called and passed the integer 10 for the n parameter. The function will print this number, and then later call itself but pass the integer 9 (which is what n – 1 is). That second call to countdown results in 9 being printed to the screen, and then calls itself and passes 8. This keeps going until countdown() is called with an n parameter of 0. Then it just returns to the function which called it, which is the countdown() function. That function then returns to the function that called it (also the countdown() function) and the program keeps returning until it has returned from the original countdown() function call.

The condition that a recursive function will stop making recursive calls to itself is called the base case.

A Stupid Recursive Example: Fibonacci Sequence

The recursion property can do some pretty cool and powerful things. Most textbook examples of recursion show the Fibonacci sequence. The Fibonacci sequence is a sequence of numbers that begins with the numbers 1 and 1, and then each number afterwards is the sum of the two previous numbers:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55 and so on…

A recursive function to calculate the Nth number of the Fibonacci sequence that is typed into Python’s interactive shell would look like this:

>>> def getFib(n):

...     if n == 1 or n == 2:

...         return 1

...     return getFib(n-1) + getFib(n-2)

...

>>> getFib(4)

3

>>> getFib(10)

55

>>>

This works because to calculate getFib(5), you just add the results of getFib(4) and getFib(3) (and those in turn make more calls to getFib() until they reach the base case where getFib(1) or getFib(2) is called.) A good indicator that you can perform a task by using recursion is that the task can be divided into identical smaller sub-tasks. The Nth Fibonacci number can be calculated by calculating the N-1 and N-2 Fibonacci numbers, which themselves can be calculated by finding other Fibonacci numbers, until you reach the base case of having to calculate the 1st or 2nd Fibonacci numbers (which are both just 1.)

But this is a stupid example of recursive functions. You could have easily written an iterative (that is, non-recursive) function to do the same thing:

>>> def getFib(n):

...     a = 1

...     b = 1

...     i = 3

...     while i <= n:

...         c = a + b

...         a = b

...         b = c

...         i = i + 1

...     return b

...

>>> getFib(10)

55

>>>

The iterative function is a little bit longer, but it does the exact same thing as the recursive version and is probably easier to understand. This stupid example doesn’t show the power of recursion very well. Why learn recursion when straightforward iterative approach works just as well? Consider the flood fill problem, which does not have an obvious non-recursive solution…

Flood Filling

Flood filling is when you want to change the color of an area of color in an image. It’s available in a lot of graphics programs and usually looks like a paint bucket being tilted over, like this:

For example, if we flood fill a circle, the change will look like this (the blue dot indicates where the flood filling starts):

The blue flood filling starts at that blue point (which was originally white), so it will keep spreading as long as it finds adjacent white pixels. Imagine it as blue paint pouring on that dot, and it keeps spreading until it hits any non-white colors (like the black circle). If we started the flood filling from the outside of the circle, then the entire outside area would be filled up instead:

Flood filling a circle that is not completely enclosed wouldn’t work the same way. The flood filling color would “leak out” the open space in the circle and then fill up the outside space as well:

The really clever thing about flood fill is that it can fill up any arbitrary enclosed shape:

Page 2 of 5 | Previous page | Next page