MaterialsBlackboard and chalk or overhead and marker
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:
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!