Handout 3A

The purpose of this exercise is to introduce the concept of recursive programming.

We have seen that the LOGO language can be extended by defining new procedures. We have also seen that procedures can be defined in terms of other procedures. What happens if we define a procedure in terms of itself? A simple example, taken from the textbook, is shown below:

TO CIRCLE
 FORWARD 1
 RIGHT 1
 CIRCLE
END
Defining and running this procedure causes the turtle to draw a circle, going around and around it forever. Make it stop by holding down the command button (the one with the little apple and on it) and typing a period. Then use the STOP command to tell LOGO you want to leave the CIRCLE procedure.

You probably already have a better way to draw a circle using REPEAT, but we will use CIRCLE as a model of a recursive procedure. What does the computer do when you ask it to CIRCLE?

  1. FORWARD 1 moves the turtle forward 1 and draws a short line.
  2. RIGHT 1 turns the turtle one degree to the right.
  3. CIRCLE tells the computer to run the command CIRCLE. But wait! We are already running the command CIRCLE! It turns out that the computer doesn't care about this; it blindly looks up the definition of the CIRCLE procedure again and starts to run it:

    1. FORWARD 1 moves the turtle forward 1 and draws a short line.
    2. RIGHT 1 turns the turtle one degree to the right.
    3. CIRCLE tells the computer to run the command CIRCLE. We are already running the command CIRCLE, which was called from inside the CIRCLE procedure, but the computer doesn't care. It just keeps going:

      1. FORWARD 1 moves the turtle forward 1 and draws a short line.
      2. RIGHT 1 turns the turtle one degree to the right.
      3. CIRCLE tells the computer to run the command CIRCLE. And so on...
The CIRCLE procedure gives the computer two simple instructions to follow and then the general instruction "do the same thing again". Can you modify the CIRCLE procedure to draw a square or triangle?

A procedure for which which one (or more!) of its instructions is to run itself is called recursive. Recursive procedures can be very powerful, but are sometimes confusing.

In almost every way REPEAT 360 [FD 1 RT 1] is a much better way to draw a circle than the CIRCLE command defined above. If there is a simple way to use REPEAT to solve a problem, use it. However, some problems are naturally recursive. When tracing (walking through step by step) a recursive procedure as we did above, we get the impression of a series of nested copies of that procedure, or even of something spiraling inward. A beautiful aplication of recursion in LOGO is to draw spirals:

TO SPIRAL :SIZE
 FORWARD :SIZE
 RIGHT 90
 WAIT 60
 SPIRAL :SIZE - 10
END
Run the command SPIRAL 200; observe how the WAIT 60 command tells the computer to wait one second before executing the next command. Eventually, you will see a beautiful spiral, and then the computer will "scribble over" that spiral. Here's what's going on:

  1. FORWARD 200
  2. RIGHT 90
  3. WAIT 60
  4. SPIRAL 290

    1. FORWARD 190
    2. RIGHT 90
    3. WAIT 60
    4. SPIRAL 280

      1. FORWARD 180
      2. RIGHT 90
      3. WAIT 60
      4. SPIRAL 270
        .
        .
        .

        1. FORWARD 10
        2. RIGHT 90
        3. WAIT 60
        4. SPIRAL 0

          1. FORWARD 0
          2. RIGHT 90
          3. WAIT 60
          4. SPIRAL -10

            1. FORWARD -10
            2. RIGHT 90
            3. WAIT 60
            4. SPIRAL -20
              .
              .
              .
After the turtle has drawn a spiral it reverses direction and spiral outward again. This is because the number :SIZE - 10 eventually becomes negative, and so LOGO eventually executes instructions like FORWARD -10. The turtle doesn't mind -- a negative distance forward is treated as a positive distance backward.

We've seen some nice patterns generated recursively, but all the commands we've defined so far cause the computer to go into an "infinite loop" which must be interrupted using the command-. key combination. There is a way to prevent this infinite looping; you check to see when some condition is met (e.g. when the distance to be traveled is negative) and quit when that happens.

TO STOPSPIRAL :SIZE
 IF :SIZE < 0 [STOP]
 FORWARD :SIZE
 RIGHT 90
 STOPSPIRAL :SIZE - 10
END
Type this in and try running it. This is the first example we've seen of the IF command; we will see more complicated examples later.

Using the EDIT command, try moving the line with the IF command to different places in the code. What changes if you put it after the RIGHT 90 command? What if you put it after the STOPSPIRAL :SIZE - 10 command? Why do these things happen? Also, why test for :SIZE < 0 and not :SIZE = 0?

STOPSPIRAL has all the ingredients of a good recursive procedure. Given an initial condition (the :SIZE of a side) it checks to see whether that satisfies the condition required to halt computation (IF :SIZE < 0 [STOP]), performs an action (FORWARD :SIZE RIGHT 90) based on that condition, then "calls itself" with a new initial condition (STOPSPIRAL :SIZE - 10). Each time it calls itself, the initial condition given to the new copy of STOPSPIRAL comes closer to the condition for halting.

By modifying the angle of turn and the recursive call "STOPSPIRAL :SIZE - 10" you can create many different kinds of spirals. Try this now.

Mtht420