Рекурсии в AutoLISP урок 8
Закончить рассмотрение встроенных функций с префиксом vl- и написание их аналогов, хочу функцией vl-sort . Я написал несколько вариантов этой функции, при помощи рекурсий, используя различные алгоритмы. На нескольких уроках, мы их рассмотрим. Реализация vl-sort — с помощью рекурсии, гораздо сложнее функций, рассмотренных, на предыдущих занятиях. Если вам не до конца понятны предыдущие уроки, рекомендую рассмотреть их еще раз. Сразу хочу оговориться — эти варианты работают медленнее, чем встроенная функция, но моя задача научить создавать рекурсии, а не написать библиотеку функций. Для начала, рассмотрим самый простой алгоритм. Его название "Сортировка методом выбора" или "Selection sort". Это самый медленный из рассматриваемых алгоритмов.
(defun rec-min (lst mi f) ; Вычисляем минимальное ; значение списка, применяя тестовую функцию ;(rec-min (cdr lst) (car lst) f) (cond ((not lst) mi) (((eval f) (car lst) mi) (rec-min (cdr lst) (car lst) f) ) (t (rec-min (cdr lst) mi f)) ) ;_ cond ) ;_ defun (defun rec-remove-singl (i lst) ; Удаляем первое вхождение элемента из списка ;(rec-remove-singl (cadr lst) lst) (if lst (if (equal i (car lst)) (cdr lst) (cons (car lst) (rec-remove-singl i (cdr lst))) ) ;_ if ) ;_ if ) ;_ defun (defun rec-sort-min (lst f) ;(rec-sort-min lst) (if lst ((lambda (x) (cons x (rec-sort-min (rec-remove-singl x lst ) ;_ заканчиваем удаление f ) ;_ заканчиваем рекурсию для дочерней рекурсии с укороченным списком ) ; ) ;_ lambda (rec-min (cdr lst) (car lst) f) ) ) ;_ if ) ;_ defun ; Проверим: (setq lst '(7 3 4 6 9 6 7 2 5 3 2 3 6 4 6 3 1) f (function <) ) ;_ setq (rec-sort-min lst f) ; Возвращает ; '(1 2 2 3 3 3 3 4 4 5 6 6 6 6 7 7 9)
У нас есть список и функция сравнения, по результату которой, либо T либо NIL
Например:
список '(1 3 2)
функция '<
Мы можем просмотреть весь список и выбрать наименьшее значение. Именно то, которое будет давать T с любым элементом списка. Потом ставим его в начало результирующего списка, удаляем первое вхождение найденного значения в изучаемом списке и к укороченному списку, рекурсивно, применяем функцию еще раз... И так, до окончания списка. На нашем примере, результат должен выглядеть следующим образом:
(cons 1(cons 2(cons 3 nil))); => '(1 2 3)
Из описания алгоритма понятно, что нам понадобится три программы.
Первая должна искать в списке минимальное значение.
Вторая — удалять первое вхождение, найденного элемента, из списка.
Третья — запускать в нужной последовательности, первые две
и формировать конечный список...
Функция поиска минимального значения:
На входе мы имеем тестовое значение, список и функцию. Если применяя функцию к первому элементу списка и тестовому значению мы получаем T — значит, первое значение списка ближе к искомому значению и мы перезапускаем функцию с укороченным списком, а бывший, первый элемент, ставим вместо тестового значения. Иначе, перезапускаем функцию с укороченным списком, но с тем же тестовым значением.
Вот и рекурсия, для поиска минимального значения:
(defun rec-min (lst mi f) (cond ((not lst) ; Если кончился список mi ; Возвращаем найденное минимальное значение ) (((eval f) ; Активируем функцию (car lst) ; Первый элемент списка mi ; Текущее минимальное значение ) ; Если Т переходим на следующую строку и меняем минимальное значение (rec-min ; Самовызов рекурсии (cdr lst) ; Укороченный список (car lst) ; Новое минимальное значение f ; Тестовая функция ) ; rec-min ) (t ; Если дошли, всегда правда (rec-min ; Самовызов рекурсии (cdr lst) ; Укороченный список mi ; Старое минимальное значение f ; Тестовая функция ) ;_ rec-min ) ;_ t ) ;_ cond ) ;_ defun ; Проверим: (setq lst '(7 3 4 6 9 6 7 2 5 3 2 3 6 4 6 3 1) f (function <) ) ;_ setq (rec-min (cdr lst) (car lst) f) ; Возвращает ; 1
В проверке специально запускаю функцию с укороченным списком, указывая тестовым значением первый элемент. Именно так она и будет работать. Функция удаления первого вхождения элемента в списке. Кстати, во многих случаях, она будет работать быстрее, чем vl-remove — ей не нужно просматривать весь список! На входе мы имеем удаляемый элемент и список. Ничего необычного в этой функции нет, надеюсь, что вы уже сами можете написать подобную. В первой проверке, как всегда, список. Если он не закончился, проверяем равенство тестового элемента и первого элемента списка. Если не равно, добавляем первый элемент к результату рекурсии без первого элемента, иначе возвращаем список без первого элемента.
(defun rec-remove-singl (i lst) (if lst ; Если не кончился список (if (equal i (car lst)) ; Сравниваем тестовое значение и первый элемент списка (cdr lst) ; Укороченный список (cons ; Формируем список (car lst) ; Первый элемент списка (rec-remove-singl ; Самовызов рекурсии i ; Тестовое значение (cdr lst) ; Укороченный список ) ;_ rec-remove-singl ) ;_ cons ) ;_ if ) ;_ if ) ;_ defun ; Проверка: (setq lst '(7 3 4 6 9) i 4 f (function <) ) ;_ setq (rec-remove-singl i lst) ; Возвращает ; '(7 3 6 9)
Хотелось бы добавить, проверка на наличие списка не обязательна, но я добавил ее, на тот случай, что эту функцию будут копировать в свои программы, забыв добавить такую проверку. Функция формирования отсортированного списка из минимальных значений, в порядке их нахождения, с одновременным удалением найденных значений из сортируемого списка. На входе мы имеем список и тестовую функцию. В этой программе, всего одна проверка на окончание списка. Чтобы не плодить лишние переменные берем пользовательскую функцию lambda. Т.е. первым делом, после загрузки lambda выражения вычисляется строка:
(rec-min (cdr lst) (car lst) f)
Ищется минимальное значение в списке. Потом, найденное значение, передается как аргумент, в функцию lambda где удаляется первое вхождение этого значения из списка и происходит самовызов рекурсии с добавлением найденного значения к результату.
(defun rec-sort-min (lst f) (if lst ; Если не кончился список ((lambda (x) ;; Пользовательская функция ;; С аргументом — вычисленное минимальное значение списка (cons ; Формируем список x ; Минимальное значение списка (rec-sort-min ; Самовызов рекурсии (rec-remove-singl ; Удаление первого вхождения элемента в списке x ; Минимальное значение списка lst ; Список ) ;_ заканчиваем удаление f ; Тестовая функция ) ;_ заканчиваем рекурсию для дочерней рекурсии с укороченным списком ) ;_ cons ) ;_ lambda (rec-min (cdr lst) (car lst) f) ; Поиск минимального значения ) ) ;_ if ) ;_ defun ; Проверим: (setq lst '(7 3 4 6 9 6 7 2 5 3 2 3 6 4 6 3 1) f (function <) ) ;_ setq (rec-sort-min lst f) ; Возвращает ; '(1 2 2 3 3 3 3 4 4 5 6 6 6 6 7 7 9)
Старая версия сайта, доступна здесь.