Martin and the dragon

In ancient times, before computers were invented, alchemists studied the mystical properties of numbers. Lacking computers, they had to rely on dragons to do their work for them. The dragons were clever beasts, but also lazy and bad-tempered. The worst ones would sometimes burn their keeper to a crisp with a single fiery belch. But most dragons were merely uncooperative, as violence required too much energy. This is the story of how Martin, an alchemist’s apprentice, discovered recursion by outsmarting a lazy dragon.

One day the alchemist gave Martin a list of numbers and sent him down to the dungeon to ask the dragon if any were odd. Martin had never been to the dungeon before. He took a candle down with him, and in the furthest, darkest corner found an old dragon, none too friendly looking. Timidly, he stepped forward. He did not want to be burnt to a crisp.

‘‘What do you want?’’ grumped the dragon as it eyed Martin suspiciously.

‘‘Please, dragon, I have a list of numbers, and I need to know if any of them are odd’’ Martin began. ‘‘Here it is.’’ He wrote the list in the dirt with his finger:

(3142 5798 6550 8914)

The dragon was in a disagreeable mood that day. Being a dragon, it always was. ‘‘Sorry, boy’’ the dragon said. ‘‘I might be willing to tell you if the first number in that list is odd, but that’s the best I could possibly do. Anything else would be too complicated; probably not worth my trouble.’’

‘‘But I need to know if any number in the list is odd, not just the first number’’ Martin explained.

‘‘Too bad for you!’’ the dragon said. ‘‘I’m only going to look at the first number of the list. But I’ll look at as many lists as you like if you give them to me one at a time.’’

Martin thought for a while. There had to be a way around the dragon’s orneriness.

‘‘How about this first list then?’’ he asked, pointing to the one he had drawn on the ground:

(3142 5798 6550 8914)

‘‘The first number in that list is not odd,’’ said the dragon.

Martin then covered the first part of the list with his hand and drew a new left parenthesis, leaving

(5798 6550 8914)

and said ‘‘How about this list?’’

‘‘The first number in that list is not odd,’’ the dragon replied.

Martin covered some more of the list. ‘‘How about this list then?’’

(6550 8914)

‘‘The first number in that list isn’t odd either,’’ said the dragon. It sounded bored, but at least it was cooperating.

‘‘And this one?’’ asked Martin.

(8914)

‘‘Not odd.’’

‘‘And this one?’’

()

‘‘That’s the empty list!’’ the dragon snorted. ‘‘There can’t be an odd number in there, because there’s nothing in there.’’

‘‘Well,’’ said Martin, ‘‘I now know that not one of the numbers in the list the alchemist gave me is odd. They’re all even.’’

‘‘I NEVER said that!!!’’ bellowed the dragon. Martin smelled smoke. ‘‘I only told you about the first number in each list you showed me.’’

‘‘That’s true, Dragon. Shall I write down all of the lists you looked at?’’

‘‘If you wish,’’ the dragon replied. Martin wrote in the dirt:

(3142 5798 6550 8914)
(5798 6550 8914)
(6550 8914)
(8914)
()

‘‘Don’t you see?’’ Martin asked. ‘‘By telling me that the first element of each of those lists wasn’t odd, you told me that none of the elements in my original list was odd.’’

‘‘That’s pretty tricky,’’ the dragon said testily. ‘‘It looks liked you’ve discovered recursion. But don’t ask me what that means—you’ll have to figure it out for yourself.’’ And with that it closed its eyes and refused to utter another word.

- From the book "Common Lisp: A Gentle Introduction to Symbolic Computation"