Classic Computer Magazine Archive COMPUTE! ISSUE 30 / NOVEMBER 1982

A Monthly Column

Friends Of The Turtle

David D. Thornburg
Associate Editor

Recursion – Part I

I saw a comic strip recently that showed a sleeping cat having a dream. The dream was of a sleeping cat having a dream, and so on. The final sleeping cat was dreaming of food. This dream of a dream of a dream is an example of recursion.

In computer languages, recursion can take several forms. Recursion is probably the most powerful and least understood programming tool in existence. Because LOGO is a marvelous language for exploring this topic, and because recursion can let you generate some beautiful pictures with programs only a few lines long, I have decided to devote this and next month's columns to this topic.

The philosophy behind this treatment of recursion is based on my forthcoming book (tentatively titled Discoveries of Beauty, Addison-Wesley, 1983) that will be appearing in your neighborhood bookstores very soon.

If you have LOGO on an Apple, TI, or Radio Shack computer, you will be able to experiment with the topics covered in this month's column. If you do not yet have LOGO, this column may help you make a decision to get it.

What is recursion in computer programming? Recursion is the process by which a procedure can use itself repetitively. The simplest type of recursion (supported by every computer language I have ever used) is called tail-end recursion. A simple example of tail-end recursion can be seen in this procedure for drawing a square:

TO SQUARE
FORWARD 40
RIGHT 90
SQUARE
END

