TEACH RECURSE2                                 Updated Aaron Sloman 1989


                        RECURSION and REPETITION

         CONTENTS - (Use <ENTER> g to access required sections)

 -- Prerequisites
 -- Introduction
 -- Defining "square" recursively
 -- Defining polygon recursively
 -- Defining "squiral"

-- Prerequisites ------------------------------------------------------

This file assumes that you have already read TEACH * RECURSE1,
introducing the basic idea of a recursive procedure.

It also assumes that you have learnt to use the POP-11 turtle for
drawing pictures in a two-dimensional array (or in the VED buffer), as
explained in TEACH * TURTLE or TEACH * VTURTLE (the latter uses VED.)

In this teach file the idea of recursion is illustrated in different
contexts, concerned with drawing pictures. If you are not interested
in this use of recursion you could simply skip to TEACH RECURSE2

In several of the files and mini-projects, you will find that we define
procedures in terms of themselves, that is recursively. This is because
there are many programming tasks which are achieved fairly simply with
the aid of recursion, and which would be much harder to do by other
means.

-- Introduction -------------------------------------------------------

Here are a few exercises to help you get used to recursive programs
involving numbers. The other TEACH files will give you lots of practice
with recursion on lists.

All the examples which follow could be done using 'looping'
constructions, e.g. REPEAT, or UNTIL, or WHILE statments. One great
disadvantage of this method is that if you want the computer to give you
an indication of when it is re-starting a loop you have to re-define the
procedure to include extra print instructions. However, if you use
recursion to restart a process, then you can use the TRACE facility to
achieve this. This can help enormously to speed up de-bugging and is
also useful for demonstrating your programs at work.

-- Defining "square" recursively --------------------------------------

One of the procedures in the TEACH * TURTLE was intended to draw a
square.

    define square (side);
        repeat 4 times
            draw(side);
            turn(90);
        endrepeat;
    enddefine;

   This used the "schema"

    repeat <number> times <action> endrepeat;

Suppose we wanted to make a slightly more general procedure, which,
instead of drawing only four times could draw a number of lines
determined by an argument, and which, instead of always turning through
ninety degrees would also turn through an amount specified by an
argument. We could again use the REPEAT construction, thus:

    define polygon (side, angle, number);
        repeat number times
            draw(side);
            turn(angle);
        endrepeat;
    enddefine;

How would you define SQUARE in terms of this procedure?

   define square (side);
        polygon(....., ....., .....)
   enddefine;

   Complete this definition and try it out.

Instead of using REPEAT we can use recursion to define the procedure
POLYGON. The "schema" for this is:

-- Defining polygon recursively ---------------------------------------

   define polygon (side, angle, number);
        if <not yet finished> then
            <draw one side and turn>
            <restart with number reduced>
        endif;
   enddefine;

Try to replace the bits of English with POP-11?

    <not yet finished> should be replaced by a test whether there
    are still some lines to be drawn, i.e. a test whether NUMBER is
    bigger than 0.

    <draw one side and turn> should be replaced by turtle commands
    using DRAW and TURN, with appropriate arguments. (See the TURTLE
    and VTURTLE teach files.)

    <restart with NUMBER reduced> requires a call of POLYGON, i.e.
    the procedure being defined, with NUMBER-1 as its last argument,
    and the remaining two arguments unaltered.

Notice that the recursive call must include as many arguments as the
procedure being defined has formal parameters (in this case three).

Test your definition of polygon when you've completed it. Try drawing an
octagon with it.


-- Defining "squiral" -------------------------------------------------

    define squiral(number, distance, subtract);
        repeat number times
            draw(distance);
            turn(90);
            distance - subtract ->distance;
        endrepeat
    enddefine;

The use of "REPEAT"......."ENDREPEAT" makes it easy to get a program to
do something a specified number of times. But how is this achieved?
Could you write a program like squiral without using REPEAT? (If you
think you can, then try it before reading on).

Here is one way of thinking about SQUIRAL. We want to do something a
specified number of times, i.e. NUMBER times. There are two main cases
to consider, somewhat like the two cases in the definition of factorial
and sum, in TEACH RECURSE1. The cases (for SQUIRAL) are:

    (a) NUMBER is 0, i.e. there's nothing more to be done (doing
        something 0 times is the same as not doing it!).
    (b) NUMBER is greater than 0, i.e. you still have to perform the
        action.

Why should we consider case (a) at all? The answer is that it is helpful
do deal with case (b) in such a way that you do the action once, then
reduce NUMBER by 1, and start again. So although you never ask for the
action to be performed zero times, the program will eventually get down
to a zero value for NUMBER.

We thus have the following "schema" for the program:

    define squiral(number,  distance, subtract);
        if number > 0 then
            <do the action>
            <call squiral again with number reduced by 1
            and distance reduced by subtract>
        endif
    enddefine;

where the action is:

    draw(distance);
    turn(90);

Problem: what will this do when NUMBER is 0?

In the original version of SQUIRAL we also included an instruction to
reduce the value of DISTANCE by the amount specified in SUBTRACT. Now
instead of doing that as part of the "action", we can simply give an
appropriate second argument to our recursive call of SQUIRAL, i.e.
DISTANCE - SUBTRACT instead of DISTANCE. So the
    recursive call looks like this:

        squiral(number - 1, distance - subtract, subtract)

i.e. start SQUIRAL again with NUMBER reduced by 1, with DISTANCE reduced
by SUBTRACT and with the same value for SUBTRACT as before.

Complete this version of SQUIRAL and try it out.


-- A different stopping condition for squiral -------------------------

One reason why this method is perhaps preferable, is that you can now
easily modify the definition of SQUIRAL so that it has a more complex
stopping condition. The last version of SQUIRAL stopped as soon as
NUMBER had the value 0. More precisely, it continued drawing so long as
the value of NUMBER was greater than 0.

Suppose you want to make the program continue drawing until the turtle
reaches a position where its X-coordinate is between 10 and 15. You
can do this simply by changing what comes between IF and THEN:

        if  xposition < 10  or  15 < xposition then

Alternatively you may wish to combine the new continuation condition
with the old one, so that the drawing stops if either NUMBER gets down
to 0 or the turtle gets to a certain range of locations.

Suppose the picture has size 21 by 21. Redefine SQUIRAL so that drawing
stops if ever the turtle gets to within two steps from the centre of the
picture (the position [11 11]), or NUMBER gets down to zero.

You will probably find it helpful to use the procedure ABS (absolute
value of a number). abs(num) is always positive or 0, never negative,
whether num is positive or not. Eg.

    abs(66) =>
    ** 66
    abs(-66) =>
    ** 66
    abs(0) =>
    ** 0

We can use this to find out whether YPOSITION differs from 11 by more
than 2, I.e. use the test

        abs(yposition - 11) > 2

The new definition will start:

    define squiral (number, distance, subtract);
        if  number > 0
        and ....

   Can you complete it?


-- Further reading ----------------------------------------------------

To find out about the turtle:

TEACH TURTLE, or TEACH VTURTLE

For more on recursive list processing See

TEACH * RECURSE3  TEACH * SETS and TEACH * SETS2


--- C.all/teach/recurse2
--- Copyright University of Sussex 1990. All rights reserved. ----------