Recursion Example

Recursion example: The Towers of Hanoi

Recall that in class we discussed a recursive solution to the Towers of Hanoi, using the following algorithm:

Given N disks to move from FROM to TO using SPARE,

  1. If N=1 just move the one disk from FROM to TO and return.
  2. Otherwise:
    1. Move N-1 disks from FROM to SPARE
    2. Move one disk (the largest one at bottom) from FROM to TO
    3. Move N-1 disks from SPARE to TO
Here is a LISP implementation of this algorithm, a lot like the solution we did in class but expressed a little more cleanly. 
(defun towers-of-hanoi (n)
  (transfer 'A 'B 'C n))

(defun move-disk (from to)
  (list (list 'MOVE 'DISK 'FROM from 'TO to)))

(defun transfer (from to spare n)
  (cond ((equal n 1) 
	 (move-disk from to))
	(t (append
   	    (transfer from spare to (- n 1))     ; move top n-1 over to spare
	    (move-disk from to)		         ; move largest disk
	    (transfer spare to from (- n 1)))))) ; move top n-1 to largest
Problem 1: Implement a function that, instead of reporting instructions for solving the Towers of Hanoi, counts up the number of moves it would take. [Solution]

Problem 2 (optional): Read ahead to the chapter on input and output, and re-implement this so that instead of building up a list of instructions, it prints the instructions out as a side-effect. [Solution]

Problem 3 (optional): Solve Problem 1, but use memoization (i.e. recording solutions to sub-problems you've already solved) to get rid of redundancy.