[racket] Generative recursion

From: wooks . (wookiz at hotmail.com)
Date: Sat Nov 6 13:37:45 EDT 2010

I tried to get you to approach this as though nobody had told you about generative recursion. 

In which case you would/should have tried the tried and tested formula you know, which should have led you to 
(tabulate-div 20) and the simple recursion that follows is (tabulate-div 19). 

You have rightly concluded that 

a) (tabulate-div 19) will give you all the divisors of 19 
b) this is irrelevant to the solution you seek. 

So the inference to draw is 

   (tabulate-div 19) is not relevant to the answer I seek -> 
        whatever led me to (tabulate-div 19) is not going to lead me to the right answer ->
            Now if  simple numeric recursion led me to (tabulate-div 19) ->
                 simple numeric recursion is not going to lead me to the right answer.

So we need something else.

I encouraged you to forget about generative recursion as it is not common parlance, but I'll try to explain it.

With recursion you want to repeat over a smaller instance of the problem. So it needs to shrink somehow
with each iteration.
Up till now the data structures you have encountered have been (or have been made to look)  recursive, so that the 
smaller instance of the problem falls out naturally from the data structure. 

With a list you get a smaller instance with (rest list). With numbers you get a smaller instance with (sub1 n).
Generative recursion is used to describe the instance where you have to perform so form of manipulation of the data
to get a smaller instance because structural recursion will not give you what you want.

You can contrast between the 2 by looking at how the recursive case in gcd-structural is generated and comparing it to how the recursive case in gcd-generative is generated.


So we agree that we need something other than the standard numeric structural recursion.

Now let me embellish (with capitals) slightly what I said in my previous post

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 YOU GENERATE by n AND SEE IF IT GAVE YOU A ZERO REMAINDER.
 That suggests that on each iteration you need to have the original 
value of n available - how are you going to achieve that. 

So before you go any further answer that question.

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

Posted on the users mailing list.