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:

  1. Know when to stop.
  2. Decide how to take one step.
  3. 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."

Previous