Martin and The Dragon
The Dragon's Dream
The next time Martin returned to the dungeon, he found the dragon rubbing its
eyes, as if it had just awakened from a long sleep. "I had a most curious dream,"
the dragon said. "It was a recursive dream, in fact. Would you like to hear
about it?" Martin was stunned to find the dragon in something resembling a friendly
mood. He forgot all about the alchemist's latest problem. "Yes, please do tell
me about your dream," he said.
"Very well," began the dragon.
"Last night I was looking at a long loaf of bread, and I wondered how many slices
it would make. To answer my question I actually went and cut one slice from
the loaf. I had one slice, and one slightly shorter loaf of bread, but no answer.
I puzzled over the problem until I fell asleep."
"And that's when you had the dream?" Martin asked.

"Yes, a very curious one.
I dreamt about another dragon who had a loaf of bread just like mine, except
his was a slice shorter. And he too wanted to know how many slices his loaf
would make, but he had the same problem I did. He cut off a slice, like me,
and stared at the remaining loaf, like me, and then he fell asleep like me as
well."
"So neither one of you found the answer," Martin said disappointedly. "You don't
know how long your loaf is, and you don't know how long his is either, except
that it's one slice shorter than yours." "But I'm not done yet," the dragon
said. "When the dragon in my dream fell asleep. he had a dream as well. He dreamt
about-if you can imagine this--a dragon whose loaf of bread was one slice shorter
than his own loaf. And this dragon also 'wanted to find out how many slices
his loaf would make, and he tried to find out by cutting a slice, but that didn't
tell him the answer, so he fell asleep thinking about it." "Dreams within dreams!!"
Martin exclaimed. "You're making my head swim. Did that last dragon have a dream
as well?" "Yes, and he wasn't the last either. Each dragon dreamt of a dragon
with a loaf one slice shorter than his own. I was piling up a pretty deep stack
of dreams there."
"How did you manage to wake up then?" Martin asked. "Well," the dragon said,
"eventually one of the dragons dreamt of a dragon whose loaf was so small it
wasn't there at all. You might call it 'the empty' loaf.' That dragon could
see his loaf contained no slices, so he knew the answer to his question was
zero; he didn't fall asleep.
"When the dragon who dreamt of that dragon woke up, he knew that since his own
loaf was one slice longer, it must be exactly one slice long. So he awoke knowing
the answer to his question. "And,. when the dragon who dreamt of that dragon
woke up, he knew that his loaf had to be two slices long, since it was one slice
longer than that of the dragon he dreamt about. And when the dragon who dreamt
of him woke up "
"I get it!" Martin said. "He added one to the length of the loaf of the dragon
he dreamed about, and that answered his own question. And when you finally woke
up, you had the answer to yours. How many slices did you loaf?”
“Twenty-seven,” said the dragon. “It was a very long dream.”
Rules for Recursion
The dragon, beneath its feigned distaste for Martin’s questions, actually
enjoyed teaching him about recursion. One day it decided to formally explain
what recursion means. The dragon told Martin to approach every recursive
problem as if it were a journey. If he followed three rules for solving
problems recursively, he would always complete the journey successfully.
The dragon explained the rules this way:
- Know when to stop.
- Decide how to take one step.
- Break the journey down into that step plus a smaller journey.
Martin Discovers Infinite Recursion

On. his next trip down to
the dungeon Martin brought with him a parchment scroll.
"Look dragon," he called, "someone else must know about recursion. I found
this scroll in the alchemist's library."
The dragon peered suspiciously as Martin unrolled the scroll, placing a
candlestick at each end to hold it flat.
"This scroll makes no sense," the dragon said. "For one thing, it's got
far too many parentheses."
"The writing is a little strange," Martin agreed, "but I think I've figured
out the message. It's an algorithm for computing Fibonacci numbers."
"I already know how to compute Fibonacci numbers," said the dragon.
"Oh? How?"
"Why, I wouldn't dream of spoiling the fun by telling you," the dragon replied.
"I didn't think you would," Martin shot back. "But the scroll says that
Fib of 11 equals Fib of n - I plus Fib of n - 2. That's a recursive definition,
and I already know how to work with recursion."
"What else does the scroll say?" the dragon asked. "Nothing else. Should
it say more?"

Suddenly the dragon assumed
a most ingratiating tone. Martin found the change startling. "Dearest boy! Would
you do a poor old dragon one tiny little favor? Compute a Fibonacci number for
me. I promise to only ask you for a small one. "
"Well, I'm supposed to be upstairs now, cleaning the cauldrons," Martin
began, but seeing the hurt look on the dragon's face he added, "but I guess
I have time for a small one."
"You won't regret it," promised the dragon. "Tell me: What is Fib of four?”
Martin traced his translation of the Fibonacci algorithm in the dust:
Fib(n-1) + Fib(n-2)

"Finished?" the dragon asked
innocently.
"'No," Martin replied. "Something is wrong. The numbers are becoming increasingly
negative."
"Well, will you be finished soon?"
"It looks like I won't ever be finished," Martin said. "This recursion keeps
going on forever."
"Aha! You see? You're stuck in an infinite recursion!" the dragon gloated.
"I noticed it at once."
"Then why didn't you say something?" Martin demanded.
The dragon grimaced and gave a little snort; blue flame appeared briefly in
its nostrils. "How will you ever come to master recursion if you rely on a dragon
to do your thinking for you?"
Martin wasn't afraid, but he stepped back a bit anyway to let the smoke clear.
"Well, how did you spot the problem so quickly, dragon?"
"Elementary, boy. The scroll told how to take a single step, and how to break
the journey down to a smaller one. It said nothing at all about when you get
to stop. Ergo," the dragon grinned, "you don't."