OpenMusic: L-System tree generation using lisp

I am trying to work with a compositional tool called OpenMusic, which is a graphical development environment based on common lisp, and it uses something called "rhythm trees". I am trying to create rhythm trees using a set of rules and in OM this tree must have the following structure:

A tree is a list with two elements
Its first element is a node
Its second element is a list of its children (which can also be trees)

Given a tree depth n, an initial single node tree (1) and transformation rules:

(1) -> (1 2)
(2) -> (1)

It should give:

n = 1 -> (1 (1 2))

Solution

Recursive algorithms for trees/lists are typically written with COND. You figure out what the ending conditions are, and put those first. Then handle atoms, and finally iterate over a list by recursively calling the function on its CAR and CDR, and CONS the results to produce the output list. So the basic template is like:

(defun algo (list)
  (cond
    ((end-condition) suitable-end-value)
    ((atom list) (do-something-with-atom list))
    (t (cons (algo (car list)
             (algo (cdr list))))))

In this case this would be something like:

(defun rhythm-tree (n tree)
  (cond ((zerop n) tree)                 ; First end-condition.
        ((null tree) '())                ; Another end-condition.
        ((atom tree)                     ; An atom: transform into...
         (cons tree                      ; a list of the atom itself...
               (list (rhythm-tree (1- n) ; and a list of children.
                                  (case tree
                                    (1 (list 1 2))
                                    (2 (list 1))
                                    (otherwise '()))))))
        ;; Iterate over elements of a list.
        (t (cons (rhythm-tree n (car tree))
                 (rhythm-tree n (cdr tree))))))

(rhythm-tree 1 1)
;=> (1 (1 2))
(rhythm-tree 2 1)
;=> (1 ((1 (1 2)) (2 (1))))