Recursively repetitive figures arise naturally and in a variety of pattern and design work. Such figures are called fractals. The essence of a fractal is that is has the same kind of micro structure as it has a macro structure.

For instance, if the West coast of British Columbia, Canada is viewed from outer space, it has an irregular shape with numerous inlets folded into the larger outline throughout this length. Looked at from a lower altitude airplane, these larger inlets themselves have an irregular and folded structure, and if one were to look closer still down on the ground, these too would be seen to have inlets and folds. That is to say, a fractal is recursive, at least to some number of levels. (In the case of the coastline, the recursion would break down to some extent after one began looking at individual grains of sand under sufficient magnification.)

A number of standard fractal designs can be constructed using recursive drawing techniques, and these are detailed below.

One of the easiest types of fractals to draw is a snowflake.

The snowflake fractal shown in figure 18.5 is based on triangles and has four levels of recursion or sizes of triangle. Assuming that the drawing starts at the lower left corner and with the direction to the right or East, the drawing of this fractal could be formulated in terms of pseudocode for a three sided figure as follows:

draw fractal = select standard coordinates select levelsofrecursion select mainlength select starting point on screen calculate turn angle based on number of sides (60 degrees for triangles) drawfigure drawfigure (mainlength, recursionlevel) = save current position and direction turnby -60 degrees; (* turn out and away first *) drawsegment (sidelen, curreclevel); (* go draw a side *) for count := 2 to numsides - 1 do (* then turn and draw each successive side except the last *) turnby 120 degrees; (* turn back in *) drawsegment (sidelen, curreclevel); end; if curreclevel < recursionlevel then (* fill in the missing side -- central third *) turnto (olddir); moveto (oldx, oldy); lineto (curx, cury); else (* go draw the last side *) turnby 120 degrees; drawsegment (sidelen, curreclevel); end; drawsegment (dist, curreclevel) = disttodraw := dist / 3.0; if curreclevel = 0 then lineby (dist); else drawsegment (disttodraw, curreclevel - 1); drawfigure (disttodraw, curreclevel - 1); drawsegment (disttodraw, curreclevel - 1); end;

The basic idea is that drawing a figure (say, a triangle) consists of drawing three successive segments with the appropriate angle between. Drawing each segment consists of drawing a third of that segment, then drawing the original figure at one third size as the middle third (unless one is past the appropriate number of recursion levels) then drawing the last third of the segment. In the code that follows, however, this has been modified to allow for the angle to be calculated for the number of sides. The number of recursion levels and number of sides is initially set to reproduce the drawing above, but both can easily be changed. Here is the code:

MODULESnowflake; (* by R. Sutcliffe 1996 01 29 to illustrate Macintosh quickdraw revised by Joel Schwartz and R. Sutcliffe to depend on GraphPaper. This program draws a recursive snowflake with a specified number of sides and level of recursion. Last revision 1998 06 16 *)FROMGraphPaperIMPORTLineBy, LineTo, TurnTo, MoveTo, GetDimensions, SetCoordSystem, CoordSystem, GetLocation;CONST(* set up these first two constants; the rest depend on them. *) recursionLevel = 3; numSides = 3; degreesAvailable = 180 * (numSides - 2); (* how many degrees around and back *) turnAngle = degreesAvailableDIVnumSides; (* turn for each corner *)VARcurDir :INTEGER; curX, curY :INTEGER; (* to globally store position and direction *) dimX, dimY :INTEGER; (* the dimensions *)PROCEDUREDrawSegment (dist :REAL; curRecLevel :INTEGER);FORWARD; (* omit if compiler is multi pass *)PROCEDUREDrawFigure (sideLen :REAL; curRecLevel :INTEGER);VARoldX, oldY :INTEGER; oldDir :INTEGER; count :CARDINAL;BEGIN(* store current directions *) oldX := curX; oldY := curY; oldDir := curDir; curDir := curDir - turnAngle; TurnTo (FLOAT(curDir)); (* turn out and away first *) DrawSegment (sideLen, curRecLevel); (* go draw a side length *)FORcount := 2TOnumSides - 1DO(* then turn and draw each successive one but the last *) curDir := curDir - turnAngle + 180; TurnTo (FLOAT(curDir)); DrawSegment (sideLen, curRecLevel);END;IFcurRecLevel < recursionLevelTHEN(* fill in the missing side -- central third *) curDir := oldDir; (* go back to old position *) TurnTo (FLOAT(curDir)); MoveTo (oldX, oldY); LineTo (curX, curY); (* and draw to new one *)ELSE(* draw another side like the ones in the loop above *) curDir := curDir - turnAngle + 180; TurnTo (FLOAT(curDir)); DrawSegment (sideLen, curRecLevel);END;ENDDrawFigure;PROCEDUREDrawSegment (dist :REAL; curRecLevel :INTEGER); (* recursively draw a third of the segment as another one then a third size figure on the next segment then another segment after that. *)VARdistToDraw :REAL;BEGINdistToDraw := dist / 3.0;IFcurRecLevel = 0THENLineBy (TRUNC(dist)); GetLocation (curX, curY); (* reset local storage of position *)ELSEDrawSegment (distToDraw, curRecLevel - 1); DrawFigure (distToDraw, curRecLevel - 1); DrawSegment (distToDraw, curRecLevel - 1);END;ENDDrawSegment;VARmainLength :INTEGER;BEGIN(* main *) (* calculate a length that will fill the screen nicely *) SetCoordSystem (MacWin); GetDimensions (dimX, dimY); mainLength := 3 * dimY/(2 * numSides); (* arrived at by experimenting *) (* starting point is "lower left" of first level recursive figure. *) curDir := 0; curX := (dimX - mainLength) / 2; curY := (dimY + mainLength) / 2; (* above formula not bad except for three sides, so adjust *)IFnumSides = 3THENcurY := curY - 75;END; MoveTo (curX, curY); DrawFigure (FLOAT(mainLength), recursionLevel);ENDSnowflake.

