Make your own free website on Tripod.com
 

Discussion #10 - Recursive Control Structure


Recursive structures look very much like iterative structures that are tail recursive, as you would expect from the similarity of their names. They both contain an instruction that calls the original procedure. They both have at least one input that is changed with each pass. They both use a stop rule to signal the completion of the run. However, as you will see, the interpreter responds "normally" to recursive procedures. Rather than repeating the original procedure over and over, as in tail recursive iteration, the Interpreter creates and runs a brand new subprocedure each time it reaches the recursive call.

Here is an example of a recursive procedure:

TO COUNTDOWN :NUMBER
  ht
  if :number = 0 [pr "BLASTOFF!! wait 50 stop]
  pr :number
  wait 30
  countdown :number - 1
  pr :number
  wait 10
END
The difference in form between this procedure and the iterative growbox procedure in Unit #8 is that the instruction that calls countdown (the recursive call) is not the last instruction in the procedure; another pr instruction follows it, causing the numbers to be displayed twice; once just before the recursive call and once just after it. What may be surprising is that the second display shows the numbers in reverse order from the way they were printed the first time. Why is this?

Do you recall the two tests which characterized an iterative command and the special way the Interpreter deals with procedures that have these characteristics? Please refresh your memory by reviewing the discussion in Unit #8. Recursive commands are those that fail the second test. The instruction that calls the subprocedure with the same name is not the last instruction line, so the Interpreter does not simply repeat the same procedure again and again. Instead, the Interpreter treats countdown as a usual superprocedure-subprocedure situation: when it reaches the calling instruction it suspends execution of the calling procedure temporarily while it executes the subprocedure.

You might want to review Discussion #4 at this point to refresh your memory about how the Interpreter handled the interactions between design, do.design, and poly. In that program, you learned that as soon as the Interpreter reached the instruction in a superprocedure that calls a subprocedure, it suspended its execution of the calling procedure and executed the subprocedure instead. When the subprocedure was finished, the Interpreter returned to the superprocedure at the point where it suspended its execution, and continued from there. Precisely the same thing happens when the Interpreter executes a recursive procedure, except that the name of the subprocedure that is called by the top-level countdown procedure is also named countdown.

When the Interpreter reaches the fourth instruction line of the procedure, it creates a new subprocedure named countdown - a clone of the top-level procedure - with a new local variable as its input. The Interpreter calculates the value of the clone's input variable (:NUMBER - 1), suspends its execution of the top-level countdown procedure, and begins execution of the subprocedure that it just created. The top-level countdown procedure just waits patiently while its clone is executed, just as design had to wait while do.design did its thing in Unit #4. When the subprocedure reaches its recursive call line, the same thing happens again: the Interpreter creates another clone and calculates the value of a new input variable, suspends execution of the calling subprocedure, and executes the new subprocedure instead. The original subprocedure waits, along with the top-level version of countdown.

This process of cloning a new subprocedure and creating a new input variable for it, suspending execution of the calling procedure, and executing the clone instead repeats over and over until the value of :NUMBER reaches 0, which activates the stop rule.

Perhaps this process could be better understood with a diagram. Let us identify each version of countdown by its input value. If the top-level countdown was given an input of 5 when it was typed in the command center, I can identify it as countdown 5. Its clone was given an input of 4 by its calling instruction, so I identify it as countdown 4, and so on. I like to explain recursion to my classes by writing each clone on a Post-it note with its own name-and-input identification. When the Interpreter reaches each clone's recursive call line and suspends its execution, that clone's identifying Post-it note is stuck on top of the one that called it.

The stack of notes representing the waiting procedures grows thicker as the program runs, like this: countdown 1 countdown 2 countdown 3 countdown 4 countdown 5 countdown 0 is the the clone that triggers the stop rule, printing "BLASTOFF!!" and then going directly to its End line, as directed by the stop command. It never gets a chance to print its input value, either before or after its recursive call line, and it never gets added to the stack of waiting clones. As soon as the Interpreter terminates countdown 0 by jumping directly to its End line, the interpreter returns to the procedure that called countdown 0 (countdown 1) and picks up the execution where it left off earlier. countdown 1 peels off the stack, prints its :NUMBER, and then moves on to its End line. The Interpreter then returns to the procedure that called countdown 1 (countdown 2), peels it off the stack, and picks up its execution where it left off by printing its :NUMBER and then moving to its End line.  This process continues until all the clones have peeled off the stack and printed their :NUMBER values. The last one to leave is the top-level countdown 5, the one that started it all. And that is why the numbers are printed in reverse order the second time!

I know that all of this will take awhile to thoroughly comprehend. The idea of the Interpreter creating clones of procedures that call themselves is new and, at first, rather unbelievable. But it provides a good model of how recursion works, and before long I am confident you will have a clear understanding of this important process.

Here is another example of a recursive program. It asks you to input the letters of a word and then prints the letters in reverse order.

TO SPELLBACKWARDS
  ht
  ct
  pr [Enter the letters of a word. Press <RETURN> after each letter Type a period when you have entered all the letters. I'll print the word backwards.]
  pr [ ]
  wait 50
  do.spellbackwards "
END
TO DO.SPELLBACKWARDS :LETTER
  pr [Enter the next letter or a period >>> | | ]
  make "letter rw
  if :letter = ". [ pr [Here is the word spelled backwards:] wait 50 pr [ ] stop]
  do.spellbackwards :letter
  insert :letter
END
The input expression in the calling line do.spellbackwards is a "quoted space" - a quotation mark followed by a space character. The value of this expression, that is assigned to the local variable :LETTER, is an empty word. This initial value of :LETTER is updated by the make instruction, which changes the value of :LETTER with each pass through the recursive procedure. Notice, too, that the stop rule in do.spellbackwards appears later than usual in the procedure. Do you see why this is necessary? The recursive procedures examined in this unit were both commands. Reporters may also be defined as recursive procedures; you will examine this important application of recursion in Unit #12.
 

Exploration #10


1. Test the countdown and spellbackwards procedures until you are thoroughly familiar with how they work, and then try explain their behavior to someone.

2. Rewrite the countdown procedure to make it count upwards first.

3. Rewrite the iterative growbox procedure in Unit #8 to make it recursive by adding a second repeat instruction to draw another set of boxes, following the iterative call (which now becomes a "recursive call" instead.)

4. Rewrite the iterative do.spiral procedure from Unit #8 to make it recursive by adding a second fd instruction following the iterative call.