Задача на использование рекурсии - Lisp (229242)

Формулировка задачи:

Описать функцию с использованием рекурсии. Даны списки

list1

list2

. Реализовать функцию, которая удаляет из

list1

все элементы-списки, которые соответствуют тому же множеству, что и

list2

. Например: для списков:

list1

='(1(2 2 3) 4 (3 2 3) 5),

list2

='(3 2 3 2) результатом будет '(1 4 5).

Решение задачи: «Задача на использование рекурсии»

Листинг программы

(defun is-equal (lst1 lst2)
  (if (atom lst1) nil  
      (and (not (remove-if (lambda (x) (member x lst2)) lst1))
           (not (remove-if (lambda (x) (member x lst1)) lst2)))))
   
(defun task (lst1 lst2)
   (cond ((null lst1) nil)
         ((is-equal (car lst1) lst2) (task (cdr lst1) lst2))
         (t (cons (car lst1) (task (cdr lst1) lst2)))))
 
==> TASK
 
(task '(1 (2 2 3) 4 (3 2 3) 5) '(2 3 3 2))
 
==> (1 4 5)

Объяснение кода листинга программы

В коде представлена реализация функции task, которая выполняет следующие действия:

task принимает два аргумента: lst1 и lst2.
Если lst1 — это nil, то функция возвращает nil.
Если is-equal возвращает nil, то функция вызывает себя рекурсивно для cdr lst1 и lst2.
Если is-equal возвращает не nil, то функция возвращает cons с первым элементом lst1 и вызовом функции task для cdr lst1 и lst2. Функция is-equal проверяет, являются ли два списка равными. Она принимает два аргумента: lst1 и lst2. Если lst1 является атомом, то функция возвращает nil. В противном случае она проверяет, содержатся ли все элементы lst1 в lst2 и наоборот. Если это так, то функция возвращает nil, иначе возвращает t. В данном примере функция task вызывается с двумя списками: lst1 — (1 (2 2 3) 4 (3 2 3) 5) и lst2 — (2 3 3 2). Функция is-equal вызывается для проверки равенства двух списков. Первый вызов функции is-equal проверяет, является ли первый элемент lst1 равным lst2. Второй вызов функции is-equal проверяет, являются ли два оставшихся элемента lst1 равными lst2. Поскольку оба вызова функции is-equal возвращают nil, функция task возвращает cons с первым элементом lst1 и вызовом функции task для оставшихся элементов lst1 и lst2. В результате выполнения функции task будет возвращен список (1 4 5).