Tail Recursion (was Re: Jade requests)

Subject: Tail Recursion (was Re: Jade requests)
From: David Megginson <dmeggins@xxxxxxxxxx>
Date: Mon, 19 May 1997 13:31:51 -0400
James Clark writes:

 > I've added a -G flag that causes Jade to print a simple stack
 > traceback on errors (it needs a flag because the traceback doesn't
 > make much sense unless optimization of tail-calls is suppressed).

This is actually a good opportunity to mention that Scheme optimizes
tail recursion, so it is OK (perhaps even desirable) to use it in your
DSSSL scripts.  

If you have a background in C (or even in other LISPs), you have
probably been taught to avoid tail-recursion in favour of iteration
whenever possible.  For example, in C this would be an inefficient way
to process a thousand-item list (it would bloat the stack):

  void
  process_item (LIST * list)
  {
    if (list != NULL) {
      /* do something with the current item */
      process_item(list->rest);
    }
  }

The equivalent in Scheme, however, works well, because Scheme
optimizes tail recursion (it does not keep entries on the stack):

  (define (process-item l)
    (cond ((not (null? l))
           ;; do something with the current item
           (process-item (cdr l)))))

I seem to recall that Scheme gurus (of which I am not one) recommend
using tail recursion rather than iteration.  I will leave it to the
computer scientists to correct or expand upon this.


All the best,


David

-- 
David Megginson                 ak117@xxxxxxxxxxxxxxxxxxx
Microstar Software Ltd.         dmeggins@xxxxxxxxxxxxx
University of Ottawa            dmeggins@xxxxxxxxxx
        http://www.uottawa.ca/~dmeggins

 DSSSList info and archive:  http://www.mulberrytech.com/dsssl/dssslist


Current Thread
  • Jade requests
    • Paul Prescod - Wed, 7 May 1997 13:27:09 -0400 (EDT)
      • <Possible follow-ups>
      • James Clark - Sun, 18 May 1997 02:41:56 -0400 (EDT)
        • Paul Prescod - Sun, 18 May 1997 19:03:22 -0400 (EDT)
        • David Megginson - Mon, 19 May 1997 13:28:55 -0400 (EDT) <=