Fractals

A fractal is a pattern (often mathematically defined) that has the same general properties (shape, pattern, etc) regardless of how closely you look at it. In this assignment you will implement one of two simple fractals.

The Specs

Regardless of which fractal you implement, you will read in a desired "size" from the user. Then you will call your fractal function with that size and it will print out the appropriate fractal. Here is a description of the two fractals:

The Sierpinski Triangle

*
**
* *
****
*   *
**  **
* * * *
********
*       *
**      **
* *     * *
****    ****
*   *   *   *
**  **  **  **
* * * * * * * *
****************
The Sierpinski Triangle, shown above, can be explained several ways. Firstly, it can be seen as a series of small triangles 
*
**
* *
****
that are arranged into larger triangles. This is done recursively, so the middle (upside-down) triangle is always blank. This is somewhat tricky to implement this way, but can be done.

Another way of viewing the Sierpinski Triangle is by looking at its historical origin: it is actually Pascal's Triangle, except instead of numbers in each position, we render a "*" for each odd number, and a " " for each even number. Pascal's triangle looks like this: 
1
11
121
1331
14641
Each line begins with a "1", and every other value on that line is the sum of the value above it and the value above and to the left of it. However, you don't need the actual numbers for this fractal, you only really need to track whether a value is odd or even. If you want to implement the fractal this way, a function header like this vector<int;> oneLine(int line) is useful (this function can easily be written recursively, or iteratively.)

Given the user's input size, print out that many lines of the Sierpinski triangle.

Falling Square

*****************
*      * *      *
*     *   *     *
*    *     *    *
*   *       *   *
*  * ******* *  *
* *  * * * *  * *
**   **   **   **
*    *  *  *    *
**   **   **   **
* *  * * * *  * *
*  * ******* *  *
*   *       *   *
*    *     *    *
*     *   *     *
*      * *      *
*****************
This fractal has a more intuitive definition, but as a result lacks an elegant recursive solution (well, that we are aware of). This fractal is only well defined for sizes (widths of the square) that are 1 more than a power of 2 (3, 5, 9, 17, 33, etc.) For all other sizes, printing out an error message is appropriate.