Lisp рекурсия

[Horror89]

Здравствуйте , возникла проблема с выполнением задания на Lisp .
Задача располагалось в разделе рекурсии , я пока в принципе не много Lisp знаю и с самой целью задачи не разбирался. Был бы очень благодарен если бы мне кто нибудь объяснил рекурсию на конкретных программных примерах(lisp) , а не в математическом виде.
А если кто-то поможет и с самой задачей был бы ещё более благодарен =)))
Вот собственно задача.

Разработать функцию, находящую теоретико-множественную разность двух списков.
Например:
Вход: (1 2 3 4 5), (4 5 6 7).
Выход: (1 2 3).

[netrino]

А обязательно рекурсивно? )
В принципе рекурсия в lisp не отличается от рекурсии в каком-либо другом языке(включая математику)) - это выражение функции через саму себя.
Классический пример ф-ции нахождения факториала рекурсивно:

(defun factorial (x)
  (if (= x 0)
    1
    (* x (factorial (- x 1)))))

Надеюсь тут всё понятно )
То бишь ф-ция вызывает сама себя, чтобы получить конечный результат, при этом обязательно должно быть некое условие выхода(в этом случае таким условием является равенство параметра x нулю, когда x = 0 рекурсивного вызова более не происходит, а возвращается конкретный результат - 1)

[Horror89]

"В принципе рекурсия в lisp не отличается от рекурсии в каком-либо другом языке(включая математику))." Я вообще так и не думал=) просто в принципе понимание этого вызова самой себя вызывает затруднение=)) . Спасибо за помощь.

[netrino]

Сообщение от Horror89

просто в принципе понимание этого вызова самой себя вызывает затруднение=))

Да, это бывает сложно по-началу представить )
Можете поискать в интернете по теме, там есть хорошие пояснения, с иллюстрациями и т.д. )
Вызов самой себя ничем не отличается от вызова другой ф-ции, точно также управление передаётся в вызываемую ф-цию, а вызывающая ф-ция "ожидает" когда вызываемая завершится и вернёт управление ) При этом вызываемая ф-ция может вызвать себя ещё раз и ожидать, когда уже от вызванной ею ф-цией вернётся управление. При это сохраняется состояние ф-ции(значение её переменных и т.д). То есть, если изначально ф-ция факториал была вызвана со значением 4, то вот что происходит:
1. ф-ция проверяет, равен ли её параметр нулю. Очевидно что не равен . Тогда она вызывает себя ещё раз с тем же параметром, но меньши на единицу.
2. ф-ция вызвана с параметром 3, опять не ноль, опять вызывает саму себя, но уже с параметром 2.
3. опять не ноль - вызов с параметром 1.
4. не ноль - вызов с параметром 0.
5. ноль ф-ция "возвращает" число 1.
6. управление получает ф-ция, которая "выше по уровню вложенности вызова", она умножает свой, полученный параметр х, который равен 1, на результат выполнения ф-ции, которую она вызвала с параметром 0 - 1.
7. теперь управление получает всё та же ф-ция, но на ещё один уровень вложенности выше, при этом умножает свой х, равный двум на результат, который вернула эта ф-ция, уровнем вложенности ниже, - 1.
8. ... на ещё один уровень выше ... свой х, равный 3, на ... ниже, - 2
9. ... на ещё один уровень выше ... свой х, равный 4, на ... ниже, - 6. И это самый "верхний" по уровню вложенности вызов )
получаем 24 =)

[Horror89]

Да да когда писать начал разобрался=) как оказалось единственное что я не понимал что функция вызывается с новым параметром .