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 0Here 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
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?
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.
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.