From ...
From: Erik Naggum <erik@naggum.no>
Subject: Re: Benefits of tail recursion (was: Cost of Recursion)
Date: 2000/02/15
Message-ID: <3159573115430567@naggum.no>#1/1
X-Deja-AN: 585968543
References: <38A0285E.3CC94DFF@raytheon.com> <86hffhu9ty.fsf@g.local> <87v29b$hke$1@eve.enteract.com> <86r9ekzoex.fsf@g.local> <889ro1$a0r$1@eve.enteract.com>
mail-copies-to: never
Content-Type: text/plain; charset=us-ascii
X-Complaints-To: newsmaster@eunet.no
X-Trace: oslo-nntp.eunet.no 950585576 20311 195.0.192.66 (15 Feb 2000 03:32:56 GMT)
Organization: Naggum Software; +47 8800 8879 or +1 510 435 8604; fax: +47 2210 9077; http://www.naggum.no
User-Agent: Gnus/5.0803 (Gnus v5.8.3) Emacs/20.5
Mime-Version: 1.0
NNTP-Posting-Date: 15 Feb 2000 03:32:56 GMT
Newsgroups: comp.lang.lisp

* Robert Munyer <munyer@mcs.com>
| For me, a loop written with ITERATE is easier to read than the same loop
| written with DO.  With ITERATE, the process of computation has a more
| linear "flow" through the text of the function.  With DO, the step forms
| are interleaved with the initialization forms, which makes the flow of
| computation feel like it's been "scattered" all over the text of the
| function.

  what's keeping you from writing an ITERATE macro that expands into DO
  (or, rather, TAGBODY and GO forms)?  it should be eminently doable in the
  majority of cases where it is indeed only (tail-recursive) iteration.

| In summary: the next time you're programming a loop, and the code doesn't
| seem to "fit," try using recursion.  You might be surprised how well it
| works.

  there is no semantic difference between (PSETQ FOO X BAR Z) (GO TAG) and
  (ITERATOR :FOO X :BAR Z) as long as both "resolve" to tail recursion.
  (I'm using keyword arguments only to be explicit.)

| In fact, I think the whole concept of "iteration vs. recursion" is a
| wrong way to think, a left-over distinction from the days before we
| understood tail recursion.  I think it makes sense to think of a
| tail-recursive program as being both iterative AND recursive.

  I agree with you on this.

| Now, on to the example I promised earlier.  Below is a function I wrote a
| couple of years ago.  As I recall, I tried several times to write it with
| DO, and every time the code came out UGLY.  So I tried doing it with
| recursion, and it "just worked."  It was easier to write, and easier to
| read, and just as efficient as the version I wrote with DO.
| 
| ; Returns INV such that (= (MOD (* NUMBER INV) MODULUS) (GCD NUMBER MODULUS)).
| ; Note that if NUMBER and MODULUS are relatively prime, the GCD is 1, and INV
| ; is the multiplicative inverse of NUMBER over the Galois field of MODULUS.
| 
| (defun mod-inverse (number modulus)
|   (check-type number  (integer 1))
|   (check-type modulus (integer 1))
|   (iterate iter ((a modulus) (b number) (c 0) (d 1))
|     (multiple-value-bind (q r) (floor a b)
|       (cond ((plusp r) (iter b r d (- c (* q d)))) ; thanks Euclid!
|             ((minusp d) (+ d modulus))
|             (t d)))))

(do ((a modulus) (b number) (c 0) (d 1))
    ((multiple-value-bind (q r) (floor a b)
       (if (plusp r) (psetq a b b r c d d (- c (* q d))) t))
     (if (minusp d) (+ d modulus) d)))

  it _is_ unfortunate that DO et al were invented so long before multiple
  values that we sometimes have to expand out the forms manually.

  hope this helps.

#:Erik