Graphics and recursion
This week marks the one year anniversary of the Remember Java web site! The project is still going strong,
even if I had to cut down on the weekly publications. However, I do not intend to cut down the site, so
do expect regular updates in years to come.
We celebrate the day, or week, by diving into the wonderful world of
recursion and see what happens when you do things
over and over and over again. The concept is not that difficult, and when you are done, you will
see some interesting graphics on you screen.
If you have not done any courses in algorithms and data structures, I would like to make sure you have an
idea of what recursion is all about. One computer dictionary describes it in this way: "Recursion. See recursion".
You get the notion of a loop, or more precisely, a method that has a call to itself. It turns out that this
can lead to very elegant solutions to some problems. However, don't forget the for-loops are still around, and
when doing simple iterations, they are preferred because of the extra overhead of method calls caused by a recursive
Never the less, I will demonstrate a very simple recursion by simulating a simple for-loop that counts. Suppose
you want to count from 0 to 5. This method would do the job, when called by count( 0, 5 ).
void count( int i, int stop )
if( i < stop )
count( i+1, stop );
Now implement a method that counts in decreasing steps. You are allowed to change the input parameters.
Hint: This could be done in two ways. Can you see them both?
The example above was a very simple one, and did not really demonstrate the power or mystery of recursion. More
complex results are achieved by studying where in the method the recursive call is placed, and the changes to the
By making small changes to the method in the previous example, implement a single method that gives this output on two lines:
0, 1, 2, 3, 4
4, 3, 2, 1, 0
Often recursion is used to divide a problem into several smaller sub problems or tasks. This includes several
sorting and searching algorithms. We will not go into those theories here, However, imagine you were to count
the files on your hard disk, or within a particular folder. One way to divide this job into several smaller jobs,
would be to count all the files in the base directory, and then do the same for each of the sub directories.
Implement a program that does this.
Yet another fascinating result of recursion appears when applied to graphics. Fractals are complex
structures that rely heavily on recursion. Other structures are more simple to draw. Study the picture below,
and try to implement it by using recursion. Some might know this as a Cantor set.
Finally, this week I will show a recursive figure I discovered some years ago and dubbed The Eight Arm. The idea
is that you draw a star with eight arms out from the centre, thus the name. You would get the figure below.
The recursive part comes in when you draw new smaller stars with its centers on eight arms. This results in
Then you repeat the procedure recursively for each of the eight new stars, thus the third step will draw
8 * 8 = 64 new even smaller stars. The size, or radius, of the new star clearly influence the figure. In the pictures
show, I let the new radius r' be 0.6 * r, where r is radius of the initial star. Furthermore,
where on the previous star you draw your new one will also make a difference. In my setup, I set the centre of
the new star at length r' away from the centre of the previous star. For 6 recursion levels, this give
Now, this looks a bit black and dull, therefore I added some colours. Of course you could set the colours on the
lines in any way. Do experiment with it! I found that using the centre co-ordinates and radius of the star as parameters
in co-sinus functions for the color components gave interesting results.
I do encourage you to implemented this recursion and have a play with it. Actually, it's quite interesting
to watch the figure while it is drawn.
These exercises were perhaps not the most exiting and clearly not very advanced uses of recursion. So, as I bonus this
week, I include some pictures of Mandelbrot (left) and Julia fractals made by the KDE Fractal Generator 1.3 by Uwe Theim.
These are just details of the whole fractals.