Notice: Undefined index: moes_p in /home/elpanov/elpanov.com/docs/index.php(3) : eval()'d code on line 1
ElpanovEvgeniy | Рекурсии, урок 8

Новая версия сайта, доступна здесь.




Рекурсии, урок 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)