Урок 8. LISP Рекурсивные функции

LISP   16 декабря 2012  Автор статьи:  

Рекурсивная функция — это такая функция, которая вызывает сама себя с другими параметрами.Самое главное при реализации таких функций это реализовать условие выхода, т.е прописать такое условие, при котором рекурсивный вызов не случится, а сразу вернется какое — нить значение. Так как наши рекурсивные функции в основном будут работать над списками, то необходимо в первой строке проверить, а не передали ли нам пустой список, т.е не равен ли наш параметр нулю, если нет, то вызвать нашу функцию, для этого мы можем воспользовавшись функцией cond или if. Давайте напишем пример какой — нить простой рекурсии, например напишем подсчет факториала:

(defun fuct(a)
(if (equal a 0) 1 (* a (fuct (- a 1))))
)

Таким образом нашу функция возвращает ноль, если мы ищем факториал от нуля и возвращает a * fuct(a-1) в ином случае. Проверим наше утверждение, действительно, при 0, факториал от нуля равен 1, при 1, у нас получается , что результат это 1 умноженная на факториал от нуля, который тоже равен 1, продолжив рассуждения мы получаем, что факториал для двух это 2 умножить на факториал единицы.
Теперь напишем более сложную рекурсию, реализуем функцию member, которая будет проверять, а содержится ли элемент a в списке lst:

(defun member(lst a)
(if null(lst)
NIL
(or (equal (car lst a)) (member (cdr lst) a))
)
)

Данная функция возвращает ложь, если список пустой, а если список не пустой мы берем его первый элемент и сравниваем с элементом а или запускаем функция member на оставшимся списке(без первого элемента), если хоть кто — нибудь вернет T, то результатом будем истина. Теперь напишем реализацию функции rember с помощью функции cond, данная функция будет удалять первое вхождение элемента в массив.

(defun rember(lst a)
(cond ((null lst) nil)
((equal (car lst) a) (cdr lst))
(t (cons (car lst)(rember (cdr lst) a)))

  • Max

    У Вас опечатка во 2 примере в 2 и 4 строке.
    (if (null lst) вместо (if null(lst)
    и
    (equal (car lst) a) вместо (equal (car lst a))

Научиться программировать

  • на Delphi

  • на Java

  • на C++