Author:		Ghost Dancer
Date:		8th February 2003

A Word document of this article is also available in the downloads section.

This article assumes you have a basic understanding of Blitz functions and program flow (If statements, For…Next loops, While…Wend loops etc.).

What Is Recursion?

Simply put, recursion is where a function calls itself a number of times until a certain condition is met. With every new call, it will change one or more of the functions parameters depending on their current values.

Confused??? This is best explained with the aid of a simple example …

A Simple Example - Factorial Function

We are going to write a function that returns the factorial of a specified number. The Factorial of a number (n) is the product of all integer numbers from 1 to n.

For example:
The factorial of 5 is 1 x 2 x 3 x 4 x 5, which equals 120.

Don't worry too much about this, the focus is not what we are doing, but HOW we are doing it.

Now, if we wanted to code this using the traditional way, we would do something like:

Print factorial(5) Function factorial(number) For n = 1 To number If n = 1 Then result = 1 Else result = n * result End If Next Return result End Function

Using recursion, our code would look like this:

Print factorial(5) Function factorial(n) If n = 1 Then Return 1 Else Return n * factorial(n - 1) End If End Function

With a function this simple there is not much difference between the two methods, but it does illustrate the basic technique.

So how does it work?
The recursion has basically replaced the loop construct (For…Next). When we examine what is going on we can see that:

factorial(5) returns the value of 5 * factorial(4)
factorial(4) returns the value of 4 * factorial(3)
factorial(3) returns the value of 3 * factorial(2)
factorial(2) returns the value of 2 * factorial(1)
factorial(1) just returns the value 1 and no further calls to factorial() are made

Hopefully, you are beginning to understand the process. To clarify further, we can work backwards so we can see the values that are returned from each call and thus, how the final result is achieved:

factorial(1) = 1
factorial(2) = 2 x 1 = 2   1 is the value returned from factorial(1)
factorial(3) = 3 x 2 = 6   2 is the value returned from factorial(2)
factorial(4) = 4 x 6 = 24   6 is the value returned from factorial(3)
factorial(5) = 5 x 24 = 120   24 is the value returned from factorial(4)

Beware of Infinity!

In the above example, you will notice that the function only calls itself when n is not equal to 1, and because n is always counting down we know that there will be a finite number of calls. However, if you do not put in a condition, the function will continually call itself forever and Blitz will give you a Stack Overflow error.

It is advisable to put in a threshold so the function will only call itself a maximum number of times. This is illustrated in the next example…

A Complex Example - The Sierpinski Carpet

Now we've covered the basics, lets do something a little more interesting. The Sierpinski Carpet is a fractal named after the Polish mathematician:

Now, you may be thinking that this looks quite complicated. However, if we break it down in to easy steps, you will see that it is actually a simple repeating pattern - a perfect candidate for recursion.

Procedure for building Sierpinski's Carpet

Step 1. Start by drawing a filled white square the size of the carpet.

Step 2. Divide this square into nine equal squares and fill the middle one black.

Step 3. Repeat step 2 on each of the eight remaining squares. Each iteration (repetition) will create nine smaller squares around it's 'parent'.

The diagram below shows 3 iterations. The pattern grows exponentially at each stage.

So, we can see on diagram 1 that we have divided the square into nine squares and filled the middle one.

The next iteration (diagram 2) has had the effect of creating eight more squares around the square drawn in the first iteration.

Now, in the third iteration, a further eight squares has been created for each of the previous eight squares drawn in the previous iteration.

Hopefully, you see how this works, and why this is a perfect job for recursion. Lets see how it's done…

The Code

;set up screen & calculate it's centre Const screenWidth = 800, screenHeight = 600 Graphics screenWidth, screenHeight, 16, 2 centerX = screenWidth / 2 centerY = screenHeight / 2 ;initialise carpet values and start recursion Const carpetSize = 600 ;set this to required carpet size Const threshold = 4 ;set the recursion threshold ;draw carpet 'background' in centre of screen offset = carpetSize / 2 Rect centerX - offset, centerY - offset, carpetSize, carpetSize ;set colour to black and begin the recursion... Color 0, 0, 0 carpet(centerX, centerY, carpetSize, threshold) ;all done! wait for key press & end program WaitKey End ;recursive function Function carpet(x, y, size, threshold) newSize = size / 3 ;1/3 previous size offset = newSize / 2 ;new offset value ;draw rect in centre Rect x - offset, y - offset, newSize, newSize If threshold > 0 Then newThreshold = threshold - 1 ;reduce threshold ;call function 8 times, for each square around centre square carpet(x - newSize, y - newSize, newSize, newThreshold) carpet(x, y - newSize, newSize, newThreshold) carpet(x + newSize, y - newSize, newSize, newThreshold) carpet(x + newSize, y, newSize, newThreshold) carpet(x + newSize, y + newSize, newSize, newThreshold) carpet(x, y + newSize, newSize, newThreshold) carpet(x - newSize, y + newSize, newSize, newThreshold) carpet(x - newSize, y, newSize, newThreshold) End If End Function

How Does It Work?

Each time the function is called, it will draw a new square and requires 4 parameters - the x & y position of the centre of the new square, the size of square (this will be the carpet size when first called), and the current recursion threshold.

First of all, the function needs to divide the current square (defined by the size parameter) into 9 so it can fill the centre square. It does this by dividing the size by 3. Because we know the x & y position of the centre, we can easily fill the centre square. Notice how the offset value is used to draw the rectangle.

Once this is done, we need to check our threshold value.

If we have reached our threshold then we have finished. Otherwise, we set our new threshold value. Then, we simply call the function 8 times using the new size and new threshold values. We also have to specify different x and y values for each of the 8 remaining squares.

Limitations

As explained above, there must be a finite number of iterations to your recursion routine so it may be able to cope with what you want it to do. For example, it is relatively easy to do a flood fill routine using recursion, but on high resolution bitmaps you may get a Stack Overflow error due to the sheer number of times the function calls itself. I would not recommend having a threshold of more than a few thousand.

Conclusion?

As will most things in life, recursion has it's place but it is not always the best solution. Some people advise that you just steer clear of it all together but personally I think it offers a more elegant solution to many problems, which would often be 'clunky' using a more traditional approach (loops etc.).

Ultimately though it's up to you whether you take this approach or not. Some of us dig it, some of us don't.

Have fun...