lisp - 在 lisp 中用深度递归删除

Question

如何使用深度递归实现删除功能？

我知道如何在浅递归中编写 remove，但是很难将其更改为深度递归。

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

Answer 1

我想您所说的“深度递归”是指对树的递归而不是对列表的递归？

更底层的答案是递归 car 和 cons 单元的 cdr，而不仅仅是 cdr。虽然我更喜欢使用高阶函数，但在本例中递归调用 mapcar:

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

编辑:这是一个低级别的解决方案:

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