Ref #2: What’s a Fractal

Draw your own fractals with my fractal drawing software, TWM Fractals.  With the new “Animate” feature, you can watch as your fractals iterate before your very eyes!  (It’s quite entertaining.)  Click the link to download.  (It requires java JRE.  I’m not really sure which version, but as long as it’s not super old, it should work.)

In geometry, a fractal is the infinite iteration of a recursively defined figure.  That is, it is a figure whose sides are defined recursively and iterated to infinity.  A simple example of a fractal it Koch’s Snowflake .  Koch’s Snowflake is a geometric fractal based around an equilateral triangle.

The algorithm for turning such a triangle into a fractal is as follows:  subdivide each side into four equal parts such that, in the middle of each side, a triangle protrudes that is similar to the original, only missing one side. It will look like this:

Once this is completed, the figure is said to have undergone one iteration.  Now we repeat the process for each side, include those newly formed sides:


and so on to infinity…

Once the figure has been iterated to infinity, it is considered a fractal.  This means that every part of its perimeter has the exact same structure (while some parts are smaller and others larger).  Fractals are often considered to be fraction-dimensional figures.  This is because, in any integer dimension, an infinite sum of infinitesimal parts (that is, 0over0) is an integral, which always has a finite solution.  But in the case of a fractal, we have an infinite sum of infinitesimal parts (still 0over0) that has an infinite solution.  This means that the perimeter of Koch’s flake has an infinite length (as each iteration increases the length by a factor of 4/3).  This is because the order of infinity that describes the number of sides is higher than the order of inverse infinity that describes the length of each side.  It is often thought of as a paradox that a figure, such as a fractal, can have a finite area but infinite perimeter and an infinite perimeter made only of infinitesimals.

Ref #1: What’s Recursion

It was recently brought to my attention, thanks to the much appreciated input of a commenter that not everyone reading this blog knows what a fractal is.  As I began to think about how to explain the concept, I started to realize that there may be many such topic that I frequent in my writings that readers are unfamiliar with.  Although I try to give enough background information within each post, perhaps that is not always entirely sufficient.  Therefore, I have decided to create a series of “reference posts” explaining various such things for the sake of increasing the overall accessibility of this site.

Recursion: see recursion.

On its basic level, a recursive algorithm is an algorithm that is somehow defined relative to the same system it is creating.  For example, one might define a geometric sequence recursively as follows:

A1 = 2

An = A(n-1) * 2

This definition would produce the following sequence:

2, 4, 8, 16, 32, 64 … 2^n

In this sequence, I have defined each term relative to the term before it with the exception of the first term which I have given a set starting point.  Since each term is found by doubling the previous term, the overall sequence can be said to be recursive because each part of the sequence is defined relative to another part of the same sequence, and so, more generally, the sequence is defined relative to itself.

Recursion is, however, a broader concept than this and can extend beyond the world of simple algebra.  In fact, recursion can be found all over nature.  A simple example is when two mirrors are held so that they reflect each other.  One ends up with the image of a mirror inside a mirror inside … This is because the image on the mirror is defined relative to itself.

Another simple example of recursion is proof by induction.  In a proof by induction, one proves that an algebraic expression of n is equivalent to each respective term of a sequence by plugging it in recursively.  I will use the same geometric sequence above as an example:

Prove: if   A1 = 2  &  An = A(n-1) * 2  then  An = 2^n

2, 4, … A(n-1) * 2 = An

Assume: An = 2^n

2, 4, … A(n-1) * 2 = 2^n

∵  (2^n) * 2 = 2^(n + 1)     ! plug-in 2^n for the sequence on the left and apply the algorithm

!of multiplying by two to find the next term.  See if that is equal

!to the definition one the right incremented by one.

(2^n) * (2^1) = 2^(n + 1)

2^(n + 1) =  2^(n + 1)

Q.E.D.

Another example of recursion is the algorithm used by a scientific calculator to parse a formula into a computable expression.  That is, if I enter the expression

3 *2+4*3*2 +2

into a scientific calculator, it solves it recursively.  It might, for example, have an evaluate method that takes the first number and applies to it the solution of the rest of the expression (which it finds using the same evaluate method) using the given operation.  If you are familiar with computer science, the code might look something like this (in summary):

double evaluate(String expression){

if(getFirstOperation(expression) == MULTIPLICATION)

return getFirstNumber(expression) *  evaluate(getRestOfExpression(expression))

+ evaluate(getExpressionAfterFirstPlus(expression));

else if(getFirstOperation(expression) == ADDITION)

return getFirstNumber(expression);

//the code would be written a little differently

//inorder to accommodate for other cases

// this is merely an example that would solve

//the above problem

}

Recursion can also be thought of more generally as any process that references itself.  For example, phycology might be considered recursive because it is using the mind to study itself.  Recursion occurs in levels (see “Levels of Recursion”) or iterations.  Every time a recursive algorithm is completed, the system is said to have undergone one iteration or advanced one level of recursion.

Google has a pretty funny joke about recursion.