[plt-scheme] Some fine distinctions

Hi,

On Tue, 12 May 2009, Matthias Felleisen wrote:

>> Tail recursion vs Accumulative recursion.
>
> A function that uses an accumulator doesn't have to be in tail-recursive 
> shape.

Here's another example (in Common LISP): an implementation of quicksort 
that does not use append.

(defun partition (pivot L &optional small large)
   (cond ((null L)
          (values small large))
         ((<= (first L) pivot)
          (partition pivot (rest L) (cons (first L) small) large))
         (t (partition pivot (rest L) small (cons (first L) large)))))

(defun quicksortam (L &optional a)
   (if (null L)
       a
     (let ((pivot (first L)))
       (multiple-value-bind (less-or-same more)
           (partition pivot (rest L))
         (quicksortam less-or-same
                      (cons pivot (quicksortam more a)))))))


-Arthur