# [racket] I don't understand structural recursion.

 From: Damien Lee (charlicon at gmail.com) Date: Sat Sep 17 18:00:13 EDT 2011 Previous message: [racket] list->values Next message: [racket] I don't understand structural recursion. Messages sorted by: [date] [thread] [subject] [author]

```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)))

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.

```

 Posted on the users mailing list. Previous message: [racket] list->values Next message: [racket] I don't understand structural recursion. Messages sorted by: [date] [thread] [subject] [author]