The place of the recusive call

The grand old Duke of York

In the definition of vprint we saw that the the recursive call was placed within the very last instruction. This is an extremely common position. You will find it, for example in the definitions of explode, flatten, reverse, remove.dups and many other procedures in the Toolbox in the Appendix. But a recursive call can appear anywhere after the initial test. (You can think about why not before the test!) For example, the following procedure, duke.of.york, has the recursive call placed just before the last instruction.

to duke.of.york :where.he.is
if :where.he.is = :top [pr [at the top] stop] 
( pr [marching up them up at level] :where.he.is ) 
duke.of.york :where.he.is + 1 
( pr [marching them down again at level] :where.he.is ) 
end

If you were puzzled by the way our step by step trace through the actions of vprint ended, you will find it interesting to copy and run the duke.of.york. Because there are still things to be done after the recursive call has been made (and its work carried out) this procedure provides a nice opportunity to see more clearly how the transfer of control is normally effected.

You will need to set up in advance a variable called "top with a number as its value. Keep the number reasonably small. You can think of it as the height of the hill measured in hundreds of feet. Then start up duke.of.york with 0 (zero) as input (if you want to see the Duke and his men go up from the bottom of the hill).

The screen display should end up looking something like this:

make "top 10
duke.of.york 0
MARCHING UP THEM UP AT LEVEL 0 
MARCHING UP THEM UP AT LEVEL 1 
MARCHING UP THEM UP AT LEVEL 2 
MARCHING UP THEM UP AT LEVEL 3 
MARCHING UP THEM UP AT LEVEL 4 
MARCHING UP THEM UP AT LEVEL 5 
MARCHING UP THEM UP AT LEVEL 6 
MARCHING UP THEM UP AT LEVEL 7 
MARCHING UP THEM UP AT LEVEL 8 
MARCHING UP THEM UP AT LEVEL 9 
AT THE TOP 
MARCHING THEM DOWN AGAIN AT LEVEL 9 
MARCHING THEM DOWN AGAIN AT LEVEL 8 
MARCHING THEM DOWN AGAIN AT LEVEL 7 
MARCHING THEM DOWN AGAIN AT LEVEL 6 
MARCHING THEM DOWN AGAIN AT LEVEL 5 
MARCHING THEM DOWN AGAIN AT LEVEL 4 
MARCHING THEM DOWN AGAIN AT LEVEL 3 
MARCHING THEM DOWN AGAIN AT LEVEL 2 
MARCHING THEM DOWN AGAIN AT LEVEL 1 
MARCHING THEM DOWN AGAIN AT LEVEL 0

Here you have clear evidence that the print instructions in the last line of the body of definition, which come after the recursive call, are carried out by each calling procedure only after each subordinate called procedure has completed its task and handed back control to the caller. Running the duke.of.york also provides a convincing demonstration of the locality of input variables. Each duke.of.york clone obviously remembers - or at least knows how to retrieve - the particular value given to its own instance of "where.he.is when the procedure was called.

If your implementation allows you to trace events in the Logo environment - usually by saying trace followed by a procedure name or list of procedure names, then try

trace "duke.of.york
duke.of.york 0

The trace display will look like this (or may be even more informative):

What is going on here is not really too surprising. From your experience, you will know that a Logo procedure terminates when it outputs or when an explicit stop is encountered. Failing that, a procedure stops only when the interpreter reaches the last line of the definition which contains end. But by then, clearly, all of the instructions - including the very last print in the case of the duke.of.york - must have been carried out. How else could the overall task be said to be completed?

Keeping track of who calls who

It is obvious from the display generated by the duke.of york that, in order to guarantee that control is properly handed back to along the line as the recursion unwinds, Logo must somehow keep careful track of the relationships within the family of clones who get put to work. In fact, as we have already implied, the guiding principle which results in the mirror image effect is straightforward enough. Unless there is some massive intervention from on high - like a toplevel command - a procedure always hands back control to its caller. If duke.of york in its clone 4 incarnation calls duke.of.york clone 5, then clone 5, when his work is done, automatically hands control back to clone 4. Of course, it is quite reasonable to feel that the precise mechanism involved in maintaining this pattern of control is something you should not really need to care about. But the way in which Logo keeps a grip on the process is significant for the structure of recursive procedures in one particular way which you might be compelled to notice.

When there are things still to be done after the recursive call is complete - like the final print instruction in the duke.of york - and when there are variables whose value must be remembered - like the multiple instances of where.he.is - then Logo has to store that information somewhere in the computer's memory. In fact it keeps it in an area called the stack. Now, although in theory this raises no problems, in the real world, keeping hold of information in memory uses space and stack space is something which is not only finite but probably quite limited. You need to be wary, therefore, of commands like the duke.of.york where the recursive call is followed by other instructions because you may well find that when the depth of the recursion is increased your machine runs out of stack space trying to hang onto its way back and a error message suddenly appears on the screen.

Tail recursion

Suppose, however, that the definition of a procedure requires nothing more to be done when the recursive call is complete. Such is the case of vprint, for example, in which a recursive call to vprint forms the last instruction. Our original trace of vprint :shopping.list implied that after each recursive call, control was handed back to the calling procedure. vprint4 passed the baton back to vprint3, which in turn handed it back to vprint2 and so on. This is almost certainly the best - and simplest - way to to think about how Logo generally manages interaction between procedures. But in the particular case of vprint, there is clearly little point in Logo really handing back control to the caller. After all, why come back and wake up the calling procedure if it is only going to have to stop and go to sleep again. It also follows that if there is no need to return to the caller, then there is no point in remembering who the caller is either.

Because of the potential problem with stack space, most implementations of Logo are clever enough to be able recognize recursive procedures of the vprint type, which, because of the positioning of the recursive call, are called tail recursive. And Logo reacts sensibly to tail recursion by simply carrying out the call and forgetting the caller. As a result, you will find that implementations of Logo do not usually suffer memory problems in handling tail recursion, even infinitely deep recursion as in boring.

Unfortunately, identifying tail recursion requires more than a check to make sure that there are no instructions after the recursive call. As you will see when we look at patterns of output in recursive operations, the recursive call may appear in the very last instruction without the procedure being be tail recursive.

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

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