Recursion

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 solution.

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 )
  {
    System.out.println(""+i);
    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?

Rec.java

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 parameters.

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

Rec.java

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.

Cantor.java

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 this figure.

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 a hexagon.

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.

EightArm.java

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.