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 n equals Fib of n-1 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) = Fib(n-1) + Fib(n-2)

Then he began to compute Fib of four:

Fib(4) = Fib(3) + Fib(2)
Fib(3) = Fib(2) + Fib(1)
Fib(2) = Fib(1) + Fib(0)
Fib(1) = Fib(0) + Fib(-1)
Fib(0) = Fib(-1) + Fib(-2)
Fib(-1) = Fib(-2) + Fib(-3)
Fib(-2) = Fib(-3) + Fib(-4)
Fib(-3) = Fib(-4) + Fib(-5)

‘‘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.’’

The End
_________________________

Here ends the story of Martin. Kudos to its original author David Touretzky, a prof at CMU.