Fractals:  Recursion Made Visible

Recursive Turtle Programs

Our goal here is to study fractals, weird shapes that are exactly the same at every level of detail.  We begin by introducing some turtle programs for simple shapes.  Then we go on to study techniques for writing recursive turtle programs to generate fractal curves.

Turtle Global Variables:  Location and Direction

init:=Module[{},position ={0,0};direction={1,0}; turtlepath={}]

Turtle Commands:  Forward, Turn, and Resize

forward[dist_]:=Module[{oldposition=position},position=oldposition + dist(direction);AppendTo[turtlepath,Line[{oldposition,position}]]];



move[dist_]:=position=position + dist(direction)


turn[angle_]:=direction=N[ direction .(({{Cos[angle Degree], Sin[angle Degree]}, {-Sin[angle Degree], Cos[angle Degree]}}))]


resize[scalefactor_]:=direction=N[ direction .(({{scalefactor, 0}, {0, scalefactor}}))]


turnANDresize[angle_,scalefactor_]:=direction=N[direction .(({{scalefactor Cos[angle Degree], scalefactor Sin[angle Degree]}, {- scalefactor Sin[angle Degree], scalefactor Cos[angle Degree]}}))]

Turtle Display

displayturtlepath[shape_]:=Show[Graphics[{Thickness[.004],turtlepath}],Axes->False,AspectRatio->Automatic,PlotRange->All]

Polygons and Stars

maketriangle[size_]:=Do[forward[size];turn[120],{3}];

makecircle[size_]:=Do[forward[size];turn[1],{360}];

makestar[numsides_]:=Do[forward[1];turn[720/numsides],{numsides}];

makepoly[numsides_]:=Do[forward[1];turn[360/numsides],{numsides}];

makepolyORstar[size_,angle_]:=Do[forward[size];turn[angle],{100}];

Shift, Spin, and Scale

shift[program_,parameterList_,n_,dist_]:=Do[Apply[program,parameterList];move[dist],{n}];

spin[program_,parameterList_,n_]:=Do[Apply[program,parameterList];turn[360/n],{n}];

scale[program_,parameterList_,n_,scalefactor_]:=Do[Apply[program,parameterList];resize[scalefactor],{n}];

Fractals -- Recursion Made Visible

What are fractals?  One informal definition is that fractals are simply recursion made visible.   Here we will write simple recursive turtle programs to generate several interesting kinds of fractals, including gaskets, snowflakes, and general bump fractals.

Gaskets

The first type of fractal we shall investigate is called a gasket.  Below is a picture of the Sierpinski gasket.
					
How do you write a turtle program makesierp to generate the Sierpinski gasket?  Don't panic.  You don't have to give the turtle thousands of forward and turn commands to generate this figure.  A simple recursive program will do the job.
The key observation is that the big gasket is made up of three identical smaller gaskets.  Conceptually this gasket is almost the same as a spiral.  A spiral is a line joined to a smaller spiral.  A Sierpinski gasket is just three smaller Sierpinski gaskets joined together.  Again this definition of a gasket would be circular, if we did not have a base case at which to stop.  So we say that a very small gasket is just a small triangle.
The structure of the makesierp program must be something like the following:
	To make a large gasket, 
		Make a smaller gasket at one of the corners.
		Then move to another corner and make another small gasket.
		Then move to another corner and make another small gasket.
		Then return to the turtle to its starting position.
The moves can be made with move and turn commands;  the rescaling is achieved with resize commands.  To make the smaller gaskets require three recursive calls to the makesierp program.  Form follows function!   By the way, why do you think you have to return to the turtle to the state in which it started?
Below is the Mathematica program for makesierp.  It's short and simple.

Clear[makesierp];

makesierp[level_,numsides_]:=If[level==0,makepoly[numsides],Do[resize[1/2];makesierp[level-1,numsides];resize[2];move[1];turn[120],{3}]]

Manipulate[Module[{},init;makesierp[level,sides];Graphics[{Thickness[.004],turtlepath}]],{level,{0,1,2,3,4,5,6,7}},{sides,{3,4,5,6}},TrackedSymbols:>{level,sides}]

Snowflakes

Snowflakes make interesting fractals.  Below is the fractal known as the Koch snowflake.  Notice its sixfold symmetry.  This curve has the amazing property that it is continuous everywhere, but differentiable nowhere.  That is, the Koch snowflake is pointy at every point on the curve.  You are going to generate the Koch snowflake using your turtle.

