Martin and the Dragon

Contributed anonymously

Materials

Blackboard and chalk or overhead and marker
Dragon nose, head, or costume (optional)
Candle (optional)
2 actors (one to play the dragon and one to play Martin) and a narrator
3 copies of "Martin and the Dragon">br>>br>

Everyone loves stories! "Martin and the Dragon" is one story that my students love. This story is found in chapter 8 of Common Lisp: A Gentle Introduction to Symbolic Computation by David S. Touretzky. The entire book is available for download.

I have presented this in two different ways.

The first of several stories in chapter 8 is about Martin wanting to know if all of the numbers in a list of numbers are odd. He asks the dragon for the answer. The dragon replies that he will not give Martin the answer to that problem. He will only tell Martin if the first number in the list is odd. He will tell Martin the answer to this question for as many lists as Martin wants to give him... thus resulting in Martin discovering recursion!

Martin visits the dragon several times in chapter 8. The first visit is with the list of numbers where he discovers recursion. The second visit is about factorials and a second look at recursion. Eventually the visits lead to the three rules of recursion:

  1. Know when to stop.
  2. Decide how to take one step.
  3. Break the journey down into that step plus a smaller journey.

A later visit shows how infinite recursion may result if one of these rules is not satisfied.

This is a great introduction to recursive methods!