Write a program that plots a Sierpinski triangle, as illustrated below. Then, develop a program that plots a recursive pattern of your own design.

order 1	order 2	order 3	order 4	order 5	order 6

Part 1.   The Sierpinski triangle is another example of a fractal pattern like the H-tree pattern from Section 2.3 of the textbook. The Polish mathematician Wacław Sierpiński described the pattern in 1915, but it has appeared in Italian art since the 13th century. Though the Sierpinski triangle looks complex, it can be generated with a short recursive function. Your main task is to write a recursive function sierpinski() that plots a Sierpinski triangle of order n to standard drawing. Think recursively: sierpinski() should draw one filled equilateral triangle (pointed downwards) and then call itself recursively three times (with an appropriate stopping condition). It should draw 1 filled triangle for n = 1; 4 filled triangles for n = 2; and 13 filled triangles for n = 3; and so forth.

API specification. When writing your program, exercise modular design by organizing it into four functions, as specified in the following API:

public class Sierpinski {

    //  Height of an equilateral triangle whose sides are of the specified length.
    public static double height(double length)

    //  Draws a filled equilateral triangle whose bottom vertex is (x, y)
    //  of the specified side length.
    public static void filledTriangle(double x, double y, double length)

    //  Draws a Sierpinski triangle of order n, such that the largest filled
    //  triangle has bottom vertex (x, y) and sides of the specified length.
    public static void sierpinski(int n, double x, double y, double length)

    //  Takes an integer command-line argument n;
    //  draws the outline of an equilateral triangle (pointed upwards) of length 1;
    //  whose bottom-left vertex is (0, 0) and bottom-right vertex is (1, 0); and
    //  draws a Sierpinski triangle of order n that fits snugly inside the outline.
    public static void main(String[] args)
}

Restrictions: Do not change either the scale or size of the drawing window.

Examples. Below are the target Sierpinski triangles for different values of n.

	% java-introcs Sierpinski 1	% java-introcs Sierpinski 2	% java-introcs Sierpinski 3

Fractal dimension (optional diversion).   In grade school, you learn that the dimension of a line segment is 1, the dimension of a square is 2, and the dimension of a cube is 3. But you probably didn't learn what is really meant by the term dimension. How can we express what it means mathematically or computationally? Formally, we can define the Hausdorff dimension or similarity dimension of a self-similar figure by partitioning the figure into a number of self-similar pieces of smaller size. We define the dimension to be the log (# self similar pieces) / log (scaling factor in each spatial direction). For example, we can decompose the unit square into 4 smaller squares, each of side length 1/2; or we can decompose it into 25 squares, each of side length 1/5. Here, the number of self-similar pieces is 4 (or 25) and the scaling factor is 2 (or 5). Thus, the dimension of a square is 2 since log (4) / log(2) = log (25) / log (5) = 2. We can decompose the unit cube into 8 cubes, each of side length 1/2; or we can decompose it into 125 cubes, each of side length 1/5. Therefore, the dimension of a cube is log(8) / log (2) = log(125) / log(5) = 3.

We can also apply this definition directly to the (set of white points in) Sierpinski triangle. We can decompose the unit Sierpinski triangle into 3 Sierpinski triangles, each of side length 1/2. Thus, the dimension of a Sierpinski triangle is log (3) / log (2) ≈ 1.585. Its dimension is fractional—more than a line segment, but less than a square! With Euclidean geometry, the dimension is always an integer; with fractal geometry, it can be something in between. Fractals are similar to many physical objects; for example, the coastline of Britain resembles a fractal; its fractal dimension has been measured to be approximately 1.25.

Part 2.   In this part you will create a program Art.java that produces a recursive drawing of your own design. It must take one integer command-line argument n that controls the depth of recursion. It must stay within the drawing window when n is between 1 and 7. It can be a geometric pattern, a random construction, or anything else that takes advantage of recursive functions. For full marks, it must not be something that could be easily rewritten to use loops in place of recursion, and some aspects of the recursive function-call tree (or how parameters or overlapping are used) must be distinct from the in-class examples (HTree, Sierpinski, NestedCircles, Brownian).

Additional requirements: Your program must be organized into at least three separate functions, including main(). All functions except main() must be private.

Restrictions: Do not change the size of the drawing window (but you may change the scale).

Submission.   Submit Sierpinski.java and Art.java. Do not add sound to either file. If your Art.java requires any supplementary image files, submit them as well. Finally, submit a readme.txt file and answer the questions therein.

Challenge for the bored.   Write a program that plots Sierpinski triangles without using recursion.