Compsci 6/101, Fall 2011, Lab 10, Re[gex|cursion]

In recitation/lab this week we will practice with regular expressions and recursion.

Regular Expressions

This reading is useful to give you some more details and examples and this page provides a summary of regular expressions.

Recursion

Snarf the code for this lab or view it online here. It generates a Sierpinski triangle fractal.

The Sierpinski triangle is a fractal because it is a geometric shape that can be split into parts, each of which is (approximately) a reduced-size copy of the whole. In a sense, this is similar to recursion because each successive call to the function works on a reduced copy of the problem. Thus recursion is a natural choice when generating fractal images.

An algorithm for obtaining arbitrarily close approximations to the Sierpinski triangle is as follows:

1. Draw a triangle.
2. Shrink the triangle to ½ height and ½ width, make three copies, and position the three shrunken triangles so that each triangle touches the two other triangles at a corner. Note the emergence of the central hole - because the three shrunken triangles can between them cover only 3/4 of the area of the original.
3. Repeat step 2 with each of the smaller triangles for as long as desired.

Complete the function sierpinski by completing the three recursive calls to generate the pictures above.