[racket] I don't understand structural recursion.

From: Damien Lee (charlicon at gmail.com)
Date: Sat Sep 17 18:00:13 EDT 2011


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))
          (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?


Posted on the users mailing list.