‘‘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.'"
( )
"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."
'If you wish," the dragon replied.
Martin wrote in the dirt:
(3142 5798 6550 8914)
(5798 6550 8914)
(6550 8914)
(8914 )
( )
“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.
"'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."
“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."
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 |
'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."