Lecture 2 Fractals from Recursive Turtle Programs use not vain repetitions 1 Matthew 6 7 Fractals Pictured in Figure 1 are four fractal curves What makes these shapes different from most of the curves we encountered in the previous lecture is their amazing amount of fine detail In fact if we were to magnify a small region of a fractal curve what we would typically see is the entire fractal in the large In Lecture 1 we showed how to generate complex shapes like the rosette by applying iteration to repeat over and over again a simple sequence of turtle commands Fractals however by their very nature cannot be generated simply by repeating even an arbitrarily complicated sequence of turtle commands This observation is a consequence of the Looping Lemmas for Turtle Graphics Sierpinski Triangle Fractal Swiss Flag Koch Snowflake C Curve Figure 1 Four fractal curves 2 The Looping Lemmas Two of the simplest most basic turtle programs are the iterative procedures in Table 1 for generating polygons and spirals The looping lemmas assert that all iterative turtle programs no matter how many turtle commands appear inside the loop generate shapes with the same general symmetries as these basic programs There is one caveat here that the iterating index is not used inside the loop otherwise any turtle program can be simulated by iteration POLY Length Angle Repeat Forever FORWARD Length TURN Angle SPIRAL Length Angle Scalefactor Repeat Forever FORWARD Length TURN Angle RESIZE Scalefactor Table 1 Basic procedures for generating polygons and spirals via iteration Circle Looping Lemma Any procedure that is a repetition of the same collection of FORWARD and TURN commands has the structure of POLY Length Angle where Angle Total Turtle Turning within the Loop Length Distance from Turtle s Initial Position to Turtle s Final Position within the Loop That is the two programs have the same boundedness closing and symmetry In particular if Angle 2 k for some integer k then all the vertices generated by the same FORWARD command inside the loop lie on a common circle Spiral Looping Lemma Any procedure that is a repetition of the same collection of FORWARD TURN and RESIZE commands has the structure of SPIRAL Length Angle Scalefactor where Angle Total Turtle Turning within the Loop Length Distance from Turtle s Initial Position to Turtle s Final Position during the First Iteration of the Loop Scalefactor Total Turtle Scaling within the Loop That is the two programs have the same boundedness and symmetry In particular if Angle 2 k for some integer k and Scalefactor 1 then all the vertices generated by the same FORWARD command inside the loop lie on a common spiral To prove the Circle Looping Lemma follow the turtle through two iterations of the loop and observe that the initial turtle state undergoes exactly the same change as the turtle traversing two iterations of the POLY procedure see Figure 2 below Since we are iterating through exactly the same loop over and over again after every iteration of the loop the looping turtle must end up in exactly the same state as the turtle executing the POLY procedure This observation is the essence of the Circle Looping Lemma The Spiral Looping Lemma can be proved in an exactly analogous manner Looping Program Poly Procedure Looping Program Figure 2 The turtle traversing through two iterations of a loop 2 Examples The WALK procedure and the accompanying turtle path Figure 3 left provide typical embodiments of the Circle Looping Lemma Notice that vertices generated by the same FORWARD command inside the loop lie on a common circle Similarly the PENTARAL procedure and the accompanying turtle path Figure 3 right are embodiments of the Spiral Looping Lemma Notice that in the PENTARAL curve vertices generated by the same FORWARD command inside the outer loop of the program lie on a common spiral WALK Repeat Forever FORWARD 1 TURN 3 FORWARD 1 4 TURN 4 FORWARD 1 3 2 TURN FORWARD 3 5 6 TURN PENTARAL Repeat Forever Repeat 5 Times FORWARD 1 TURN 2 5 TURN 10 RESIZE 1 06 Figure 3 The turtle paths corresponding to the WALK procedure left and the PENTARAL procedure right Notice that corresponding vertices in the WALK curve lie on a common circle and that corresponding vertices in the PENTARAL curve lie on a common spiral When the POLY procedure generates either a regular polygon or star the vertices clearly lie on a common circle But for angles A that are incommensurable with 2 that is for angles A for which there are no integers m n such that m A 2n the curve does not close and it is not so obvious that the vertices generated by the POLY procedure must necessarily lie on a circle Yet as we can see from Figure 4 even when 2 A is not rational the vertices do nevertheless seem to lie on a common circle We shall now give a simple proof of this result based on standard arguments from Euclidean geometry 3 Figure 4 The output of the POLY procedure for different input angles A From left to right a regular ten sided polygon A 5 a seven pointed star A 6 7 and a figure that never closes A 2 2 Notice that in each case the vertices lie on a common circle Proposition 1 The vertices generated by the procedure POLY Length Angle lie on a common circle for any angle A 2 k for some integer k and any length L 0 Proof Consider the circle generated by the first three vertices D E F visited by the turtle while executing the POLY procedure see Figure 5 We need to show that the next vertex G visited by the turtle lies on the same circle that is we need to show that x CG R where R is the radius of the circle circumscribed about DEF and C is the center of this circle But CDE CEF since by construction the lengths of the three corresponding sides are equal SSS Now A A Therefore CEF CFG because these triangles agree in two sides and an included angle SAS Hence since CEF is isosceles CFG is also isosceles so x CG R F A G L A L E R x R R L R D C Figure 5 The circle generated by the first three vertices D E F visited by the turtle while executing the POLY procedure The vertices of the fractals in Figure 1 do not lie on common circles nor do they lie on common spirals Thus as a consequence of the Looping Lemmas these fractals cannot be generated by iterative turtle procedures To generate these fractal curves we must resort instead to recursive turtle programs 4 3 Fractal Curves and Recursive Turtle Programs There are many different types of fractal curves including gaskets snowflakes terrain and even plants Here we