Martin and The Dragon

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 bum 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 comer 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 ofthem 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.


Martin Visits the Dragon Again

"Hel1o Dragon!" Martin called as he made his way down the rickety dungeon staircase.
"Hmmmph! You again. I'm on to your recursive tricks." The dragon did not sound glad to see him.
"I'm supposed to find out what five factorial is," Martin said. "What's factorial mean, anyway?" At this the dragon put on a most offended air and said, "I'm not going to tell you. Look it up in a book." "All right," said Martin. "Just tell me what five factorial is and I'll leave you alone. "


"'You don't know what factorial means, but you want me to tell you what factorial of five is??? All right buster, I'll tell you, not that it will do you any good. Factorial of five is five times factorial of four. I hope you're satisfied. Don't forget to bolt the door on your way out."

"But what’s factorial of four?" asked Martin, not at all pleased with the dragon's evasiveness.

“Factorial of four? Why, it's four times factorial of three, of course."

"And I suppose you're going to tell me that factorial of three is three times factorial of two," Martin said.

"What a clever boy you are! " said the dragon. "Now go away."

"Not yet," Martin replied. "Factorial of two is two times factorial of one.

Factorial of one is one times factorial of zero. Now what?"

"Factorial of zero is one," said the dragon. "That's really all you ever need to remember about factorials."

"Hmmm," said Martin. "There's a pattern to this factorial function. Perhaps 1 should write down the steps I've gone through." Here is what he wrote:

Factorial (5)= 5 x Factorial (4)
= 5 x 4 x Factorial (3)
= 5 x 4 x 3 x Factorial (2)
= 5 x 4 x 3 X 2 x Factorial (l)
= 5 x 4 x 3 x 2 x 1 x Factorial (0)
= 5 x 4 x 3 x 2 x 1 x 1
Martin started to write again:
Factorial (5) 1 x 1= 1
2 x 1 x 1 = 2
3 x 2 x 1 x 1 = 6
4 x 3 x 2 x 1 x 1= 24
5 x 4 x 3 x 2 x 1 x 1 = 120
“Hey!” Martin yelled. “Factorial of 5 is 120. That’s the answer! Thanks!!"

'I didn't tell you the answer," the dragon said testily. "1 only told you that factorial of zero is one, and factorial of n is n times factorial of n- 1. You did the rest yourself. Recursively, I might add. "

"That's true," said Martin. "Now if only knew what 'recursively' really meant."

Next