This lab is all about writing functions, especially recursive ones!

To that end, you are going to create programs that create fractal images:
  • These are images where a part, or parts of the image, is the same as the entire image but on a smaller scale.

Fractals have lots of applications in engineering and pure mathematics.

Makefile and Submission

Download and use this Makefile. Add compilation details for each part. Use the following terminal command for submission. 
~/bin/submit -c=IC210 -p=lab11 Makefile part*.cpp
 

Credit: Feliks Tomasz Konczakowski

Part 1: Can you repeat that please?

To start we will write a helper function repeat that will be helpful for drawing the fractal patterns for the rest of the lab.

Download part1.cpp In this file, you will find a main method that is completely written for you, and a prototype for a function that you need to write:


// Prints out the string s, count times in a row,
// in a single line.
void repeat(string s, int count);

Use recursion.

We know you could write the definition of this function using a loop. But to get started, your task is to write the definition of the repeat function using recursion.

Don't change the main() function at all.

You should not change main at all for this part — just get repeat working perfectly and submit.

Strings for Unicode symbols.

You should notice some unusual-looking strings in the main function such as

string DIAMOND = "\u2bc1";

As you saw in Project 2, this is a special non-ascii symbol called Unicode. The important thing to know is that, even though it prints out as a single symbol in the terminal, it has to be stored as a string and not a single char.

We’ll use these unicode symbols in the rest of the lab!

Part 2: Cantor Set

Once the first part is working perfectly, copy your repeat function into the part2.cpp file to get started on this part.

Our first fractal image will be a one-dimensional visualization of the Cantor Set. This is an important mathematical set with some surprising properties: for example, it is completely “empty” and doesn’t contain any sub-interval of the real line, but it simultaneously has more elements than all of the possible fractions (in terms of cardinality).

But all that doesn’t matter to us; we are just drawing some ASCII art!

Your task

Write a program part2.cpp that reads in a size from the user, and prints out in a single line the Cantor set for that size, using X and _ characters.

Example runs:

~$ ./part2
size: 1
Width-1 Cantor set:
X

~$ ./part2
size: 3
Width-3 Cantor set:
X_X

~$ ./part2
size: 9
Width-9 Cantor set:
X_X___X_X

~$ ./part2
size: 27
Width-27 Cantor set:
X_X___X_X_________X_X___X_X
  
Make sure to understand the recursive relations applied in the examples.

Width-1 Cantor set
= Base case



Width-3 Cantor set =
Width-1 Cantor set + Width-1 empty region + Width-1 Cantor set



Width-9 Cantor set =
Width-3 Cantor set + Width-3 empty region + Width-3 Cantor set



Width-27 Cantor set =
Width-9 Cantor set + Width-9 empty region + Width-9 Cantor set

Recursive definition of a Canter set

Here is a good definition of the Cantor set for our purposes:
A Cantor set of length n has three equal parts:

Notice how this definition is recursive! The actual Cantor set goes on infinitely into smaller and smaller recursive sets.

Base case

In order for this to work in a computer program, it needs to have a base case! Here is how you will make that work:
In your program

Your program will work and look good for any (positive) size that is given, but to avoid specifying the details on rounding the auto-tests will only use powers of 3 for sizes like 1, 3, 9, 27, 81, etc.

Hints

Part 3: The full Cantor

Download part3.cpp.

Now we want to show the step-by-step creation of the Cantor set on multiple lines, all with the same width. So you should start with a line of all Xs, then a line with the middle third removed, and so on, ending with the last line like you printed in your part 1.

See some examples below. Again, we will only run auto-testing on power-of-three sizes, even though your program should print something that looks good for any given size.

  • You should keep your functions from Part 2, repeat and cantor_row.

  • But now you will want to modify cantor_row. You might want to add another parameter to keep track of how many levels to go down in the recusion. So the prototype might look like:

    void cantor_row(int width, int index);

  • Needless to say, it is important to find out the recursive relation used for cantor_row. Hints: (Read the following very carefully)
    • cantor_row(9,3):
      cantor_row(3,1) underlines cantor_row(3,1)
    • cantor_row(9,9):
      cantor_row(3,3) underlines cantor_row(3,3)
    • cantor_row(27,9):
      cantor_row(9,3) underlines cantor_row(9,3)
  • It is a good idea to check the correctness of your cantor_row() function by running the code below (comment out the contents in main() of part3.cpp and add the following code). You may want to think about the recursive relation using small-width cases first. Then, move on to the case of width 9 and then width 27 and so on to verify your guess. 

    
