Path: utzoo!attcan!uunet!zephyr.ens.tek.com!uw-beaver!ubc-cs!manis
From: manis@cs.ubc.ca (Vincent Manis)
Newsgroups: comp.edu
Subject: Re: Recursion Summary
Message-ID: <10250@ubc-cs.UUCP>
Date: 27 Oct 90 01:37:45 GMT
References: <9882@milton.u.washington.edu> <9893@milton.u.washington.edu> <1990Oct25.145621.13691@watdragon.waterloo.edu>
Sender: news@cs.ubc.ca
Distribution: na
Organization: Institute for Pure and Applied Eschatology
Lines: 34

Quicksort's recursion is quite interesting. Because there's, even with
the cleverest partitioning technique, a non-zero probability that you
will select pessimal pivots which require O(n) stack space, it's worth
taking the time and effort to be careful about which partition you sort
recursively. 

This results in a variety of Quicksort which looks like this (in Scheme)

(define Quicksort
  (lambda (a left right)
    (let ((i 0) (j 0))
      (let ((partition (lambda ... the partitioning code, sets i and j)))
         (partition)
         (if (< (- i left) (- right j))
            (begin      ; Left partition is smaller. 
              (Quicksort a left i)
              (Quicksort a j right))
            (begin      ; Else: right partition is smaller. 
              (Quicksort a j right)
              (Quicksort a left i)))))))

In this example, we always sort the larger partition tail-recursively
(i.e., iteratively), and sort the smaller partition
non-tail-recursively. This bounds the stack growth to O(lg n), and is
therefore a desirable improvement, or so I tell my students. 

This is the sort of optimization I would never expect a compiler (even
one designed by Guy Steele) to do, which is why people have to be aware
of tail recursion. 
--
\    Vincent Manis <manis@cs.ubc.ca>      "There is no law that vulgarity and
 \   Department of Computer Science      literary excellence cannot coexist."
 /\  University of British Columbia                        -- A. Trevor Hodge
/  \ Vancouver, BC, Canada V6T 1W5 (604) 228-2394