CS 106: Lab 07

CS 106 Winter 2016

Lab 07: Recursion

Due: Friday, March 4th, 4:00pm

Starter code: None

Question 1 Wheels Within Wheels, Part I

Write a sketch that draws the picture above, in a window of size 500×500. The picture has a recursive structure: at every level we draw a circle. If we're not done yet, we recursively fill it with four smaller copies of the design at the next lower level. (If your final design is a rotated version of this one, don't worry; the important thing is to get the nesting pattern correct.)

There's one messy mathematical aspect of this diagram: the size of four smaller circles contained within their parent circle. You can use the following code to figure that out:

int N = 4;
float s = sin( PI / N );
float scaling_factor = s / (s + 1);

Once you define those constants, you can set up nested geometric contexts that use the scaling factor, combined with suitable translations and rotations (similar to the Dancers and Carousel exercises). Make sure to set up the translations so that the four circles touch each other and reach exactly to the edge of the enclosing circle.

You must also support two key controls: use the "-" and "=" keys to decrease and increase the number of recursive levels drawn in the picture.

I suggest that you base your code on the structure of the Gasket1 sample sketch. There will be two main differences to the drawTriangle() function (which you should rename!):

You should always draw a circle at every recursive level. The current drawTriangle() function draws a triangle only in the base case.
Use a for loop to make the four recursive calls. In each pass through the loop, set up a geometric context and make the appropriate recursive call.

When figuring out your solution, it's best to work at recursive Level 1, which should look like a single large circle with four circles inside of it. Once you get Level 1 working correctly, all the other recursive levels should "just work".

Save your work as a sketch entitled FourWheels.

Question 2 Wheels Within Wheels, Part II

The fractal construction above isn't restricted to a wheel containing four wheels—each circle can contain any number of child circles. In fact, if you change N in the code provided above, the resulting scaling_factor will tell you the new scale to use to fit a different number of child circles into their parent.

Even better, you can use a different number of child circles at each recursive level, creating lots of new design opportunities. Let's assume that we'll always draw a single large outer circle, and that each element in an array of integers will determine the number of children of every circle at the level before it. An empty array (of size zero) will produce a single circle. Here some examples using non-empty arrays. Click on the image to view a scalable PDF version.

It turns out that you can modify a solution to the previous question to create a solution to this one. Proceed as follows:

Change your recursive function so that instead of taking a single integer as input (the number of recursive levels), it takes two inputs: an array of integers (like the ones in the image above) and an index into that array.
Now, the base case occurs when you've run out of array to draw; in other words, check for the base case by checking whether the index passed into the function is beyond the final element in the array.
When you make a recursive call, you pass in the same array, but add one to the index.
Of course, you need to base the drawing process on the elements in the array. In your recursive function you need to compute a local scaling_factor based on the current array element, and change the number of times you loop to make recursive calls.
Define a global variable with an array that looks good to you. Make sure it has at least three elements, and that it's not just all fours (since that would be identical to the first exercise).
Feel free to experiment with enhancements. You don't need to fill the circles with different colours (as I did above), but you can. You can also try making the wheels rotate at every level.

The changes above are actually fairly quick once you get the hang of recursion. You probably won't need to change more than about 5–10 lines of code in FourWheels to make it work.

Save your work as a sketch entitled ArrayWheels.

Submission

Remember to review the Code Style Guide and use Processing's built-in auto format tool. Then review the How To Submit document. At the top of all of your source files, be sure to include a comment with your name and student ID number. When you're ready, zip up the entire L07 folder, which contains the FourWheels and ArrayWheels sketches, and upload the file L07.zip to LEARN.