int main()
{
  cout << endl << "cantor_row(1,1):" << endl;
  cantor_row(1,1);

  cout << endl;
  cout << endl << "cantor_row(3,1):" << endl;
  cantor_row(3,1);
  cout << endl << "cantor_row(3,3):" << endl;
  cantor_row(3,3);


  cout << endl;
  cout << endl << "cantor_row(9,1):" << endl;
  cantor_row(9,1);
  cout << endl << "cantor_row(9,3):" << endl;
  cantor_row(9,3);
  cout << endl << "cantor_row(9,9):" << endl;
  cantor_row(9,9);


  cout << endl;
  cout << endl << "cantor_row(27,1):" << endl;
  cantor_row(27,1);
  cout << endl << "cantor_row(27,3):" << endl;
  cantor_row(27,3);
  cout << endl << "cantor_row(27,9):" << endl;
  cantor_row(27,9);
  cout << endl << "cantor_row(27,27):" << endl;
  cantor_row(27,27);
  cout << endl;

  return 0;
}

~$ ./part3
size: 1
Width-1 Cantor set:
X

~$ ./part3
size: 3
Width-3 Cantor set:
XXX
X_X

~$ ./part3
size: 9
Width-9 Cantor set:
XXXXXXXXX
XXX___XXX
X_X___X_X

~$ ./part3
size: 27
Width-27 Cantor set:
XXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXX_________XXXXXXXXX
XXX___XXX_________XXX___XXX
X_X___X_X_________X_X___X_X





cantor_row(1,1)




cantor_row(3,1)
cantor_row(3,3)




cantor_row(9,1)
cantor_row(9,3)
cantor_row(9,9)




cantor_row(27,1)
cantor_row(27,3)
cantor_row(27,9)
cantor_row(27,27)
 

Part 4: Going further, Carpet

Now let’s try to make some two-dimensinal fractals! The first shape is called a Sierpinski carpet and it’s kind of the 2D version of a Cantor set, but it looks way cooler:

(source: AnaMarie)

~$ ./part4
size: 1
Width-1 Sierpinski carpet:
♦
~$ ./part4
size: 3
Width-3 Sierpinski carpet:
♦♦♦
♦ ♦
♦♦♦
~$ ./part4
size: 9
Width-9 Sierpinski carpet:
♦♦♦♦♦♦♦♦♦
♦ ♦♦ ♦♦ ♦
♦♦♦♦♦♦♦♦♦
♦♦♦   ♦♦♦
♦ ♦   ♦ ♦
♦♦♦   ♦♦♦
♦♦♦♦♦♦♦♦♦
♦ ♦♦ ♦♦ ♦
♦♦♦♦♦♦♦♦♦
~$ ./part4
size: 27
Width-27 Sierpinski carpet:
♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦
♦ ♦♦ ♦♦ ♦♦ ♦♦ ♦♦ ♦♦ ♦♦ ♦♦ ♦
♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦
♦♦♦   ♦♦♦♦♦♦   ♦♦♦♦♦♦   ♦♦♦
♦ ♦   ♦ ♦♦ ♦   ♦ ♦♦ ♦   ♦ ♦
♦♦♦   ♦♦♦♦♦♦   ♦♦♦♦♦♦   ♦♦♦
♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦
♦ ♦♦ ♦♦ ♦♦ ♦♦ ♦♦ ♦♦ ♦♦ ♦♦ ♦
♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦
♦♦♦♦♦♦♦♦♦         ♦♦♦♦♦♦♦♦♦
♦ ♦♦ ♦♦ ♦         ♦ ♦♦ ♦♦ ♦
♦♦♦♦♦♦♦♦♦         ♦♦♦♦♦♦♦♦♦
♦♦♦   ♦♦♦         ♦♦♦   ♦♦♦
♦ ♦   ♦ ♦         ♦ ♦   ♦ ♦
♦♦♦   ♦♦♦         ♦♦♦   ♦♦♦
♦♦♦♦♦♦♦♦♦         ♦♦♦♦♦♦♦♦♦
♦ ♦♦ ♦♦ ♦         ♦ ♦♦ ♦♦ ♦
♦♦♦♦♦♦♦♦♦         ♦♦♦♦♦♦♦♦♦
♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦
♦ ♦♦ ♦♦ ♦♦ ♦♦ ♦♦ ♦♦ ♦♦ ♦♦ ♦
♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦
♦♦♦   ♦♦♦♦♦♦   ♦♦♦♦♦♦   ♦♦♦
♦ ♦   ♦ ♦♦ ♦   ♦ ♦♦ ♦   ♦ ♦
♦♦♦   ♦♦♦♦♦♦   ♦♦♦♦♦♦   ♦♦♦
♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦
♦ ♦♦ ♦♦ ♦♦ ♦♦ ♦♦ ♦♦ ♦♦ ♦♦ ♦
♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦
 

