tail recursion

[Arthur Lemmens <lemmens@xxxxxxxxxx>]

Arthur Lemmens wrote:
> For deciding if a function is tail recursive, it doesn't
> matter if it calls itself once or twice. The important question
> is: does the function *do something with the result* of calling itself?

Brandon Ibach replied:
>   That's pretty much what I was getting at with the "double call"
> comment, though I was thinking of it in terms of whether the function
> needs to keep track of its state (such as the values of its
> parameters) across the call.  Obviously, with the two calls, the
> function would need to at least keep track of things across the first
> one, eliminating the possibility of turning the function into a loop.

Yes.
I was just trying to point out that it doesn't help to count
the number of recursive calls.
Here's an example of a function that has two recursive calls, 
but is still tail recursive:

(define count-powers-of-2 (lambda (n)
; Returns the number of 1-bits in the binary 
; representation of <n>.
; E.g. (count-powers-of-2 3)   => 2
;      (count-powers-of-2 16)  => 1
;      (count-powers-of-2 255) => 8
  (let loop ((n n) (count 0))
    (if (zero? n)
      count
      (if (odd? n)
        (loop (quotient n 2) (+ count 1))
        (loop (quotient n 2) count) )))))


Brandon Ibach:
> Perhaps if I can clean up the QSORT stuff sufficiently, 
> it would make a good addition to the DSSSL Procedure
> Library at Mulberry.

Here's a version of qsort (taken from "ML for the Working 
Programmer" by L.C. Paulson, rewritten in Scheme):

(define qsort (lambda (less? ls)
; Sorts LS according to the comparison function LESS?
  (if (or (null? ls) (null? (cdr ls)))
    ls
    (let partition ((pivot (car ls))
                    (left '()) 
                    (right '())
                    (ls (cdr ls)))
      (if (null? ls)
        (append (qsort less? left)
                (cons pivot (qsort less? right)))
        (if (less? (car ls) pivot)
          (partition pivot (cons (car ls) left) right (cdr ls))
          (partition pivot left (cons (car ls) right) (cdr ls)) )))) ))

Paulson notes that "the append can be eliminated by accumulating 
the sorted result in a second argument" but leaves this version 
as an exercise.
You may want to try this exercise yourself. If you do it right,
you'll find that one of the two recursive calls to qsort will
change to a tail recursive call.

Arthur Lemmens


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