Towers of Hanoi - 2

In the video tutorial 1b of the MIT Lisp video tutorials, the solution of the Towers of Hanoi puzzle is expressed as this Lisp definition:

(define (move n from to spare)
  (cond
    ((= n 0) "done" )
    (else)
      (move (-1+ n) from spare to)
      (print-move n from to)
      (move (-1+ n) spare to from))))

I have translated that into DrScheme, using Textual (MzScheme, includes R5RS), which can be found at the end of this posting (see Program).

Now look at the program trace of (move 3 1 2 3), using substitution (as explained in the video tutorial):

(move 3 1 2 3)              ;;  n  T  F  S
  (move (-1+ 3) 1 3 2)      ;;  3  1  2  3
    (move (-1+ 2) 1 2 3)    ;;  2  1  3  2
      (move (-1+ 1) 1 3 2)  ;;  1  1  2  3
        "done"              ;;  0  1  3  2
      (print-move 1 1 2)    ;;  1  1  2  3
      (move (-1+ 1) 3 2 1)  ;;  1  1  2  3
        "done"              ;;  0  3  2  1
    (print-move 2 1 3)      ;;  2  1  3  2
    (move (-1+ 2) 2 3 1)    ;;  2  1  3  2
      (move (-1+ 1) 2 1 3)  ;;  1  2  3  1
        "done"              ;;  0  2  1  3
      (print-move 1 2 3)    ;;  1  2  3  1
      (move (-1+ 1) 1 3 2)  ;;  1  2  3  1
  (print-move 3 1 2)        ;;  3  1  2  3
  (move (-1+ 3) 3 2 1)      ;;  3  1  2  3
    (move (-1+ 2) 3 1 2)    ;;  2  3  2  1
      (move (-1+ 1) 3 2 1)  ;;  1  3  1  2
        "done"              ;;  0  3  2  1
      (print-move 1 3 1)    ;;  1  3  1  2
      (move (-1+ 1) 2 1 3)  ;;  1  3  1  2
        "done"              ;;  0  2  1  3
    (print-move 2 3 2)      ;;  2  3  2  1
    (move (-1+ 2) 1 2 3)    ;;  2  3  2  1
     (move (-1+ 1) 1 3 2)   ;;  1  1  2  3
        "done"              ;;  0  1  3  2
     (print-move 1 1 2)     ;;  1  1  2  3
     (move (-1+ 1) 3 2 1)   ;;  1  1  2  3
        "done"              ;;  0  3  2  1

I have used indentation to show how deep the trace is in the iteration (in essence, how low the value of n is), and color coding to indicate which of the three steps is being executed inside the combination of the alternative expression (see MIT/GNU Scheme - Conditionals) as used in the definition above. Furthermore, I have added in the comments fields the substituted values for n, from, to, and spare (n F T S).

As you can see, this is a recursive process, and certainly not an iteration. Now, can we rewrite this program, so it does an iterative process to solve the puzzle, instead of the current recursive process?

Program

;; Towers of Hanoi, solution 1

;; move : number number number number -> string
;; calculate moves for Towers of Hanoi
;; side effect: display move disk: from -> to
;; example:
;; (move 3 1 2 3)
;; 1: 1 -> 2
;; 2: 1 -> 3
;; 1: 2 -> 3
;; 3: 1 -> 2
;; 1: 3 -> 1
;; 2: 3 -> 2
;; 1: 1 -> 2
;; "done"
(define (move n from to spare)
  (cond
    [(= n 0) "done" ]
    [else (begin
            (move (-1+ n) from spare to)
            (print-move n from to)
            (move (-1+ n) spare to from))]))
(define (print-move n from to)
  (begin
    (display n)
    (display ": ")
    (display from)
    (display " -> ")
    (display to)
    (newline)))
(define (-1+ x)
  (- x 1))