[racket] I don't understand structural recursion.

Do you have some examples? Concrete examples of possible input values
and what you expect the corresponding output to look like? And if the
function expects integers as input, then what is the difference in the
output between two successive input values like 2 and 3? 4 and 5? 0
and 1?


On Sat, Sep 17, 2011 at 6:00 PM, Damien Lee <charlicon at gmail.com> wrote:
> Hello,
>
> I should probably warn you that this is a homework question, but I have
> tried to solve it, honestly.
>
> "Construct a program that outputs (in some order) all structurally distinct
> binary trees of n nodes.  Two trees are considered structurally distinct if
> they have different numbers of nodes or if their left or right subtrees are
> structurally distinct."
>
> Here's my attempt,
>
> (define-struct tree (left right))
>
> ;; trees : Integral -> (ListOf Tree)
> ;; Return a list of all structurally distinct binary trees containing
> ;; N nodes.
> (define (trees N)
>  (cond ((< N 1) empty)
>        ((= N 1) (make-tree empty empty))
>        (else
>         (map (lambda (root)
>                (let ((left-tree  (trees (- root 1)))
>                      (right-tree (trees (- N 1 root))))
>                  (make-tree left-tree right-tree)))
>              (build-list N add1)))))
>
> I'm ashamed to point out that my function doesn't comply with my contract.
> That's my problem: I end up inserting lists of trees instead of structures
> into my tree's children. I can't see a away to avoid making a list in the
> recursive calls, though.
>
> I'm all tangled up with this. Can anyone help me out?
>
> Thanks,
> Damien.
> _________________________________________________
>  For list-related administrative tasks:
>  http://lists.racket-lang.org/listinfo/users
>