The program in this section recursively draws a tree fractal. The idea is that it draws a trunk in the current direction, then two trees at half size at forty-five degrees on either side of the top of the trunk, then a tree at three-quarters size in the same direction as the original trunk. After the first vertical trunk, the remaining trees can be thought of as branches. Recursion is exited if the length of the trunk is less than two units.

MODULEDrawTree; (* Program by R. Sutcliffe to illustrate GraphPaper revised 1998 06 16 recursively draws a fractal based tree. *)FROMGraphPaperIMPORTMoveTo, LineBy, Turn, TurnTo, GetLocation;PROCEDUREDrawATree (trunkLength :CARDINAL);VARbaseX, baseY :INTEGER;BEGINIFtrunkLength < 2THENRETURNEND(* if *); LineBy (trunkLength); GetLocation (baseX, baseY); Turn (45.0); DrawATree (trunkLengthDIV2); (* 1/2 current size right *) MoveTo (baseX, baseY); Turn (-90.0); DrawATree (trunkLengthDIV2); (* 1/2 current size left *) MoveTo (baseX, baseY); Turn (45.0); DrawATree (3 * (trunkLengthDIV4)); (* 3/4 current size up *) MoveTo (baseX, baseY);ENDDrawATree;BEGIN(* Find a good place to start drawing the tree. *) MoveTo (0,-250); TurnTo (90.0); DrawATree (128);ENDDrawTree.

Here is a screen shot of the tree that is drawn:

The tree fractal was drawn in a different way than the snowflake that preceded it. Rather than use a pair of mutually recursive procedures, it employed only a single procedure that drew segment-right fractal-left fractal-central fractal. Snowflakes can be drawn in a similar manner, without the filled in sides, and by using a singly-recursive procedure as in the following:

MODULEDrawFractal; (* Program to draw a fractal by R. Sutcliffe revised 1998 06 16 *)FROMGraphPaperIMPORTLineBy, Turn, TurnTo, MoveTo;TYPECardArray =ARRAY[0..12]OFCARDINAL;CONSTorder = 6; (* fits on most screens *) (* make a constant array with the powers of two for the line lengths. *) Power = CardArray {1,2,4,8,16,32,64,128,256,512,1024,2048,4096};PROCEDUREFractal (level:CARDINAL); (* Recursive drawing of levelth fractal *)BEGINTurn (-60.0); (* at all but the outer level, we do segment-fractal-segment *) LineBy (Power [level]);IFlevel > 1THENFractal (level - 1);END; (* if *) LineBy (Power [level]); Turn (120.0); LineBy (Power [level]);IFlevel > 1THENFractal (level - 1);END; (* if *) LineBy (Power [level]); (* at the outer level we complete the figure so it is closed *)IFlevel = orderTHENTurn (120.0); LineBy (Power [level]);IFlevel > 1THENFractal (level - 1);END; (* if *) LineBy (Power [level]);END; Turn (-60.0);ENDFractal;VARch :CHAR;BEGIN(* DrawFractal *) (* orient on the page the way we want *) TurnTo (180.0); MoveTo (100, -50); Fractal (order);ENDDrawFractal.

This program produces the following version of the snowflake fractal:

