;Solving the Tower of Hanoi in Scheme
(define (move N from to spare)
  (if (= N 0)
      (display "")
      (begin 
        (move (- N 1) from spare to)
        (display "move from ")(display from)(display " to ")(display to)(display "\n")
        (move (- N 1) spare to from))))

Sample run:

> (move 3 'start 'end 'spare)
move from start to end
move from start to spare
move from end to spare
move from start to end
move from spare to start
move from spare to end
move from start to end

How can we solve it iteratively (ie via tail recursion) ?

Warning: reading futher will reveal an iterative version.

It requires a lot more code and not in any way faster.

; Solving the Tower of Hanoi iteratively in Scheme
(define (moveIter N from to spare)
  (moveIterImpl N from to spare () ()))

(define (moveIterImpl N from to spare displayList moveList)
  (if (= N 0)
      (if (null? displayList)
         (display "")
         (begin
           (output (car displayList))
           (if (null? moveList)
               (display "")
               (eval (toMoveIterCmd moveList displayList)))))
      (moveIterImpl (- N 1) from spare to 
        (cons (toPair from to) displayList)
        (cons (toMoveParam (- N 1) spare to from) moveList))))

(define (toMoveIterCmd moveList displayList)
  (cons 'moveIterImpl 
        (cons (car (car moveList))
              (cons (cons 'quote (cons (car (cdr (car moveList))) ()))
                    (cons (cons 'quote (cons (car (cdr (cdr (car moveList)))) ()))
                          (cons (cons 'quote (cons (car (cdr (cdr (cdr (car moveList))))) ()))
                                (cons (cons 'quote (cons (cdr displayList) ()))
                                      (cons (cons 'quote (cons (cdr moveList) ()))
                                            ()))))))))

(define (toMoveParam N from to spare)
  (cons N (cons from (cons to (cons spare ())))))

(define (output displayItem)
  (begin
    (display "move from ")(display (car displayItem))
    (display " to ")(display (car (cdr displayItem)))
    (display "\n")))

(define (toPair from to)
  (cons from (cons to ())))

To run, simply type:

> (moveIter 3 'start 'end 'spare)