There is a simple trick for generating the Koch snowflake and other snowflakes as well.  Consider the following simple bump:  

To generate one side of the Koch snowflake, replace every line in this figure by this bump, scaled to 1/3 its size.  Now you have:

Repeat this process again and again until the bumps are very small --  that is, replace each line by a bump 1/3 the size of the line.  This procedure builds 1/3 of the Koch snowflake.


How do you generate the code makekoch for this part of the Koch snowflake.  Easy.  There are four recursive calls.
	To make a large snowflake, 
		Make a smaller snowflake along one of the edges of the original figure.
		Then move to the next edge and make another small snowflake.
		Then move to the next edge and make another small snowflake.
		Then move to the last edge and make another small snowflake.
Below is the Mathematica program for  makekoch.  Notice that the base case is simply a straight line.  (To begin, we replace the straight line with a bump.)

makekoch[level_]:=If[level==0,forward[1],resize[1/3];
makekoch[level-1];turn[60];makekoch[level-1];turn[-120];makekoch[level-1];turn[60];makekoch[level-1];resize[3]]

Manipulate[Module[{},init;makekoch[level];Graphics[{Thickness[.004],turtlepath}]],{level,{0,1,2,3,4,5,6}},TrackedSymbols:>{level}]

Now we can write a program makekochsnowflake that uses the makekoch program to generate the complete Koch snowflake by placing a Koch bump on each edge of a triangle.

makekochsnowflake[level_]:=Do[makekoch[level];turn[-120],{3}]

init;
displayturtlepath[makekochsnowflake[5]]

Fractal Trees

We can also generate somewhat realistic looking trees using fractal turtle programs.   To make the following tree, first make the tree trunk, then make the left subtree, then make the right subtree, and return the turtle to its initial state.

Clear[makeTree];

makeTree[level_,angle_]:=If[level==0,forward[1];forward[-1],
forward[1];turn[-angle];resize[4/5];makeTree[level-1,angle];turn[2 angle];makeTree[level-1,angle];turn[-angle];resize[5/4];forward[-1]]

Manipulate[Module[{},init; turn[90];makeTree[level,angle];Graphics[{Thickness[.004],turtlepath}]],{level,Table[k,{k,0,8}]},{angle,Table[k,{k,30,120,10}]},TrackedSymbols:>{level,angle}]

More Fractals

Hangman

Clear[makehangman];

makehangman[level_]:=If[level==0,turn[0],resize[1/2];makehangman[level-1];forward[1];makehangman[level-1];forward[1];turn[90];forward[1];makehangman[level-1];turn[180];forward[1];turn[-90];resize[2];forward[1];turn[180]]

Manipulate[Module[{},init; makehangman[level];Graphics[{Thickness[.004],turtlepath}]],{level,Table[k,{k,1,7}]},TrackedSymbols:>{level}]

Clear[makeflower];

makeflower[level_]:=If[level==0,makepoly[6],Do[resize[1/3];makeflower[level-1];resize[3];move[1];turn[60],{6}]]

Manipulate[Module[{},init; makeflower[level];Graphics[{Thickness[.004],turtlepath}]],{level,Table[k,{k,1,7}]},TrackedSymbols:>{level}]

Pascal's Triangle

binomialTable[size_]:=Table[Mod[Binomial[n,k]+1,2],{n,size,0,-1},{k,0,size}];

MatrixForm[binomialTable[5]]

Manipulate[Module[{binomialTable=Table[Mod[Binomial[n,k]+1,2],{n,(2^depth),0,-1},{k,0,(2^depth)}]},Graphics[Raster[binomialTable]]],{{depth,0},{0,2,4,6,8}},TrackedSymbols->{depth}]

binomialTable[size_,modulus_]:=Table[Mod[Binomial[n,k],modulus]/(modulus),{n,size,0,-1},{k,0,size}];

MatrixForm[binomialTable[5,3]]

Manipulate[Module[{binomialTable:=Table[Mod[Binomial[n,k],modulus]/(modulus),{n,(2^depth),0,-1},{k,0,(2^depth)}]},Graphics[Raster[binomialTable,ColorFunction->Hue]]],{{depth,0},{0,2,4,6,8}},{{modulus,3},{3,4,5,6,8}},TrackedSymbols->{depth,modulus}]