# Almost Mid Quarter

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)