Recursion and Fractals
Recursion is the process of repeating items in a self-similar way. It can be implemented in Scratch by making a Custom block that runs itself. This can be used to create Fractals.
A fractal is pattern that produces a picture, which contains an infinite amount of copies of itself. Some well-known specimens are the Mandelbrot set, the Sierpinski Triangle (also, but less commonly known as the Sierpinski Gasket), and the Koch Snowflake.
Creating the Koch Curve
The Koch Curve is a fractal that can be created relatively easily in Scratch. It is a piece of the larger fractal, the Koch Snowflake.
Understanding Recursion in the Koch Curve
The Koch Curve is made of four Koch Curves that are a third of the size of the original Koch Curve. They are they are arranged so that the first and fourth are flat and the middle two point up to make an equilateral that is triangle missing one side.
To make it easier to draw, the Koch Curve can be broken down into iterations, each one more complicated than the last. The first iteration is made up of four straight lines. The second iteration contains four copies of the first iteration. The third iteration contains four copies of the second iteration or sixteen copies of the first iteration. As iterations are added it gets more complicated and looks more and more like the real Koch Curve.
Basic Pen Path without Recursion
The triangle in the center is an equilateral triangle, therefore each of its angles have a measure of 60°.
Using basic geometry the angles of the rotations the sprite must make can be found.
Using this these angles, a script can be created that draws the first iteration of Koch Curve. Since each line segment is 1/3 the total length of the Koch Curve, the sprite should move 1/3 of the length given each time.
Adding Recursion
To add recursion, instead of drawing a line, a smaller Koch Curve can be drawn. When each iteration above one is drawn, it contains four smaller Koch Curves that are one iteration less than it self. For example, when drawing the second iteration you must draw four copies that are 1/3 the size of the first iteration. When the program gets to the first iteration it must draw straight lines. The following code will make the fifth iteration of the Koch Curve:
Creating the Mandelbrot Set
The Mandelbrot set is a mathematical fractal defined in the complex plane. It is completely self-similar, meaning that it repeats over and over as one zooms in. The Mandelbrot set was named after its discoverer, Benoit Mandelbrot, and has many close relationships to the Julia Sets.
Understanding the Definition
In its definition, the Mandelbrot uses complex numbers. A complex number is the sum of a real number and an imaginary one, with an imaginary number simply being the square root of a negative number. Since that can not be taken, the square root of -1 is assigned the value i. For example, 3+3i is a complex number.
The Mandelbrot set is defined as all c values in the complex plain which are bounded under iteration in the following equation:
zn + 1 = zn2c
First, one starts with a z value of c (i.e. z1 = c). Then, when one puts that z back into the equation, it becomes z^2+c. That z is then taken and put back through the equation over and over. This is called iteration.
For example, let c=1. The value z then becomes 1. Once 1 is put back into the equation, the equation becomes 1^2+1, which equals 2. Once 2 is put back in, it becomes 2^2+1, or 5. Once 5 is put back in, it becomes 26. That sequence escapes to infinity and therefore c=1 is not part of the Mandelbrot set. Meanwhile, the sequence c=-1 gives 0, -1, 0, -1, 0, ect..., is bounded and so belongs to the Mandelbrot set.
It has been proven that if any sequence contains a complex value that is outside a distance of 2 from the origin, it will escape to infinity.
Coloring
In a basic Mandelbrot set, white is used for a c-values that escape to infinity and black is used for all c-values that do not. This would be the actual Mandelbrot set.
In most Mandelbrot sets, though, colors are used to help depict the Mandelbrot set or make it more art-orientated. Colors are not defined through an equation, but rather through the last iteration before escaping a distance of two from the origin. The iteration is then assigned a color of the creator's preference. Color can also apply to the rate of the equation reaching infinity.
Creating the Variables
Due to the fact that Scratch does not directly support mathematics in the complex plain, a simple workaround has to be used. Each complex number will be defined as two variables, the real part, and the complex part. And since there will be operations based on the complex numbers, two complex numbers will be needed, or four variables. For the tutorial, these names will be used:
Along with that, a variable Best Fit will be used to figure out the color to be used when coloring a complex value:
Coding
To start, a base of clones is needed to render a full screen due to the computing power needed to render the Mandelbrot set:
Next, it is important to give the clones a skeleton:
Although this is a functional script, it will take a while to render. For speed preferences, a custom block will be inserted:
As noted above, it is important that the custom block "forced iteration" runs without a screen refresh or else all the benefit of extra speed will be lost.
Anyway, now that that is coded, a skeleton will be created for sampling a point and figuring out whether or not it is part of the Mandelbrot set:
Now here is where the mathematics of the Mandelbrot set comes into play. In the Test for Legibility custom block, someone has to take a complex number, apply the equation which defines the Mandelbrot set, and repeat if it is still within a distance of 2 from the origin:
Up above, it may be noticed that the repeat continues until the complex number is found not to be part of the Mandelbrot set, or until it has iterated 20 times. That 20 can be changed to whatever one wants, with higher numbers producing higher quality; though the higher the number, the more lag will be caused.
To complete the Mandelbrot set, colors need to be implemented:
Those colors may be changed to one's wishes.
Final Product
In the end, this is all the code used to draw the Mandelbrot set (scroll to see all of the code):
Julia Set
The Julia set is a series of equations that are mathematical fractals, and that is defined very similarly to the Mandelbrot set. The official equation is:
ƒc(z) = z2 + c
The only difference in its definition from the Mandelbrot set is that c is no longer a point in the complex plane, but rather a complex parameter, which is consistent whichever point you pick. Also, z1 is defined as being the point you pick in the complex plane. The technique above for rendering the Mandelbrot set may be used here again, with the required changes.
