Repetition and recursion

Printing problems

Suppose you have created a variable called "shopping list which has as its value the list [bread cheese tea]. You can, of course, display this list on the screen by typing pr :shopping.list. Print will strip off the square brackets, display the list across the screen and move the cursor to the next line - like this:

BREAD CHEESE TEA

But suppose you want to see this list set out rather more like a normal shopping list with one item under the other:

BREAD
CHEESE
TEA

Unfortunately, no primitive is available to do the job directly. So, if you think that such a command might be a useful tool, you need to define it.

Play it again Sam?

Deciding on a name is easy enough. We could call the command vprint (short for vertical print). But the definition is more of a problem.

In looking for a strategy, it might occur to you that since print always moves the cursor down to a new line when it has displayed its input, vprint could be based on a repetition of the command print, with each member of the list taken individually as input. After all, we do have a primitive repeat which we can take advantage of.

Repeat takes two inputs: the first is a number and the second a list of instructions. The instructions in the list are carried out - just as if they were typed in at the keyboard - the number of times indicated by the first input. When you know in advance how often a list of instructions should be repeated and when the list of instructions remains constant, then repeat is indeed the ideal tool to use. For example - to use an idea familiar to Logo turtle fans - if you want to get someone to walk around the sides of a 30 metre square and return to their exact start position, then you can do no better than repeat four times the instruction go forward 30 steps and turn right 90 degrees. If you really cannot resist trying this out in Logo, despite our ban on turtles, type

showturtle
repeat 4 [fd 3 rt 90]

Notice, however, that in the case of our vertical printout of a list, the instructions could not remain absolutely constant. It is a different word which must be printed at each step. Moreover the number of steps will vary with the length of the list. Of course, it is possible to get around these difficulties. We might, for instance, toy with the following as a definition of vprint:

to vprint :list
repeat count :list [print first :list make "list bf :list]
end

But this is fairly messy. For one thing, the words in the list have to be counted. Worse still, in the instruction list which is to be repeated, there is one instruction whose only function is to adjust the value of the original :list in order to trick Logo into believing that it is always carrying out the same instruction - viz. to print the first word of :list.

Another way to handle the task

You will agree that if the procedure vprint is to cover every eventuality it will need to be prepared for its input list to contain no words at all - in other words for the input to be an empty list. True, this might seem crazy in the real world, but stick with it and try to think about an appropriate response. Presumably, if you were asked to write out such a list, you might reasonably choose to fold your arms and do nothing. To make an equivalent response, given similar circumstances, a Logo procedure would simply need to stop. One line of the definition of vprint, then, might well be:

if empty? :list [stop]

Now take the remaining cases where the input list is non-empty. You have to agree that a vertical printout of such a list would be achieved if

(a) the first word in the list was printed out on its own line and
(b) the rest of the list was printed out vertically beneath.

OK, OK, you say. You might be forced to agree on logical grounds but at first this hardly seems a genuinely helpful observation. Doesn't it merely put off tackling the real problem? To get to grips with the definition of vprint, surely we still need to know how to print out vertically the rest of the list.

Well, no we don't. Or rather, we know how to do it already. The rest of the list is after all a list just like the one we started with except that it is one word shorter. It must follow then that a vertical printout of this shorter list could also be produced using exactly the same strategy - by printing its first word and then vertically printing the rest. And if you ask me, now, how do I print vertically the rest of this even shorter list, the answer is still the same, unless, of course, the list is so short that it contains no words at all. In such a case, obviously, it is time to stop. (You have to admit that you agreed to this earlier.)

To recap, then: If its input list contains no words vprint should stop, otherwise it should print the first word of its input and then vprint the rest. Translating this into Logo is straightforward:

to vprint  :list
if empty?  :list [stop]
print first :list
vprint bf :list
end

Send in the clones

You might feel bothered that vprint is part of the definition of vprint. Haven't you learnt in other circumstances that such circularity in definitions is vicious? Well, as far as the Logo interpreter is concerned, it makes no difference whether vprint calls a procedure known as vprint or some other quite different procedure. Each call is taken as a new call to a new procedure and when a procedure is called, the instructions in the body of the definition are carried out - that's all. When vprint calls vprint it does not call itself, it calls up a clone. If it helps, you can imagine that each procedure call also conjures up a new interpreter who just gets on with his own little task regardless of whatever is going on around him.

A closer look at the mechanics

To convince you that vprint can indeed do the trick, when defined as above, let us trace its behaviour step by step.

Suppose that you have indeed set up a variable called "shopping list with a value [bread cheese tea], and that, with vprint defined as above, you type vprint :shopping.list. This is what happens:

vprint with input [bread cheese tea] checks if :list - i.e. [bread cheese tea] - is empty and, since it is not, the stop is ignored
vprint prints bread, i.e. first :list (followed by carriage return)
vprint calls a new vprint - call this vprint2,- with input [cheese tea] (i.e. bf [bread cheese tea]) and vprint2 is set to work immediately, before vprint itself is finished
- vprint2 checks if :list - in its case [cheese tea] - is empty and, since it is not, the stop is ignored
- vprint2 prints cheese i.e. first :list (followed by carriage return)
- vprint2 calls a new vprint3 with an input [tea] (i.e. bf [cheese tea])
- and vprint3 is set to work immediately, before vprint2 itself is finished
  - vprint3 checks if :list - in its case [tea] - is empty and, since it is not, the stop is ignored
  - vprint3 prints tea i.e. first :list (followed by carriage return)
  - vprint3 calls a new vprint 4 with an input [ ]
  - and vprint4 is set to work immediately, before vprint3 itself is finished
    - vprint4 checks if :list - in its case [ ] - is empty, and since it clearly is, vprint4 stops (i.e. stop is run)
  - calling vprint4 was the last instruction in vprint3 - so with no more to do vprint3 ends
- calling vprint3 was the last instruction in vprint2 - so with no more to do vprint2 ends
calling vprint2 was the last instruction in vprint - so with no more to do vprint ends

What is, clearly, crucial in all this is that, although vprint is defined as taking one input called "list and although, by definition therefore, each clone of vprint makes use of a variable called "list, in the case of each and every clone this variable is - like all input variables - a local variable. For each clone, :list simply identifies whatever input the clone receives when called. Now since, in the definition of vprint, a clone is always called with an modification of the caller's original input, it turns out that, despite the identity of the input variable names, for each vprint-clone :list is something quite new.

Recursion

A procedure such as vprint, which contains in its definition a call to (a clone of) itself is called a recursive procedure and the associated noun for the mechanism involved is recursion. When it comes to handling lists of unpredictably variable length, recursive procedures, which - as you have just seen - can nibble through them from one end to the other, are extremely useful tools. A typical selection of such tools from the Toolbox might include remove, replace, explode, implode

Recursive procedures can be classified in various ways. The general structure of the body of the definition provide one useful means to distinguish patterns of recursion (see here).

If you feel like another view of recursion - a more visual view - then look here

Ron Brasington
Department of Linguistic Science
The University of Reading
Reading
UK

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