If you entered this procedure and then started it by typing SQUARE, the turtle would move forward 40 units, turn right by 90 degrees, and then use the SQUARE procedure again. Each time the procedure is used, the turtle adds one more side to the square. After the turtle has drawn four sides, the square is finished, but the turtle will keep retracing its path until you interrupt the program (or until your version of LOGO decides it can't keep track of multiple uses of SQUARE any more).

This type of tail-end recursion is available in languages like PILOT through the use of the jump (J:) command, or in BASIC through the GOTO command. The equivalent SQUARE procedure in Atari PILOT looks like this:

*SQUARE
GR: DRAW 40
GR: TURN 90
J: *SQUARE
E:

Tail-end recursion can also be used to create figures that grow. For example, if we create the LOGO procedure SQUIRAL by entering:

TO SQUIRAL :SIZE
FORWARD :SIZE
RIGHT 91
SQUIRAL :SIZE + 1
END

then when we enter, for example, SQUIRAL 1, the turtle first moves forward by one unit, turns 91 degrees, and then repeats the procedure with the new value of :SIZE equal to the old value plus one. The reason that variables can be "passed" to procedures this way is that each time a LOGO procedure is used, the contents of the variables are maintained locally to that use of the procedure. LOGO provides the internal bookkeeping to insure that the value of :SIZE in the second use of SQUIRAL is kept apart from the value of :SIZE we started with. Local variables are a most important feature of languages like LOGO.

The SQUIRAL procedure also repeats forever, but it does not retrace its own path. This type of tail-end recursion is also possible in languages that have only global (rather than local) variables. In Atari PILOT, for example, this procedure would look like this:

*SQUIRAL
GR: DRAW #S
GR: TURN 91
C: #S = #S + 1
J: *SQUIRAL
E:

The use of the compute (C:) command allows us to change the value of the numeric variable #S.

As you can see, tail-end recursion is both useful and easy to understand. This form of recursion is just a simple loop from the back of the procedure to the front. Generalized recursion is not so limited.

In order to show how general recursion works, we will explore some curves that we described a few columns back – the fractals. Fractal curves are generated by the continued repetition of a simple motif within each portion of an overall curve. For example, suppose we start with the same curve we used in the article on fractals:

By repeating this motif within each straight line segment, we can generate the next pattern in the sequence:

This process can be repeated as many times as we want to get even more complex renditions of the curve:

Explicit Procedures For Drawing Fractals

Before developing a single recursive procedure for drawing this curve, we will explore some explicit methods that will help us understand the recursive form later.

The first procedures we will create are based on the basic triangular bump pattern. To draw this figure, we can use the following two procedures:

TO K0 :SIZE
FORWARD :SIZE
END

TO K1 :SIZE
K0 :SIZE/3
LEFT 60
K0 :SIZE/3
RIGHT 120
K0 :SIZE/3
LEFT 60
K0 :SIZE/3
END

(This may appear to be a hard way to draw this figure, but the power of this method will become obvious soon.)

To see the result of this procedure, we should start with the turtle near the left edge of the screen and facing to the right. The following setup procedure should do the job nicely:

TO SETUP
PENUP
SETPOS[-120-60]
RIGHT 90
PENDOWN
END

Now enter:

CLEARSCREEN
SETUP
K1 243

You should see the first level curve on the screen.

We chose 243 for the length of the curve because it fills the screen nicely and because it is a power of three. This last characteristic insures that our more complex renditions of this figure will be drawn with integer line lengths. This is especially valuable for those of you using TI or Radio Shack LOGO.

Suppose we want to draw the next level of this curve. To do this, we need to replace each straight line segment with a replica of the figure generated by K1 with the value of :SIZE reduced by a third. The following procedure does this for us:

TO K2 :SIZE
K1 :SIZE/3
LEFT 60
K1 :SIZE/3
RIGHT 120
K1 :SIZE/3
LEFT 60
K1 :SIZE/3
END

As you can see, K2 is identical to K1 except that K2 uses the procedure K1, and K1 uses the procedure K0. To see the result of this procedure, enter:

CLEARSCREEN
SETUP
K2 243

By now it should be pretty clear that we can generate the next level of the Koch curve by creating the procedure:

TO K3 :SIZE
K2 :SIZE/3
LEFT 60
K2 :SIZE/3
RIGHT 120
K2 :SIZE/3
LEFT 60
K2:SIZE/3
END

By making a simple modification to K3, we can create the procedure K4 that gives yet another level of detail to our figure, and so on.

How far do we need to continue this process? We could easily create procedures up to K20 or so, but do we really need to? Since our original procedure (K1) drew lines that were 243/3, or 81 units long, then the lines drawn by K2 were 27 units long. K3 used nine unit lines, K4 used three units and, if we were to define it, K5 would use lines one screen unit long. Since the computer display screen can't handle lines less than one unit long, it hardly makes sense to try to create this curve with any more resolution than that.

Because of LOGO's ability to use recursion, we will be able to create a single compact procedure that represents this type of curve to any level of accuracy we wish.

Recursive Procedures For Drawing Fractals

If we look at the procedure K0 through K4, we can see a clue that will show us how to create these fractal curves with only one procedure. The first thing to notice is that K0 is the only procedure that actually draws any lines. The other procedures only use lower numbered procedures themselves, or turn the turtle. By writing the actual steps as they are executed, we can show how these procedures work. Let us examine K2, for example. If we expand the steps, we can see the sequence of commands as they are carried out. Each column in the table below shows a different procedure. Since K2 uses K1 and K1 uses K0, this table needs only three columns. The arrows show the direction in which control is passed from one procedure to the other.

Table of Command Sequences for K2

When we used K2, it used K1 four times, and K1 used K0 16 times to actually draw the lines. A table for K3 would be four times longer than this and would require four columns. If you decide to construct such a table yourself, you will see that by the time K3 has finished, it will have used K2 four times, K1 16 times, and KO 64 times.

Because of the similarities between K1, K2, K3, etc., we should be able to use one procedure to create these curves with any level of complexity we want. We can do this because when LOGO procedures use themselves recursively, LOGO creates as many new copies of the procedure as are needed to keep the levels uniquely identified.

The only procedure we created that is markedly different from the rest is K0, because it only draws lines. The following procedure incorporates all the features of K0, K1, K2, etc., into one compact form that lets us generate any level of this curve we desire.

TO TRIAD :SIZE :LIMIT
IF :SIZE < :LIMIT [FORWARD :SIZE STOP]
TRIAD :SIZE/3 :LIMIT
LEFT 60
TRIAD :SIZE/3 :LIMIT
RIGHT 120
TRIAD :SIZE/3 :LIMIT
LEFT 60
TRIAD :SIZE/3 :LIMIT
END

To see how this procedure operates, let's examine it line by line. Suppose you were to give the command TRIAD 243 100, for example. First, the size (243) would be tested to see if it was less than the limit (100). Because it is not, TRIAD would be used again with a size of 243/3, or 81. Since in this new use of TRIAD the size (81) is less than 100, a line will be drawn (just as with the procedure K0). As soon as this happens, the STOP command forces LOGO back to the earlier version of TRIAD to carry out its next command (LEFT 60). This process is continued in just the same way that K1 used K0. The only difference is that we are taking advantage of LOGO's ability to keep track of multiple uses of a procedure we have defined only once. It is as though LOGO makes as many copies of TRIAD as it needs and gives them and their variables special names so that they are used in the right order and without getting the contents of the variables confused.

Experiment with TRIAD (leaving the turtle visible). By watching the figure being drawn, you might gain more insight into the way that recursion is being used to create the figure. To generate the figures we have already drawn, you might use:

TRIAD 243 243
TRIAD 243 81
TRIAD 243 27

Remember to clear the screen and use SETUP before drawing each curve. To see the most detailed level of this curve that can be shown on the screen, enter

CLEARSCREEN
SETUP
TRIAD 243 3

Next month we will continue with more examples of fractal curves and explore a few more complex examples of recursion. In the meantime, please feel free to experiment on your own!