CODEWITHSUNDEEP
variablesrecursioncommon-lisp
caramel1995
caramel1995

Reputation: 3055

Prevent recursive function from reallocating a new variable

One of my task in programming class is "Tower Of Hanoi" , the language I was using is Common Lisp and the source code is as follow :

The Code :

Variables:

(defparameter *Source*      "Peg 1")
(defparameter *Spare*       "Peg 2")
(defparameter *Destination* "Peg 3")

I want the above variable declaraction to be inside the function

(defun towers-of-hanoi (disks)

;disks accept list as parameter , for e.g `(s m l)

  (let ((tempPeg))
    (if (= (list-length disks) 1)
      (format t "Move ~{~A~} from ~A to ~A~%"
              (last disks) *Source* *Destination*) 
      (progn
        (setq tempPeg *Spare*)
        (setq *Spare* *Destination*)
        (setq *Destination* tempPeg) 

        (towers-of-hanoi (subseq disks 0 (- (list-length disks) 1)))

        (setq tempPeg *Spare*)
        (setq *Spare* *Destination*)
        (setq *Destination* tempPeg)

        (format t "Move ~{~A~} from ~A to ~A~%"
                (last disks) *Source* *Destination*) 

        (setq tempPeg *Spare*)
        (setq *Spare* *Source*)
        (setq *Source* tempPeg)
        (towers-of-hanoi (subseq disks 0 (- (list-length disks) 1)))
        (setq tempPeg *Spare*)
        (setq *Spare* *Source*)
        (setq *Source* tempPeg)
        (format t "")))))

The Question :

1.)I'm using recursive algorithm to solve this problem , as I know in this algorithm , the 3 variables (Source , Spare and Destination) must interchange with each other (by some rules) . If I place the defvar inside the function , even though I carry out this 3 operations (setq tempPeg *Spare*) (setq *Spare* *Destination*) (setq *Destination* tempPeg) before calling the towers-of-hanoi function again but the function again redefine the 3 variables back through it's original value .

2.)What I wanted to know is that is it possible for me to place the declaraction of the 3 variables inside the function and still able to prevent the function from redefining the same variable for each recursive called?

P/S the assignment only allows me to define a function header that accept disks as the one and only argument but not the Source , Spare , and Destination rod.

Upvotes: 0

Views: 201

Answers (2)

Rainer Joswig
Rainer Joswig

Reputation: 139261

Your use of lists is not idiomatic. Remember lists in Lisp are singly linked cons cells. All operations which traverse lists or work from the end of lists are inefficient.

To answer your question:

(defun do-something (a)
   (let ((foo 42))                            ; binding
      (labels ((do-something-recursively (b)  ; local recursive function
                 (...)))
        (do-something-recursively a))))

Upvotes: 1

Joshua Taylor
Joshua Taylor

Reputation: 85853

There are probably two good options here. The first is that since the function depends on a few values, the function could take them as arguments. That's probably the clearest way to do what you're trying to do, and it makes the recursive calls cleaner, because you don't need to rebind or assign a bunch of variables before making the call. For instance, here's a simple recursive function:

(defun swap-until-x-is-zero (x y)
  (print `(swap-until-zero ,x ,y))
  (unless (zerop x)
    (swap-until-x-is-zero (1- y) (1- x))))

CL-USER> (swap-until-x-is-zero 3 5)

(SWAP-UNTIL-ZERO 3 5) 
(SWAP-UNTIL-ZERO 4 2) 
(SWAP-UNTIL-ZERO 1 3) 
(SWAP-UNTIL-ZERO 2 0) 
(SWAP-UNTIL-ZERO -1 1) 
(SWAP-UNTIL-ZERO 0 -2) 
NIL

Now, if that's supposed to start with some reasonable default values, then those function arguments could be made optional:

(defun swap-until-x-is-zero (&optional (x 3) (y 5))
  (print `(swap-until-zero ,x ,y))
  (unless (zerop x)
    (swap-until-x-is-zero (1- y) (1- x))))

and then you can simply call (swap-until-x-is-zero):

CL-USER> (swap-until-x-is-zero)

(SWAP-UNTIL-ZERO 3 5) 
(SWAP-UNTIL-ZERO 4 2) 
(SWAP-UNTIL-ZERO 1 3) 
(SWAP-UNTIL-ZERO 2 0) 
(SWAP-UNTIL-ZERO -1 1) 
(SWAP-UNTIL-ZERO 0 -2)

It should be clear how this approach could be applied to the Hanoi problem; you'd simply add three optional arguments to the hanoi and recursively call it with the altered values:

(defun towers-of-hanoi (disks &optional (source "Peg 1") (spare "Peg 2") (destination "Peg 3"))
  ...
  ;; instead of:
  ;;   (progn
  ;;     (setq tempPeg *Spare*)
  ;;     (setq *Spare* *Destination*)
  ;;     (setq *Destination* tempPeg) 
  ;;     (towers-of-hanoi (subseq disks 0 (- (list-length disks) 1))))
  ;; we do:
  (let ((tempPeg spare))
    (towers-of-hanoi (subseq disks 0 (- (list-length disks) 1))
                     source      ; stays the same
                     destination ; swap destination and spare
                     spare))     ; swap destination and spare
  ...)

That said, sometimes there are enough parameters that it's easier to just use special variables (i.e., dynamically scoped variables) for them (though I don't think that this is such a case), and to get those, you can use the special declaration:

(defun towers-of-hanoi (disks)
  (declare (special *source* *spare* *destination*))
  (let ((tempPeg))
    (if (= (list-length disks) 1)
        (format t "Move ~{~A~} from ~A to ~A~%" (last disks) *Source* *Destination*) 
        (progn
          (setq tempPeg *Spare*)
          (setq *Spare* *Destination*)
          (setq *Destination* tempPeg) 
          (towers-of-hanoi (subseq disks 0 (- (list-length disks) 1)))
          ...))))

You'll still have to establish the initial bindings of the variables, though, so for the outermost call you'd have to do something like:

(defun hanoi-driver (disks)
  (let ((*source* "Peg 1")
        (*spare* "Peg 2")
        (*destination* "Peg 3"))
    (declare (special *source* *spare* *destination*))
    (hanoi disks)))

I think that that simply adding the three &optional variables to hanoi is ultimately a cleaner solution, personally.

Upvotes: 2

Related Questions