Ends and means

A boring procedure

Before we look at the ways in which the inputs to a recursive procedure may be systematically modified and at the types of test which may be used to terminate the recursion, it is important to establish that there is no requirement in principle for a recursive procedure to accept an input nor for its definition to contain any kind of conditional at all. For example, in the following definition of boring, you will find no input variable in the header and no if anywhere in the body, though the command is clearly recursively defined.

to boring
pr  [Oh! Not again]

Of course, the consequence of there being no if and no test is that there is also no terminating instruction list to carry out, and you had better know how to stop Logo running on forever if you want to try out boring. (In Terrapin Logo for the Mac, <control> g does the trick). For good reason, this type of procedure with no terminating condition is rarely used.

There were three in the bed . . .

There were n in the bed
And the little one said
Turn over
They all turned over
And one fell out

There were n -1 in the bed
And . . . .

Unlike boring, but rather like this verse, most of the recursive procedures you will meet will expect one or more inputs and typically at least one of these will be systematically modified (changed in some simple, regular way) on each recursive call until some target is reached. Targets are specified in the tests which provide the first input to an if - most often at the beginning of the definition. They may be either numerical or non-numerical. As for the modifications to the procedure's input when the recursive call is made, you will see that they normally conspire to create patterns of control which can be thought of as either count-up or count-down - when the target is numerical - or wind-through (maybe backwards or forwards) when the input is a word or list.

The next two pages look in turn at numerical and non-numerical targets and the means of varying inputs to match such ends.

Ron Brasington
Department of Linguistic Science
The University of Reading

E-mail: ron.brasington@rdg.ac.uk