[racket] Generative Recursion

Forget about the term generative recursion for a second.

I've coined a phrase that for me encapsulates much of the approach of the Design Recipe - I call it Delta Programming.

Why - well you have a result you would like, you have your input and you have in your template a bunch of expressions - lets call them partial results - which are derived from your inputs.

Assuming you have listed those partial results, often times the problem reduces to picking the expression that yields the partial result nearest to your goal and working out the adjustments needed to give you your answer. So instead of programming from a blank slate, you are programming what needs to change (i.e the delta), given the partial results.

So you came up with a test

(tabulate-div 20) should equal (list 1 2 4 5 10 20) 

Lets start with what you know. 
Previously you have been given a template for numeric recursion

(define (tabulate-div n)
    (cond
       [(zero? n) ......]
       [else .........n..........................................
                ........(sub1 n)................................
                ........(tabulate-div (sub1 n))........]))

the meaning of n and (sub1 n) is apparent, but what does (tabulate-div (sub1 n)) mean.

Use your example. If (tabulate-div 20) means give me all the divisors of 20 what does (tabulate-div (sub1 20)) give.
Well thats (tabulate-div 19). What does it mean and how is it relevant to what I am trying to achieve.

Lets say we figure out a simple recursive call isn't going to help us here, what else can we do.

Well some kind of recursive call is obviously necessary (after all this is the section on generative recursion).
Lets look at (tabulate-div (sub1 n)) again but think of it as  (tabulate-div (function-that-generates-the-next-problem)) and 
we have just tried it with  function-that-generates-the-next-problem set to  (sub1 n). 
Did it work?

Really we want (tabulate-div (function-that-generates-the-next-problem)) to give us (list 2 4 5 10 20) and to combine that answer 
with the answer to the 1st problem which is 1. 

So the solution begins to look something like  

   (combine (solution involving n)
                    (tabulate-div (function-that-generates-next-problem))

Lets take your solution to the 1st problem - you generated 1 by dividing n by n (i.e 20/20) and your idea was to divide each successive problem by n.

Hmmm? That suggests that on each iteration you need to have the original value of n available - how are you going to achieve that.

Lets say you figure that out, the next number that features in your solution is 2 and you said you were going to do divisions.

Well if n is going to feature in those divisions, we either have x/n = 2 or n/x = 2. 

Right what is n going to be? 
Given we have figured n, what expression are we going to use to get our 2nd expression - x/n or n/x.
Given we have chosen between these expressions (function-that-generates-next-problem) has to be something that will successively generate x's to give us the (2 4 5 10 20).

Is every x we generate going to contribute to our answer? 
If not how do we decide which x's to keep and which not to?

Try thinking along those lines and see how you get on.











 		 	   		  
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20101105/b61a68fa/attachment.html>