[racket] HtDP: Why is quick-sort considered generative recursion?

On 4/22/11 8:14 PM, Jay wrote:
> Hi,
>
> I don't understand what aspect of the quick-sort algorithm (as presented
> in /How to Design Programs/) makes it an instance of generative
> recursion; it looks to me like a structural problem.
>
> I'd appreciate any clarification.

A structurally recursive program over lists of numbers follows the template:

(define (lon-template lon)
   (cond [(empty? lon) ...]
         [else (first lon) ... (lon-template (rest lon))]))

Quicksort does not follow that template.  Notice that the quicksort 
function makes calls to itself passing in arguments that are not 
sub-components of the original input.  In other words, we are 
*generating* new problems to solve in order to solve the original 
problem of sorting a list.

David