LINGUIST List 12.1376

Sat May 19 2001

Disc: How Do You Demonstrate Recursion?

Editor for this issue: Karen Milligan <karenlinguistlist.org>

Directory

1. Mark_Mandel, Disc: How do you demonstrate recursion?
2. Job M. van Zuijlen, Re: Disc: New: How do you demonstrate recursion?

Dorothea Cogill <dcogillmetz.une.edu.au> wrote in LINGUIST List 12.1345:

>>>>>
What does it take for someone or something to show a grasp of recursive rules?

Assume you have a communication system in which some symbols stand for
actions (let's make those symbols the vowels A E I O & U, but they could be
anything you please), and other symbols stand for objects to which the
actions can be applied (let's make these symbols the consonants of the
alphabet - whatever). Put two symbols in order, and they amount to a
command to perform that action on that object. The correct order is set;
say it's ACTION + OBJECT, for example. Then (for the symbols offered
above) a string like "A Q" is a command to perform action A on object Q;
throw a ball, for example, if A is 'throw' and Q is 'ball'.

 [...]

The question is - well, I guess there are two questions.
1. does your system possess recursion? After all, if a sentence S is
ACTION + OBJECT, then two in a row can be written S-> S(S), which can be
expanded indefinitely (I hope your computer is translating these symbols
correctly!).
<<<<<

I wouldn't call that recursion, but simply compounding. As I understand the
term, you don't have recursion until the output of an operation can serve
as the input to another instance of the same operation, whether directly or
via a chain of intervening operations. The system as described above has
just one rule:
 1: action + object => command
which by itself has no room for recursion. In CFG notation this would be
"command -> action object", or S -> V N if you like, but the first way I
wrote it shows "input" and "output" more clearly.

Now, suppose you issue the command "E A Q", where "E" means 'pretend, act
out', and the translation of this command is 'pretend to throw the ball,
act out throwing the ball'. *Then* you'll have recursion. We've added the
rule
 2: command => object
which allows a command to be used as an object in rule 1, creating the loop
that defines recursion. Of course, not all combinations are meaningful,
such as *"A A Q" 'throw the throwing of the ball'.

This may not be what you wanted to know about, but it seems to me to be
what your question purports to be about.

 Mark A. Mandel : Dragon Systems, a Lernout & Hauspie company
 Mark_Mandeldragonsys.com : Senior Linguist
 320 Nevada St., Newton, MA 02460, USA : http://www.dragonsys.com

The example you give does not count as recursion, I think. But to
investigate that, you would first look at the kind of grammar that would
be able to generate sequences like "AQEP". It seems that a simple
regular expression would be sufficient, for example,
([A,E,..,U][B,C,..,Z]*), which means one element from the first list
(the vowels), followed by one element from the second list (the
consonants), repeated indefinitely (indicated by the '*'). So endless
repetition does not necessarily require recursion.

Another way to look at this, is to see what kind of automaton you need
to recognize your language, and you will find that a finite-state
automaton will be sufficient.

A less technical way to look at your problem is to observe that each
pair can be generated independently, like when we perform a sequence of
tasks without any particular order. For recursion to become necessary,
you need something more complicated. For example, you're on the
telephone and then another call comes in, which you handle, and then you
go back to the first call. This requires a "stack", you put the first
person on hold (put him/her on the stack), take the call from the second
person, and the "pop" the first person from the stack and continue your
conversation. You can even imagine more elaborate scenario's.

I hope this helps.

Job van Zuijlen