## How to Generate the Sierpinski Triangle

This tutorial explains how to generate or draw the Sierpinski Triangle, with a computer program.
This is a detailed step-by-step guide, with multiple examples.
The provided explanations are valid for generating the Sierpinski Triangle in any programming language.

The Sierpinski triangle is an intriguing, hollow triangle shape, that has
a fractal nature. The fractal and recursive properties of the Sierpinski triangle
are best understood through the concept of self-similarity: the smaller parts of
the Sierpinski triangle look exactly like the entire triangle.
As such, the Sierpinski triangle can be best described in a recursive manner:
the shape of the Sierpinski triangle is made of three smaller Sierpinski triangles,
and each of those three is made of three smaller Sierpinski triangles,
and each of those three is made of three smaller Sierpinski triangles, etc...

While Sierpinski triangles were used as decorative patterns a long time ago,
afterwards they were named after the Polish mathematician Waclaw Sierpiński.

### Let's Draw the Sierpinski Triangle

To start drawing the Sierpinski triangle, the positions of three points that are
the triangle's vertices need to be known. The positions of the three points can be given
by coordinates.

In the source code, the coordinates of three vertices of a triangle
are given by the first three statements.
The next statement draws an ordinary blue triangle between the given vertices.

[Run the program by clicking the 'Run' button]

Each of the triangle's vertices p1
, p2 , p3
can be painted in a different color.
The top one is painted red, the left one is orange and the right one is painted cyan.
This is accomplished by the last three statements of the source code.

[Run the program]

[Click on the 'Next' button (on the page top) to read the next page,
or press the F4 key]

## 2. The Three Inscribed Triangles

The next step of generating the Sierpinski triangle is to draw three inscribed
smaller triangles. Each of the three inscribed triangles can use the same color
as the vertice it is touching.

[Run the program by clicking the 'Run' button]

For drawing the three smaller triangles, the mid-points of
each side of the big triangle need to be computed. In the source code, the mid-points are
named mid12 , mid13 , mid23 .
Each of the three mid-points is later visualized in a different color (purple, azure and olive).

[Run the program]

The three inscribed triangles are visualized in colors red, orange, and cyan.
Those colors match the color of the vertice that each of the inscribed triangles is touching.

Since ZedLX doesn't have a built-in function for calculating mid-points,
a user-defined function MidPoint is provided at the
end of the source code. There are many possible implementations of this function.
The source code provides three implementations, where only the last one is actually
used in this program.

## 3. A Function for Drawing

The most common way to generate the Sierpinski triangle is by using functions.
To create a function that generates the Sierpinski triangle, the code from the previous page only
needs to be slightly reorganized to form a function.

The function SierpinskiTriangle created in such a manner still
won't really draw a Sierpinski triangle, but it is an important step in writing the correct function.

[Run the program by clicking the 'Run' button]

The real function that generates the Sierpinski triangle must be a recursive function.
Recursive functions are not easy to write, so it is a good idea to use some intermediate steps
in the process of writing a recursive function.

[Run the program]

Notice that it is required to actually rename all the points inside the
SierpinskiTriangle function. All the vertices and mid-points now
use slightly different names compared to the previous page, where indices 1, 2 and 3 have
now been replaced by the letters A, B and C.

The last change is to perform a call of the SierpinskiTriangle function.
The call is made at the place in the source code where previously the blue triangle was displayed.
The new call to the SierpinskiTriangle function features an
unused argument of value 4, called the level, which will be required in the next improvement of this program.

## 4. Writing a Recursive Function

The hardest step of writing a recursive Sierpinski triangle function is, of course,
the recursion. The recursion can be very mind-boggling, so it is usually the
best to stick to some good old rules.

A rule, and a very important insight, is that every recursive function must have an atomic case,
triggered by the stopping condition. Otherwise, the recursion would continue indefinitely.

### The Atomic Case of Recursion

The actual stopping condition can be something practical, of our choice.
In the provided source code, the atomic case is triggered when
level falls down to 0, which is the stopping condition.

So, what is the atomic case for generating the Sierpinski triangle? Obviously, it is a single triangle.
Therefore, a single triangle should be drawn when the stopping condition is reached.
The provided source code draws that single triangle in the pink color.

It is also important to remember to exit the function in the atomic case,
as that is the main point of the atomic case.
The return statement exits the function.
In recursive functions, it exits from only one level of recursion, not from the entire call tree.

The entire source code of the atomic case is provided at the beginning of the
SierpinskiTriangle function.

### Adding the Recursive Case

Writing just the atomic case is not sufficient to make a function recursive.
The second required change, compared to the previous page, is that recursive calls
have to be performed inside the recursive function.
In the source code, the correct recursive calls are now stated,
which results in an image that already looks a lot like the Sierpinski triangle.

[Run the program]

The recursive case of the SierpinskiTriangle function
is everything not belonging to the atomic case.
Obviously, any recursive case must contain recursive calls.

