Recursive patterns – the Cantor set

The Cantor set is an infinite set defined by German mathematician Georg Cantor (1845-1918) in 1883 (Note that a version of the set was defined earlier by Irish mathematician Henry John Stephen Smith in 1875 [1]). The rules for his infinite set are:

  1. Start with a simple line.
  2. Erase the middle of the line.
  3. Repeat step 2 with the remaining lines, over, and over, and over.

This of course offers an exceptional introduction to the notion of recursion. The process can continue to the point where the line segment becomes 1 unit in length, and therefore from a practical viewpoint the recursion stops. From a theoretical viewpoint, it can continue forever.

The first step in creating a recursive algorithm for Cantor is deciding how the algorithm will function. We know from the rules of the infinite set that the idea is to remove the middle ⅓ of the line, however the easier way to achieve this is to “split” the line drawing the left and right thirds. This means that if we initiate the algorithm using a line starting at position (x,y), with a length z, line(x, y, x+z, y), then the next iteration of the algorithm would draw two “sub-lines”, of the form (written in Processing):

void cantor(float x, float y, float z)
{
   line(x, y, x+z/3, y);
   line(x+z*2/3, y, x+z, y);
}

Now a non-recursive algorithm could be derived using these two calls to line(), however this does involve some tiresome math for every iteration of the loop. Not exactly ideal. However the two lines above form the basis of the recursion. Instead of using them to draw an individual line, they can be used to process the recursion. Let’s convert the function above to a recursive one. It requires a few tweaks to the function. Obviously the value y only needs to be passed once, and the exact position of the line segment can be passed as the starting point (x,y), and length (z).

void cantor(float x, float y, float z)
{
   cantor(x, y, z/3);
   cantor(x+z*2/3, y, z/3);
}

Of course if this were run, it would do nothing (except chew up processor resources). We have to add back a call to line() to actually draw something, and increment the value of y (otherwise the lines in the recursive calls will overwrite each other).

void cantor(float x, float y, float z)
{
   line(x, y, x+z, y);
   y = y + 20;
   cantor(x, y, z/3);
   cantor(x+z*2/3, y, z/3);
}

Now there is one final thing to do, add an end condition, so the recursion can terminate. This we can add by adding an if statement to terminate once the length of a line is less than zero.

void cantor(float x, float y, float z)
{
   if (z >= 1){
      line(x, y, x+z, y);
      y = y + 20;
      cantor(x, y, z/3);
      cantor(x+z*2/3, y, z/3);
   }
}

Here is an example of this running in a Processing with the following initial call:

cantor(10, 20, width-20);

[1] Cantor, G., “Uber unendliche, lineare Punktmannigfaltigkeiten“, (On infinite, linear point-manifolds (sets)“, Mathematische Annalen, 21, pp.545-591 (1883). (long, in German, no pictures!).
[2] Smith, H.J.S, “On the integration of discontinuous functions”, Proc. of the London Mathematical Society, 6, pp.140-153 (1874/75).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.