Notes on the Towers of Hanoi problem.

The problem: We have three towers A, B, C. We have some disks on tower A. We want to move the whole collection of disks to tower C without breaking the two rules that (a) we only move one disk at a time, and (b) we can never place a larger disk on top of a smaller one.

First, look here for an overview of the problem and a good explanation of it.

The Towers of Hanoi problem is ofen used to illustrate recursive programming. For many standard programming languages, recursion is considered a relatively advanced concept, not for beginners. In LISP however, because we uses LISTS as the basis of the programming language itself, recursion is very natural and also quite easy to learn. But it takes getting the "ah ha!" moment.

The general idea of recursion is that have two cases: a BASE CASE and a RECURSIVE CASE. Typically, the recursive case is happy to run forever and never stop, but the base case cuts off this march toward infinity. Here is an example recursive algorithm to print out the elements of a list:


Function: RECURSIVE-PRINT  (RP for short).

Recursive case: If your list is not empty, print the first thing in the
list, then call the function again on the rest of the list.

Base case: If your list is empty, then STOP.

This gives us the following:

RP (A B C)
Print A, call RP (B C)
Print B, call RP (C)
Print C, call RP ()
STOP

Output: A B C

Here is a LISP program that does the same thing:


(defun RP (l)            ; Define the function RP
  (cond                  ; On the condtion
    ((Null l)            ; ... that the list is empty (null)
     (print 'all-done))  ; Print out the message that we are all done.
    (t                   ; Otherwise, [t means true in all cases]
     (print (first l))   ; ... print the first thing in the list
     (RP (rest l)))))    ; ... then call RP on the rest of the list

(RP '(A B C))            ; We run the program, calling our function RP on the list '(A B C)
A 
B 
C 
ALL-DONE 
ALL-DONE

(Note ALL-DONE shows up twice because after printing it, the function also
returns the last value in the fuction, and LISP prints that too.)

For fun, we can print the list in reverse. This is a little trickier. See if you can get to "ah ha!" for it. The key here is we keep calling the function on the rest of the list until there is no more list. Then, on the way back up, we print the first thing in the list. But since we are starting on the bottom, we end up printing the list in reverse order. If you can't "see" it in your head, it is OK. Just move on for now.


(defun Reverse-RP (l)      ; Define the function Rerverse-RP
  (cond                    ; On the condtion
    ((Null l) nil)         ; ... that the list is empty (null), do nothing.
    (t                     ; Otherwise, [t means true in all cases]
     (Reverse-RP (rest l)) ; ... call Reverse-RP on the rest of the list
     (print (first l)))))  ; ... THEN print the first thing in the list

(Reverse-RP '(A B C))      ; We run the program, calling our function Reverse-RP on the list '(A B C)
C 
B 
A 
A

Here are the rules for the Towers of Hanoi Problem:

Only one disk can be moved at a time.
Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
No disk may be placed on top of a smaller disk.

We can state the Towers of Hanoi solution for N disks recursively:

Move all the disks on a tower except the last one (N-1 disks) to the tower where you are NOT going. RECURSIVE STEP
Move the bottom disk (Nth disk) to where you ARE going. BASE CASE
Move the tower you previously moved to where you are not going (the N-1 disks) to where you ARE going.

This solution works for any number of disks, from 1 disk to 10,000 disks, but we can state it recursively in three steps. Easy!

Here is a small program, where I give you most of the LISP code, but you have to make a substitution to finish the code.

Problem: Replace the placeholder ?x with a value so that the function adds 7 to any number and returns the result:


(defun add-7 (n)
  (+ n ?x))

The solution:

(defun add-7 (n)
  (+ n 7))

LISP> (add-7 12)
19