CS 106 Winter 2018
Assignment 06: Recursion
Question 1 Pythagorean Tree
Imagine drawing a square. On the top edge of the square, arrange two more squares, tilted at 45 degree angles, so that they each touch one corner of the original square and meet above it, like this:
Now, keep doing the same thing: add four grandchildren, two squares on the tops of each of the two child squares. Add eight great-grandchildren, and so on to some predetermined number of levels. The theoretical limit of this process will be a kind of fractal known as a Pythagorean Tree.
Let's change the design slightly, so that instead of a square we draw a house-shaped pentagon that looks like a triangle glued onto the top of the square. (The triangle should correspond to the gap between the squares above, so that the angle at the peak of the roof is 90 degrees.) We'll glue child houses onto the sloped sides of the roof of each parent house. If we say that the "Level 0" drawing is just one such house, then the first seven levels of this process might look like this:
In the provided starter code, open the Tree sketch. The sketch manages the number of recursive levels for you—use the left and right arrow keys to decrease and increase the number of levels. Of course, in the starter code, nothing is drawn. Fill in the tree() function so that it draws a house-based Pythagorean tree that looks like the seven examples above. Here are some tips for doing so:
In the tree() function, always draw a house. Then, if the level is still greater than zero, make two recursive calls in scaled, rotated and translated geometric contexts that will force the child trees to be positioned relative to the sides of the roof of the "trunk" of the tree you just drew.
The scaling factor for children must be chosen to match the ratio between the length of the side of the roof and the length of the base of the house. That ratio is √2/2, or sqrt(2.0)/2.0 in code. Consider putting that value in a global variable as a kind of constant.
You'll need ideas from the "Advanced Shapes" module to draw a house. Keep in mind that you can define your house to have any coordinates you want (i.e., you can choose the side length of the square and the location of the origin). Think about choosing coordinates that make the recursive geometric contexts easier to figure out. Note also that you can impose a "master" geometric context in draw(). So for example, you can define the entire tree to grow out of the origin, and then translate the whole thing with a single call to transate() in draw(), just before the call to tree().
Notice that the outlines of the smaller houses are thinner. You don't have to worry about that. (You can try to give all houses uniform outlines if you want, but it's potentially tricky.) Notice also that the branches of the tree eventually start overlapping around Level 4. That's a fundamental property of this fractal, and again you don't have to worry about it.
As with many other recursive programs, completing this question requires more thinking than coding. You can get away with as few as 25–30 lines of code. If you're stuck, you might get some benefit from practicing drawing this fractal at recursivedrawing.com.
Save your finished sketch in your A06 folder with the name Tree.
Question 2 Mondrian
By Piet Mondrian - [1], Public Domain, Link
Piet Mondrian was one of the most important artists of the 20th century. His neoplasticism style contributed greatly to the growth of abstract art. Many paintings in this style use an extremely limited artistic vocabulary: horizontal and vertical black lines divide the canvas into rectangles, some of which are filled with red, yellow, or blue. In this exercise, we'll use recursion to create a sketch that replicates some of the appearance of Mondrian's work, in a limited way.
In the provided starter code, open the sketch titled Mondrian. You'll see a general structure not unlike that of the previous question, with a global number of recursive levels controllable with the left and right arrow keys. This sketch also redraws the sketch window at the current level if you press the space bar.
In this sketch the mondrian() function takes a number of parameters as input:
x, y, w, h: the same parameters that are used in the rect() function: define a rectangle inside of which the painting will be drawn.
horiz: a boolean variable determining whether the rectangle we're about to paint should be split horizontally (by a line running west-east) or vertically (by a line running north-south) in the case that there's still recursion to do.
current_levs: the number of recursive levels remaining until we hit the base case.
Complete the mondrian() function. You shouldn't have to change any other part of the sketch. Your function should work roughly as follows:
If you're in a base case (i.e., a level-0 painting), just draw the rectangle defined by the arguments passed in to the function. Use random numbers to choose the fill colour of the rectangle, so that most of the time the rectangle is white, but some smaller fraction of the time it can be red, blue, or yellow.
If you're in a recursive case, choose a random "split point". That will be a random y value between the top and bottom of the current rectangle if the horiz variable is true, and a random x value between the left and right of the rectangle if it's false. In either case, that split point will define two sub-rectangles of the initial rectangle. Call the mondrian() function recursively on those two sub-rectangles. In those recursive calls, the horiz variable should be the opposite of whatever it was in the current call, so that you alternate splitting horizontally and vertically at each level.
The diagram below shows a completed level-4 Mondrian painting in the upper centre, together with the tree of recursive sub-paintings that make it up. For example, the top-level painting is split vertically into the paintings to its immediate left and right. Click for a PDF. Note that because we always split in two, and we're doing this over four levels, the final painting will be made from 24 = 16 rectangles.
Note that there's no need to use geometric contexts to solve this problem. All the information about the "context" is embodied by the rectangle's corners. Don't use pushMatrix() or popMatrix().
The solution is likely to require about 20–30 lines of code, and a few calls to random() (which we'll talk about in great detail soon.
Save your finished sketch in your A06 folder with the name Mondrian.
Submission
When you are ready to submit, please follow these steps.
Please ensure that any sketches you submit compile and run. It's better to submit a sketch that runs smoothly but implements fewer required features than one that has broken code for all features. If you get partway into a feature but can't make it work, comment it out so that the sketch works correctly without it.
If necessary, review the Code Style Guide and use Processing's built-in auto format tool. You do not need to use the precise coding style outlined in the guide, but whatever style you use, your code must be clear, concise, consistent, and commented.
If necessary, review the How To Submit document for a reminder on how to submit to LEARN.
Make sure to include a comment at the top of all source files containing your name and student ID number.
Create a zip file called A06.zip containing the entire A06 folder with its subfolders Tree and Mondrian.
Upload A06.zip to LEARN. Remember that you can (and should!) submit as many times as you like. That way, if there's a catastrophe, you and the course staff will still have access to a recent version of your code.
If LEARN isn't working, and only if LEARN isn't working, please email your ZIP file to the course account (see the course home page for the address). In this case, you must mail your ZIP file before the deadline. Please use this only for emergencies, not "just in case". Submissions received after the deadline may receive feedback, but their marks will not count.