Recursion exercises

Fractals

Drawing simple fractals is a good exercise since it combines recursion with some program state: depending on the fractal and the drawing method used, you need to keep track of (and perhaps directly manipulate) the position of the cursor, and possibly the drawing angle.

Exercise 1 Koch curve. Write a program (similar to the box fractal drawing done in class) that draws the Koch curve, as described here.
Hints: There are two differences with respect to box fractal program. First, you can draw the Koch curve in one go, without "lifting the pen". Every segment starts where the previous left off. Thus, you will not need "move" commands, only "draw" commands.
Second, the angles for drawing each subfigure of the box fractal were independent. In the Koch curve, a subfigure/segment is drawn at an angle that depends on its position in the larger figure: the first and last subfigure are drawn at the same angle as in the larger figure, the second and third one are drawn at angles ±π/3.

Exercise 2 Fractals as L-systems. Fractals can be expressed using grammars or rewriting systems (the same formalism used to describe programming language syntax).
Write a program that draws a fractal described as an L-system (for instance, the dragon curve, or the Koch curve or Sierpiński triangle defined using segments).
Hints: Have a parameter that says how many times the rules are expanded. You can hardcode the functions that map a character into the final drawing commands, but you should write a function that can expand any rules. Make a table of rules (strings) indexed by uppercase letter.

Marius Minea
Last modified: Thu Feb 19 8:45:00 EET 2015