Your task is to make a program part4.cpp which reads in a size from the user, and displays a Sierpinski carpet of that size.

Here’s the recursive definition:

A n * n Sierpinski carpet divides the square into 9 smaller (n/3) * (n/3) squares.

  • Each of the 8 outside squares is a (smaller) Sierpinski carpet.
  • The square in the middle is empty.

See sample runs on the left.

To make this look good, we don’t want to use X’s and underscores this time. Instead, use actual spaces " " for the blank space, and use diamonds ♦ for the base case of a 1x1 carpet. Because the diamond is not a normal ASCII character, it can’t be represented with a normal char type in C. However, you can represent it as a string using the Unicode syntax:

string DIAMOND = "\u2bc1";
cout << "Here is a diamond:" << DIAMOND << endl;

Hints

  • Even though the fractal image recurses in two dimensions, your program still works only one row at a time! You probably want to make a function to output a single row, with a signature like

    
void carpet_row(int width, int row_index);

    where the parameter row_index represents which row of the image is being produced.

    If you follow this suggestion and start your row_index at 0, then, for example, calling carpet_row(27,12) should produce the 13th row of the example above, which looks like this:

    ♦♦♦   ♦♦♦         ♦♦♦   ♦♦♦

  • You will probably want to copy your repeat function from the previous part and use it again!

  • Like before, you should not print out any newlines in the recursive carpet_row function, because this function has to be called (recursively) many times to produce a single row of the image.

    You still need to cout<<endl at the end of each line, but should do this outside of carpet_row.

More detailed explanation

He is a more detailed explain of how to think about the recursive function carpet_row, using the example of printing the 13th row of a width-27 carpet by calling carpet_row(27, 12).

Here is the image we are trying to produce, with this particular row highlighted in red, and with the 9 sub-regions outlined in blue:

So now we can see that this row (in red) needs to go through three parts:

  1. The fourth line of a 9x9 carpet, which we can draw by using recursion with carpet_row(9, 3)
  2. 9 blank spaces, which we can draw using the function you made from before with repeat(" ", 9)
  3. The fourth line of another 9x9 carpet, which will be another recursive call to carpet_row(9, 3)
Things to notice about this example:
  • The row index changed in the recursive call, from 12 to 3. We subtracted 9 in this case because row 13 of the original image corresponds to row 4 of the regions in the middle third.
  • The middle part of the row is empty. That is because we are in the middle third of the carpet according to the row index. If we were a row from the top third or bottom third, then there would be no empty middle part but three recursive calls instead.

The most important thing to remember is to use recursion - it's very powerful and will help your program stay simple! If you find your self writing many complicated if/else cases and very long functions, ask for help because you are probably going in the wrong direction.

A well-written recursive program will be nice and simple at the end, but it can be tricky and take lots of patience to get there. You will have to think hard about what you want the program to do, and then be very patient and thorough in debugging.

Part 5: Extra credit: The famous triangle

 The Sierpinski triangle is one of the most famous and beautiful fractal patterns. It consists of three half-height Sierpinski triangles (recursive!) arranged with an upside-down blank triangle in between them.

See on the left some example runs to show how your program should work.

For this program, you should use a triangle character to print the base case of a 1x1 triangle using this string:

"\u25b2"; // ▲

Print the inside spaces of the triangle with a dot character ".".

Similar to before, we will only perform auto-tests at power-of-two sizes like 1, 2, 4, 8, 16, 32, etc., but it might be fun to make your program work somehow for any possible size. Note that the size given is the height of the triangle your program should create; the width should be 2h-1.

I want you to work hard and figure this out, but here are a few hints:

  • I recommend making a recursive function 
    void triangle_row(height, row_index)
    to print out a single row a Sierpinski triangle as in the previous parts.
  • Function triangle_row() can ignore the leading whitespace letters but focus on the actual triangle contents. The leading whitespace letters in each row can be easily taken care of later using another function.
  • Hint: The top-half triangle is exactly halfway between the two bottom-half triangles, with dots on either side.