The most basic form of the fractal known as Sierpinski's curve consists of a square with squares on its corners in the manner shown in figure 18.8. Assuming standard coordinates with the origin at the centre, and given that the basic length on one of the corners is *dist*, drawing is done in four steps starting from the indicated point. (Recall that *Line* draws to a point with the given displacement from the current point.)

*top*: Line (dist, -dist); Line (2 * dist, 0); Line (dist, dist);

followed by Line (dist, -dist) to glue to the next piece

*right*: Line (-dist, -dist); Line (0, -2 * dist); Line (dist, -dist);

followed by Line (-dist, -dist) to glue to the next piece

*bottom*: Line (-dist, dist); Line (-2 * dist, 0); Line (-dist, -dist);

followed y Line (-dist, dist) to glue to the next piece

*left*: Line (dist, dist); Line (0, 2 * dist); Line (-dist, dist);

followed by Line (dist, dist) to glue to the next piece

That is, each procedure has three steps that draw a copy (in one of four rotations) of what is shown in figure 18.9, followed by a connector to the next part.

The fun begins when this process is made recursive, in the sense that the prototype procedure *Top* becomes:

Top = IF level > 0 THEN Top (level - 1); Line (dist, -dist); Right (level - 1); Line (2 * dist, 0); Left (level - 1); Line (dist, dist); Top (level - 1) END

If this is drawn at level two, the top (including the glue) becomes figure 18.10, and this pattern can be replicated around the basic square using the other three procedures in turn.

With a careful calculation of starting points, the level two diagram can be superimposed on top of the level one diagram, and indeed as many levels can be drawn as desired. In the code that is given below, three levels have been drawn by the main loop. Care must be taken not to ask for too many levels, or one could find the program in an infinite loop unable to compute the next smaller side length.

MODULESierpinski; (* Heavily adapted from a version in Wirth's PIM-2 by R. Sutcliffe to illustrate GraphPaper last revision: 1998 06 22 *)FROMGraphPaperIMPORTLine, LineTo, MoveTo;CONSTsize = 512; (* use a power of two that fits on screen. *) numOfLevels = 3; (* set to number smaller than the power in the last line; if 512; use 8 or less here *)VARdist :INTEGER; (* Each of the mutually recursive procedures draws one side of the basic square figure in the orientation given by its name. At the lowest level, this is an angled part, a straight part, and then an angled part, concluding with a "larger" copy of itself at a lower level to glue to the next piece. *)PROCEDURETop (level:CARDINAL);BEGINIFlevel > 0THENTop (level - 1); Line (dist, -dist); Right (level - 1); Line (2 * dist, 0); Left (level - 1); Line (dist, dist); Top (level - 1)ENDENDTop;PROCEDURERight (level:CARDINAL);BEGINIFlevel > 0THENRight (level - 1); Line (-dist, -dist); Bottom (level - 1); Line (0, -2 * dist); Top (level - 1); Line (dist, -dist); Right (level - 1)ENDENDRight;PROCEDUREBottom (level:CARDINAL);BEGINIFlevel > 0THENBottom (level - 1); Line (-dist, dist); Left (level - 1); Line (-2 * dist, 0); Right (level - 1); Line (-dist, -dist); Bottom (level - 1)ENDENDBottom;PROCEDURELeft (level:CARDINAL);BEGINIFlevel > 0THENLeft (level - 1); Line (dist, dist); Top (level - 1); Line (0, 2 * dist); Bottom (level - 1); Line (-dist, dist); Left (level - 1);ENDENDLeft;VARlevel :CARDINAL; startX, startY :INTEGER;BEGINdist := sizeDIV4; (* initial segment distance *) startX := 0; startY := dist; level := 0; (* The following loop draws the level one figure and then overlays it with the level two figure, and so on until the number of specified levels have all been drawn. *)REPEATINC(level); (* begin at one and work up to max set. *)DEC(startX, dist); (* set up new corner to start *) dist := dist / 2; (* and basic distance for next level *)INC(startY, dist); MoveTo (startX, startY); (* We end up d units left and d/2 units up from last start for next one.*) (* In the main program the figure is drawn with the four "sides" in succession, each followed by a line segment to glue to the next piece. *) Top (level); Line (dist, -dist); Right (level); Line (-dist, -dist); Bottom (level); Line (-dist, dist); Left (level); Line (dist, dist);UNTILlevel = numOfLevelsENDSierpinski.

When this version of the code was compiled and run, the following figure was produced.

Careful examination will reveal the three levels drawn. More can be called for, but the diagram becomes somewhat cluttered for illustrative purposes.