This week we continued the topics of sequences, iteration and recursion. I cooked up an in-class activity on the implementation of recursive function calls in programming languages, but at the last minute decided it was not quite ready to serve. Maybe next quarter.
We derived, as a class, a recursive formula that models the actions of an old game, “The Towers of Hanoi.” The game has three poles in a row and disks of different sizes, each with a hole at its center. The disks start in a wedding-cake arrangement on the leftmost pole and must be moved to the same arrangement on the rightmost pole, following two simple rules: only one disk can be moved at a time and a larger disk cannot be placed on a smaller disk. It’s a lesson that begs to be tried in person with a model. I made do with the board. Maybe next quarter.
An interesting side note on the teaching of the Towers of Hanoi. The explicit formula for the recursive sequence that models the moves needed to move n disks is 2^n – 1. For 64 disks this formula, on a standard calculator will give you the estimate,
1.844674407 x 10^19
Writing a simple, recursive program in the Haskell computer language, however, will give an exact answer.
Here’s the program (the recursion is the reference to the function hanoi within the definition of the function hanoi):
hanoi n = if (n == 1) then 1 else (2*hanoi (n-1) +1)
Here’s the exact answer,
My lectures follow the flow of the text–dipping in and out to help connect definitions to theorems, theorems to examples, examples to narrative, etc., and sometimes to look underneath the text, to what is not being said. The relationship of lecture and text is another tension in teaching. Follow the text too closely and the students may wonder why they don’t just read the book themselves and not bother with class. Lecture apart from the text and students may wonder why they bought it. Of course there are students who read the text but don’t understand it and students who understand the text but don’t read it, but that’s a different tension of teaching.
Next week is the midterm exam. I’ll be writing it this weekend. Of course it should be a Goldilocks test, not too easy, not too hard, but just right. Maybe next quarter.