Recursion across procedures

Diagnosing recursion

If you have been following Part One in the 'prescribed' order, you may by now have come to the conclusion that it is a simple matter to determine whether or not recursion is at work in some system. The diagnostic procedure seems to be:

Check through the individual procedure definitions. If, in any one of them, the procedure name reappears in the procedure definition, then the system makes use of recursion.

In fact the test is not quite so simple, because the facts are not quite so simple.

Recursion and narural language

As it happens, this point can be nicely demonstrated by examining the interaction between some quite basic rules in a grammatical description - a system set up by a linguist to generate automatically the sentences of a language.

In order to cater for sentences like:

  1. John likes Mary
  2. I know that John likes Mary
  3. You know the boy who likes Mary
a linguist might include the following rules in his grammar of English (simplifying somewhat):
  1. S --> NP VP
    (A Sentence is composed of a Noun Phrase followed by a Verb Phrase)

  2. NP --> Det Noun (S)
    (A Noun Phrase is composed of a Determiner - Noun sequence followed optionally by a Sentence)

  3. NP --> that S
    (A Noun Phrase is composed of that followed by a Sentence)
You are intended to take Rules 2 and 3 as alternatives and, at least for the moment, you need to accept that, just as it makes obvious sense to treat John likes Mary in Sentence 1 as a sentence, it also makes good sense to treat who likes mary in Sentence 2 as a sentence (which just happens to be used to restrict the meaning of the boy).

Because of the way in which Rules 1, 2 and 3 of the grammar are related and because of the way in which they therefore interact, this grammar allows for the creation (or the specification) of an infinite number of infinitely long sentences like:

I know that you think that this is the boy who likes the girl who said that she thought that the man who . . .

The linguist would say, consequently, that this grammar provides a recursive definition of a sentence.

A LOGO perspective

Looking at such a grammar as a LOGO programmer, you would, no doubt, take each grammar rule as equivalent to procedure. (This is effectively what was done in setting up the Lonely Hearts environment.) And you would be obliged to say that, when treated as procedures, Rule 1 calls Rule 2 and that Rule 2 calls Rule 1 recursively.

It follows, then, that recursion is not restricted to the confines of a single procedure. A collection of procedures can implement recursion even though individually none of them is recursively defined.

To take a simple, example, here is a pair of procedures which interact like Rules 1 and 2 of the grammar - read.out calls pass.on and pass.on calls read.out. 

to read.out :news
if empty? :news [stop]
pr se :news "!
pass.on :news
end

to pass.on :info
read.out bl :info
end
If you are familiar with the (ever so slightly) bawdy song Sir Jasper, you will recognize the pattern of events if you run read.out with [oh sir jasper do not touch me] as input.

Of course, you might be thinking that you could define a single recursive procedure to do exactly the same thing. In this case, you can. (Why not try it?) But that is not the point. Sometimes - as in the linguistic example above - recursing across procedures may be the only feasible technique.

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

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

ÿ