When writing the three recursive calls that draw the inscribed Sierpinski triangles,
the level needs to be provided as an argument instead of the color.
In order to prevent the recursion from running indefinitely,
all recursive calls must end in an atomic case in a finite number of steps.
To guarantee finiteness, the level
gets reduced by 1 on each level of recursion. Therefore,
the level will eventually fall down to zero (from the initial value of 4),
which will then trigger the stopping condition.

Compared to the previous page, the drawings of the three inscribed ordinary triangles
have simply been replaced by drawings of the three inscribed Sierpinski triangles.
With such a simple change, the program already works well.
The recursion always works in surprising and magical ways.

[Run the program]

## 5. Cleaning up the Sierpinski Triangle

The drawing of the Sierpinski triangle must now be cleaned up, compared to
the image produced by the previous page.

[Run the program]

The first change was to remove the drawings of
mid-points midAB
, midAC , midBC , which were previously
shown in purple, azure and olive colors. While mid-points
must be computed, they don't need to be displayed,
as they are making the final image much worse.
Now that the drawings of mid-points have been removed, the Sierpinski triangle can be clearly seen,
painted in the pink color.

[Run the program]

On the next page, the depth of the Sierpinski triangle is increased.

## 6. Increasing the Depth of the Sierpinski Triangle

The number of levels of the Sierpinski triangle is now increased to 6, by the last argument
of the call to the user-defined function SierpinskiTriangle.
It is an increase by two compared to the image produced by the previous page.

[Run the program]

The color of the Sierpinski triangle has been changed to periwinkle.
Also, there is no more need to visualize, in three colors, the three
vertices p1
, p2 , p3 of the big triangle,
so the drawing statements have been removed compared to the previous page.

[Run the program]

If you like this tutorial, you can use the gray sharing buttons to share it with your friends.
The sharing buttons create a link to the current page.
The buttons for Twitter, Facebook, Pinterest, Reddit and LinkedIn are provided.

On the next page, the selection of colors is made easier.

## 7. Coloring the Sierpinski Triangle

The Sierpinski triangle is now displayed in completely different colors,
compared to the image produced by the previous page.

[Run the program]

The clearScr function allows a default background color
and a default drawing color to be provided. It enables both colors to be specified in the single line of the
source code. In the source code, the single call to the function trianglep
does not specify an explicit color anymore, which makes it use the default drawing color.

Compared to the previous page, the number of levels has been increased to 7.
As the number of levels of the Sierpinski triangle is being increased, the triangle
will actually become thinner and thinner. With a sufficiently high number of levels,
the entire triangle would disappear, as the Sierpinski triangle has a total area of zero.
At the same time, it has infinite sum of all edge lengths.
It is an extraordinary shape, indeed.

[Run the program]

On the next page, RGB triplets are used for coloring the Sierpinski triangle.

## 8. Coloring by RGB Triplets

The drawing of the Sierpinski triangle is now in gold color on a blue background,
which looks very different than the image produced by the previous page.

[Run the program]

ZedLX allows colors to be given by RGB triplets inside the square brackets.
It is important to note that the three RGB color components must be given as linear values
in range of 0 to 100, as the data type 'color' in ZedLX is defined that way.
The colors are then converted to the sRGB color space as they are displayed.

The number of levels of Sierpinski triangle is still 7, therefore it has not been increased.
There is not much point in increasing the level further, as the drawing is
quickly approaching the maximum resolution of the output image.

[Run the program]

On the next page, we examine the level of detail of the Sierpinski triangle.

## 9. Depth of Recursion

We now present a quick image sequence of a Sierpinski triangle with
increasing depth of recursion. The depth of recursion equals the level of detail.

[Run the program]

At any iteration of the main for loop, the level of detail is equal to
the value of the loop's variable i.
The level of detail starts from 0, ends at less than 9, and it is increased by one
in each iteration of the loop. Each iteration lasts about one second, which is
ensured by the call to the sleepMs function.
This function produces a pause, where the argument is in milliseconds.

The end result is that a sequence of images is produced, showing the effect of increasing
levels of detail of the Sierpinski triangle.

If you like this tutorial, you can use the gray sharing buttons to share it with your friends.
The sharing buttons create a link to the current page.
The buttons for Twitter, Facebook, Pinterest, Reddit and LinkedIn are provided.

## 10. Animating the Sierpinski Triangle

We now present an animation of a rotating Sierpinski triangle, displayed in the gold color
on the dark blue background.

[Run the program]

The usual facilities for animating objects in ZedLX have been employed.
It is very easy to add animation to ZedLX programs. The source code shows the
facilities employed to create this animation:
vertical synchronization, clear screen, current time, and vector arithmetic with rotations in degrees.
[Run the program]

With this page, we complete our tutorial on drawing the Sierpinski triangle.
Click on the 'Articles'
button at the top to select another article.
We also suggest taking a peak into our main 'Gallery' of programs,
and taking a look into 'Overview'
of our main programming tutorial for beginners.
Have fun!