[racket] 26.1.1 tabulate-div

From: Justin Zamora (justin at zamora.com)
Date: Sun Nov 7 12:40:07 EST 2010

Your problem is that you are not using generative recursion.
Structural recursion is based on breaking down the structure of the
input into its parts, recursing on the parts, then combining the
results to get the final answer.  Since your solution is based on
breaking down n into its divisors, you are really doing a structural
recursion on n, not a generative recursio.

The point of generative recursion is that there are problems that are
not based on the structure of the input and need to recurse on
something else.  For example, the move-ball example of Section 25.1
recurses on the position of the ball, not on the structure of the ball

To solve this problem, you need to stop thinking about breaking down
n, and think about another method of finding out which numbers are the
divisors of n.


On Thu, Nov 4, 2010 at 9:16 PM, Ken Hegeland <hegek87 at yahoo.com> wrote:
> I had made a previous post on this subject and have spent a few days trying to work out this problem but I feel like I have hit a dead end, and I am hoping I can get some advice from a few people with more experience than I.
> The code I have managed to create so far is:
> (define(find-div n i)
>   (cond
>     [(=(remainder n i)0)i]
>     [else(find-div n(sub1 i))]))
> ;(find-div 20 3)
> (define(tabulate-div n)
>   (cond
>     [(= n 1)(list 1)]
>     [else(append
>           (cons n empty)
>           (tabulate-div(find-div n(sub1 n))))]))
> (tabulate-div 20)
> I believe that I understand how generative recursion, and I have spent a lot of time attempting to figure this problem out in a much more complex way. The above code seems much easier to read and understand, but, it suffers similar problems as the other things I have tried. Mainly, it doesn't produced the wanted answer, it's close, but not quite there.
> (tabulate-div 20) should equal (list 1 2 4 5 10 20)
> However, with this code the answer given is (list 20 10 5 1).
> I have figured out that if I somehow divide 20 by each number in the list I get
> (list(/ 20 20)(/ 20 10)(/ 20 5)(/ 20 1))=(list 1 2 4 20) which seems a little closer, but still not quite there. Although this would only be close and not all the way there, I feel its a step in the right direction. My problem is that if I add a local definition of:
> (local((define q(/ n (find-div n n))))
> it produces an incorrect answer. This would give me(list(/ 20 20)(/ 10 10)(/ 5 5)(/ 1 1))
> Maybe I don't understand how generative recursion works exactly. I could really use some advice, this problem is starting to aggravate me.
> _________________________________________________
>  For list-related administrative tasks:
>  http://lists.racket-lang.org/listinfo/users

Posted on the users mailing list.