A Rock Group Game:

 Let's play a game: when I clap, please raise your hands once. That's easy, no?

 CLAP Hands get raised.

CLAP, CLAP Hands get raised twice.

CLAP Hands get raised.

 All right, all right, you guys are doing well, but I can tell some of you think this is getting boring. Are you ready for a harder game? Please pay attention to the new rule: "Until Neil tells us to stop, every time you hear clapping, please raise your hand once, then clap once."

 CLAP Hands get raised and I hear some CLAPs; after a pause, more hands are raised, I hear more CLAPS and amidst chaos and CLAPs, everybody starts laughing as they understand what's happening...

 Lucky for us that Neil was here, or we would have gone on forever! This is recursion! I heard this story in a lecture by Seymour Papert, the brilliant man who invented LOGO.

 "I think that I shall never see a poem as lovely as a tree." Joyce Kilmer (1913)

 A tree has a root, a trunk, branches and leaves. Each branch may have leaves and may also have sub-branches. Any sub-branch may in turn have sub-sub-branches, etc... We have seen these ... before; usually we have meant go on forever, go on to infinity. Do you think any tree has an infinite number of branches? No (I have already said you can't find anything infinite in the real world). The ... simply means go on as long as necessary.

Anyway we would look silly if we said "the monkey jumped from one sub-sub-branch to a sub-sub-sub-branch": let's just call them branches as you have been doing all your life and change our definition to say that "any branch may itself have branches." There is recursion when the definition includes the term we are defining.

 Vicious circles:

Now, we all know you can't normally use the word you want to define in the definition:

AARDVARK: an animal, kind of strange, you know, like an aardvark!

RECURSIVE: Involving recursion

Thanks a lot! Now, imagine a dictionary with these two entries:

 BIZARRE: strange

STRANGE: bizarre

 This is called a vicious circle because if you don't know these 2 words, the dictionary is of no help. In the rare cases where a definition includes the term to be defined and still makes sense, we have a recursive definition.

 If you have a PC, you already know that the data and the programs are stored in files. These files are stored in directories. The directories can also have directories stored in them and you may notice this sounds just like the branches of a tree. In fact we do say that you have a directory tree. Do you think your computer can have an infinite directory tree?

 LOGO:

 Let us look at computer programming in the only language that children should hear about: LOGO. A few years ago, I felt so strongly against this very school teaching BASIC that I came and started teaching LOGO here as a volunteer until the school changed its mind (luckily, it did rapidly). In LOGO, if square has not been defined, then you can define it as

TO SQUARE (normal version)

REPEAT 4 [FD 10 RT 90]

END

 This is called a program. When you invoke it (by typing SQUARE), the instructions in the program are followed one by one and in this case a square is drawn. From this point on, you can use SQUARE as often as you want. For instance, you will get a pretty picture by typing

  REPEAT 12 [SQUARE RT 30]

 One of the many reasons that LOGO is greatly superior to BASIC is that, like all modern computer languages, it allows recursion. This means that we could write this for drawing a square:

  TO SQ (recursive version)

 This will draw the same square over and over again, which has the disadvantage that the program never ends. This "infinite loop" is what mathematicians in computer science worry about. Think about it, your boss wants to know how many customers do this or that and you write a program that instructs the computer to do it. Alas, by mistake, you may have created an infinite loop and you wait and wait... (and in the old days, pay and pay...). What are you to do? Maybe the computation was almost done when you finally pull the plug and turn off the computer: you'll never know!

Delta | Berkeley Utilities | Shareware & Freeware | Our People | Game of Go | Map of Site | Links

Last updated on January 8, 1999
Please send any comments to Jean-Claude Chetrit
Please check our mirror site at
http://OPENetwork.com/index.shtml
if you have any difficulty on this site.