remove with deep recursion in lisp

How can I implement the remove function with deep recu开发者_如何学编程rsion?

I know how to write remove in shallow recursion, but it's hard to change this into deep recursion.

 (myremove '(1 2) '(1 ((1 2) 3) (4 (5 ((1 2) 5))))) -> (1 (3) (4 (5 (5))))

I suppose by "deep recursion" you're referring to recursion over a tree instead of recursion over a list?

The more low-level answer to this is to recurse down both the car and the cdr of the cons cells, instead of just the cdr. Though I'ld prefer to use higher order functions, in this case calling mapcar recursively:

(defun myremove (item tree)
  (if (atom tree)
      tree
      (mapcar (lambda (subtree) (myremove item subtree))
              (remove item tree :test #'equal))))

EDIT: Here's a low-level solution:

(defun myremove (item tree)
  (cond ((atom tree)
         tree)
        ((equal item (car tree))
         (myremove item (cdr tree)))
        ('otherwise
         (cons (myremove item (car tree))
               (myremove item (cdr tree))))))