На этом шаге мы рассмотрим примеры использования рекурсии по аргументам.
Будем говорить, что рекурсия простая, если вызов функции встречается в некоторой ветви программы лишь один раз. Простой рекурсии в императивном программировании соответствует обыкновенный цикл.
Если в качестве результата функция возвращает значение другой функции, и рекурсивный вызов участвует в вычислении аргументов этой функции, то будем говорить о присутствии в функции рекурсии по аргументам.
Пример 1. Вычисление факториала натурального числа X. Поставленная задача решается с помощью функции, которая принимает значение, равное единице при равенстве аргумента нулю, а во всех остальных случаях равна произведению аргумента на значение этой же функции от аргумента, уменьшенного на единицу.
(DEFUN FACT (LAMBDA (X)
(COND ( (ZEROP X) 1 )
( T (* X (FACT (- X 1))) )
)
))
Пример 2. Функция COPY, которая строит копию самого "верхнего" уровня списка LST:
(DEFUN COPY (LAMBDA (LST)
(COND ( (NULL LST) NIL )
( T (CONS (CAR LST) (COPY (CDR LST))))
)
))
Построенная функция COPY является рекурсивной по аргументу, т.к. рекурсивный вызов является аргументом функции CONS. Функция COND в теле функции содержит две ветви: ветвь с условием окончания и ветвь с рекурсией, с помощью которой функция проходит список, копируя и укорачивая в процессе этого список по направлению CDR или, как говорят, в ширину.
Копирование списков представляет собой одно из основных действий над списками, и поэтому соответствующая функция входит в число встроенных функций практически во всех LISP-системах.
Пример 3. Определите функцию, удаляющую из списка последний элемент.
(DEFUN DROPLAST (LAMBDA (LST)
(REVERSE (CDR (REVERSE LST)))
))
Пример 4. Функция, удаляющая из списка первое вхождение данного элемента на верхнем уровне.
(DEFUN REMOVEF (LAMBDA (X LST)
(COND ( (NULL LST) NIL )
( (EQ X (CAR LST)) (CDR LST) )
( T (CONS (CAR LST) (REMOVEF X (CDR LST))) )
)
))
Тестовый пример:
$ (REMOVEF (A B) (A B (A B) C (A B)))
(A B C (A B))
Пример 5. Функция, удаляющая из списка каждый второй его элемент.
(DEFUN EVERYSECOND (LAMBDA (L)
(COND ( (NULL L) NIL )
( (NULL (CDR L)) L )
( T (CONS (CAR L) (EVERYSECOND (CDDR L))) )
)
))
Пример 6. Определение наибольшего элемента одноуровневого числового списка LST.
(DEFUN MAXIM (LAMBDA (LST)
(COND ( (NULL LST) NIL )
( (EQ (LENGTH LST) 1) (CAR LST) )
( T (MAX2 (CAR LST) (MAXIM (CDR LST))) )
)
))
; ---------------------
(DEFUN MAX2 (LAMBDA (X Y)
(( (> X Y) X )
Y )
))
Какие исправления необходимо проделать в программе, чтобы получить наименьший элемент одноуровневого списка?
Пример 7. Функция, которая, чередуя элементы списков (A B ...) и (1 2 ...), образует новый список (A 1 B 2 ...).
(DEFUN CHEREDUJ (LAMBDA (X Y)
(COND ( (NULL X) Y )
( T (CONS (CAR X) (CHEREDUJ Y (CDR X))) )
)))
Пример 8. Подсчет количества вхождений атома X в список LST.
(DEFUN NINSERT (LAMBDA (X LST)
(COND ( (NULL LST) 0)
( (EQ X (CAR LST))
(+ 1 (NINSERT X (CDR LST)) ) )
( T (NINSERT X (CDR LST)) )
)))
Пример 9. Нахождение суммы элементов одноуровневого числового списка.
(DEFUN SUMMA (LAMBDA (LST)
(COND ( (NULL LST) 0)
( T (+ (CAR LST) (SUMMA (CDR LST))) )
)
))
Пример 10. Подсчет количества атомов в заданном списке LST, находящихся на первом уровне.
(DEFUN LENGTH_1 (LAMBDA (LST)
(COND ( (NULL LST) 0 )
( T (+ 1 (LENGTH_1 (CDR LST))) )
)
))
Отметим, что если применять эту функцию к списку списков, то элементы NIL, которые заключают каждый список, будут также учитываться!
Пример 11. Функция, которая вставляет элемент X на N-ю позицию в список LST:
(DEFUN INSERT (LAMBDA (X N LST)
(COND ( (NULL LST) (CONS X LST) )
( (EQ N 1) (CONS X LST) )
( T (CONS (CAR (LST))
(INSERT X (DIFFERENCE N 1)
(CDR LST)))
)
)
))
Пример 12. Функция, преобразующая список (A B C D ...) в список вида ((A B) (C D) ...).
(DEFUN DOUBLE (LAMBDA (L)
(COND ( (NULL L) NIL )
( (NULL (CDR L)) NIL )
( T (CONS (LIST (CAR L) (CADR L))
(DOUBLE (CDDR L))) )
)
))
Пример 13. Из двух заданных списков X и Y одинаковой длины построим новый список, структуру которого рассмотрим на примере: если X есть список (A B C), а Y - список (1 2 3), то новый список должен иметь вид (A 1 (B 2 (C 3))).
(DEFUN SASHA (LAMBDA (X Y)
(COND ( (NULL X) )
( T (LIST (CAR X) (CAR Y)
(SASHA (CDR X) (CDR Y)))
)
)
))
Пример 14. Из двух заданных списков X и Y одинаковой длины построим новый список, структуру которого рассмотрим на примере: если X есть список (A B C), а Y - список (1 2 3), то новый список должен иметь вид ((A 1) (B 2) (C 3)).
(DEFUN UNIT (LAMBDA (X Y)
(COND ( (NULL X) NIL)
( (EQ (LENGTH X) 1)
(LIST (CAR X) (CAR Y)) )
( T (LIST (LIST (CAR X) (CAR Y))
(UNIT (CDR X) (CDR Y))) )
)
))
Пример 15. Перегруппировка элементов заданного списка так, чтобы одинаковые элементы, если они есть в списке, расположились подряд.
(DEFUN COLLECT (LAMBDA (LST)
(COND ( (NULL LST) NIL )
( T (CONS (CAR LST)
(COLLECT (COND ( (MEMBER (CAR LST)
(CDR LST))
(CONS (CAR LST)
(REMOVEF
(CAR LST)
(CDR LST))))
( T (CDR LST))))) )
)
))
; --------------------------
(DEFUN REMOVEF (LAMBDA (X LST)
(COND ( (NULL LST) NIL )
( (EQ X (CAR LST)) (CDR LST) )
( T (CONS (CAR LST) (REMOVEF X (CDR LST))) )
)
))
Пример 16. Подсчет количества положительных, отрицательных и нулевых элементов числового списка LST.
(DEFUN COUNT (LAMBDA (LST) ; Подсчет количества положительных, отрицательных и ; нулевых элементов числового списка LST (LIST (SUMMA LST PLUSP) (SUMMA LST ZEROP) (SUMMA LST MINUSP)) )) ; --------------------------- % (DEFUN SUMMA (LAMBDA (LST FUNC) ; Подсчет количества элементов числового списка, ; для которых предикат FUNC истинен (COND ( (NULL LST) 0 ) ( (FUNC (CAR LST)) (+ 1 (SUMMA (CDR LST))) ) ( T (SUMMA (CDR LST)) ) ) ))
Пример 17. Возведение первого нечетного элемента числового списка в квадрат.
(DEFUN FIRST (LAMBDA (LST)
(COND ( (NULL LST) NIL)
( (ODDP (CAR LST))
(CONS (* (CAR LST) (CAR LST))
(CDR LST)) )
( T (CONS (CAR LST) (FIRST (CDR LST))) )
)
))
Пример 18. Возведение всех нечетных элементов числового списка в квадрат.
(DEFUN ALL (LAMBDA (LST)
(COND ( (NULL LST) NIL)
( (ODDP (CAR LST))
(CONS (* (CAR LST) (CAR LST))
(ALL (CDR LST))) )
( T (CONS (CAR LST) (ALL (CDR LST))) )
)
))
Пример 19. Перевод натурального числа в "римскую запись". Функция, прведенная ниже, реализует первоначальную римскую систему счисления. Такие сокращенные способы записи, как, например, IV вместо IIII вошли в употребление лишь в начале 16-го века.
(DEFUN ROM (LAMBDA (N)
(COND ( (NOT (< N 1000))
(CONS M (ROM (- N 1000))) )
( (NOT (< N 500))
(CONS D (ROM (- N 500))) )
( (NOT (< N 100))
(CONS C (ROM (- N 100))) )
( (NOT (< N 50))
(CONS L (ROM (- N 50))) )
( (NOT (< N 10))
(CONS X (ROM (- N 10))) )
( (NOT (< N 5))
(CONS V (ROM (- N 5))) )
( (NOT (< N 1))
(CONS I (ROM (- N 1))) )
)
))
Пример 20. Вычисление значения многочлена степени N по схеме Горнера с коэфициентами, хранящимися в списке COEF, в точке X.
(DEFUN GORNER (LAMBDA (COEF N X)
(COND ( (EQ N 0) (NTH 1 COEF) )
( T (+ (NTH 1 COEF)
(* X (GORNER (CDR COEF)
(- N 1)
X)
)
)
)
)
))
; ----------------------
(DEFUN NTH (LAMBDA (N LST)
; Функция возвращает N-й элемент списка LST
(COND ( (EQ N 1) (CAR LST) )
( T (NTH (- N 1) (CDR LST) ) )
)
))
На следующем шаге мы рассмотрим рекурсию по значению.
