<div id="header">

Generative Recursion

...

HTML
<div id="content">

HTML
<strong>

HTML
<font color="red">

Instructions for students & labbies:

HTML
</font>

HTML
</strong>

Students Students should use DrScheme, following the design recipe,
on the exercises at their own pace,
while labbies wander among the students, answering questions,
bringing the more important ones to the lab's attention.

HTML
<A NAME="recipe">

Generative Recursion Design Recipe Review

...

...

</A>

In class, we concluded that we now have presented a new more general methodology for use with
developing Scheme functions called generative recursion. If
To develop a function is generative recursive, we modify our
use a generalized design recipe with that incorporates the following changes:

HTML
<UL class="MsoBodyTextIndent">

HTML
<LI class="MsoBodyTextIndent">

...

• When making function examples, we need even more examples, as they help us

...

• to find the algorithm we will use.

...

HTML
</li>

...

...

<LI class="MsoBodyTextIndent">

• When making a template, we don't follow the structure of the data.

...

HTML
<UL>

...

• Instead, we ask ourselves six questions:

...

• 1. What is (are) the trivial case(s)?

...

HTML
</li>

...

• 2. How do we solve the trivial case(s)?

HTML
</li>

HTML
<LI>

...

• 1. For the non-trivial case(s), how many subproblems do we use?

...

HTML
<LI>

• 1. How do we generate these subproblems?

HTML
</li>

HTML
<LI>

...

• 1. Can we combine the results of these subproblems

...

HTML
</li>

...

• 1. to solve the given problem?
  2. How do we combine the results of these subproblems?
     

HTML
</li>

HTML
</UL>

• 1. *We use the answers to the preceding questions to fill in the following very general template:

     HTML
     <PRE>

     ...

     • 1. Code Block
          (define

     ...

     • 1. (f _args

     ...

     • 1. _)

     ...

     ...

     • 1. (cond

     ...

     • 1. [

     ...

     • 1. (_trivial_? _args

     ...

     • 1. )) (_solve-trivial_ _args

     ...

     • 1. _)

     ...

     • 1. ]

     ...

     ...

     • 1. [else

     ...

     • 1. (_combine_ (f (_generate-subproblem-1_ _args_))

     ...

     • 1. ...

     ...

     • 1. (f (_generate

     ...

     • 1. -subproblem-n_ _args_)))]))

     ...

     • 1. *

     HTML
     </PRE>

     HTML
     </li>

     HTML
     <LI class="MsoBodyTextIndent">

     • 1. We add a step to reason about why our algorithm terminates,

     ...

     • 1. since this is no longer provided by simply following the structure

     ...

     • 1. of the data.

     ...

     HTML
     </li>

     HTML
     </UL>

     ...

     Converting a token stream to a list input stream

     ...

     The Scheme reader reads list inputs rather than symbols or characters where a list input is defined by the following set of mutually recursive data definitions:

     ...

     A general list is either:

     • empty ,
     • (cons i lagl) where i is an input and l agl is a general list.

     Note that the second clause above could be written as the following two clauses:

     ...

     Your task is to write the core function listify used in an idealized Scheme reader
     stream. listify converts a list of tokens, where a token is defined below, to
     a list of inputs as defined above.

     ...

     • any built-in Scheme value (including symbol, boolean, number, string, empty
       (the empty list), etc.; or
     • (make-open), or
     • (make-close)
       given the structure definitions

     ...

     in your program. As a rough guideline follow the parse.ss (https:wikiriceedudisplayCSWIKI211lab04parsess) program that we wrote in class on Monday, Feb 2. Note that finding the first input is more involved than finding the first line. You will probably want to explicitly check for errors in the input because they correspond to natural tests on the form of the input.

     ...

     ...

     <a name = "insertVsQuick">

     Insertion Sort vs. Quicksort

     ...

     In class, we've described two different ways of sorting numbers,
     insertion sort and quicksort.

     Code Block

     ;; insertion sort (define (isort lalon) (cond [(empty? lalon) empty] [(cons? l) (insert (first l) (isort (rest l)))])) (define (insert new sortedl) (cond [(empty? sortedl) (list new)] [else (cond [(&lt; new (first sortedl)) (cons new sortedl)] [else (cons (first sortedl) (insert new (rest sortedl)))])])) ;;;;;;;;;;;;;;;;; (define (qsort l) [(cons? (cond alon) (insert (first alon) (isort (rest alon)))])) (define (insert new sortedlon) (cond [(empty? lsortedlon) (list emptynew)] [else (if (< new [(cons?first lsortedlon) (local [(define pivot (firstcons new lsortedlon))] (cons (first sortedlon) (defineinsert ltnew (filter (lambda (n) (&lt; n pivot)) l)) rest sortedlon))))])) ;; quicksort (adapted to functional lists) (define (qsort alon) (cond [(empty? alon) empty] [(cons? alon) (define eq (filterlocal [(lambdadefine (n)pivot (= n pivot)) lfirst alon)) (define gtother (filter (lambda (n) (&gt; n pivot)) l))]rest alon)) (append (qsortdefine lt) lesser (filter (lambda (n) (<= n pivot)) other)) eq (define greater (filter (lambda (n) (> n pivot)) other))] (append (qsort lesser) (list pivot) (qsort gtgreater)))]))

     So we have two fundamentally different approaches to sorting a list
     (and there are lots of others, too).
     It seems unsurprising that each might behave differently.
     Can we observe this difference? Can we provide explanations?
     We'll do some timing experiments,
     outline the theoretical analysis,
     and see if the two jive.

     ...