ElpanovEvgeniy | Рекурсии, урок 4

Рекурсии, урок 4

Сегодня будем создавать свои варианты функций с префиксом VL- при помощи рекурсии. Такие функции часто встречаются в интернете. Я не присваиваю себе уникальные права первооткрывателя, но искать ссылку на первоисточник не буду! Просто я напишу эти функции с использованием своих названий переменных... Начнем с того, что, напишем функцию, работающую подобно vl-every используя пример стандартного применения из справки.

 
(vl-every (function =) '(1 2) '(1 2 3))

А вот и сама рекурсия.

 
(defun rec-every (fun lst-1 lst-2)
  (if (and lst-1 lst-1)
    (and
      (eval
        (list
          fun
          (car lst-1)
          (car lst-2)
        ) ;_  list
      ) ;_  eval
      (rec-every fun (cdr lst-1) (cdr lst-2))
    ) ;_  and
    T
  ) ;_  if
) ;_  defun

Вызывать:

 
(setq fun (function =) lst-1'(1 2) lst-2 '(1 2 3))
(rec-every fun lst-1 lst-2) ; Вернет T

(setq fun (function =) lst-1'(1 2) lst-2 '(5 6 7))
(rec-every fun lst-1 lst-2) ; Вернет NIL

(setq fun (function <) lst-1'(1 2) lst-2 '(5 6 7))
(rec-every fun lst-1 lst-2) ; Вернет T

Интересное отличие от стандартной функции — мы жестко задали количество аргументов, а встроенная функция может сравнивать любое их количество... Уточню что аргумент 'FUN — любая функция, результат которой мы будем отслеживать на отличие от NIL . Разберем, как работает рекурсия: В первой строке, как всегда, пишем проверку для выхода.

 
(and lst-1 lst-1)

Если у нас есть оба списка и они не пустые, то переходим к следующей строке

 
(and
  (eval
    (list
      fun
      (car lst-1)
      (car lst-2)
    ) ;_  list
  ) ;_  eval
  (rec-every fun (cdr lst-1) (cdr lst-2))
) ;_  and

здесь мы проверяем отличие от NIL результат двух функций, если первый результат отличен от NIL то проверяется второй. Рассмотрим их отдельно:

 
(eval
  (list
    fun
    (car lst-1)
    (car lst-2)
  ) ;_  list
) ;_  eval

EVAL — применяет функцию, сохраненную в переменной FAN к первым элементам обоих списков.

(rec-every fun (cdr lst-1) (cdr lst-2))

Вызов рекурсии с укороченными списками — без первых элементов. И наконец, второе выражение IF — всегда возвращает T Когда закончился один из списков или оба, мы возвращаем T Например, стандартная функция vl-every

 
(vl-every '= nil '(1 2 3)); возвращает T

Теперь, пошагово, рассмотрим работу рекурсии. С этого места будет удобно скопировать урок в ЛИСП-редактор...

 
  ; Сама рекурсия
  
(defun rec-every (fun lst-1 lst-2)
  (if (and lst-1 lst-1)
    (and
      (eval
        (list
          fun
          (car lst-1)
          (car lst-2)
        ) ;_  list
      ) ;_  eval
      (rec-every fun (cdr lst-1) (cdr lst-2))
    ) ;_  and
    T
  ) ;_  if
) ;_  defun

  ; Аргументы
  
(setq fun   (function =)
      lst-1 '(1 2)
      lst-2 '(1 2 3)
) ;_  setq

  ; Вызывать
  
(rec-every fun lst-1 lst-2)

;; Шаг 1.

  ; fun   = (function =)
  ; lst-1 = '(1 2)
  ; lst-2 = '(1 2 3)
  
(defun rec-every (fun lst-1 lst-2)
  (if (and lst-1 lst-1) ; Получаем T, переходим на следующую строку
    (and
      (eval
        (list
          fun
          (car lst-1) ; Получаем 1
          (car lst-2) ; Получаем 1
        ) ; (list '= 1 1)
      ) ; Вычисляем выражение (= 1 1) и получаем T
  ; Переходим к следующему выражению
      (rec-every
        fun
        (cdr lst-1) ; Получаем '(2)
        (cdr lst-2) ; Получаем '(2 3)
      ) ; самовызов, переходим на шаг 2
    ) ;_  and
    T ; не дошли
  ) ;_  if
) ;_  defun

;; Шаг 2.

  ; fun   = (function =)
  ; lst-1 = '(2)
  ; lst-2 = '(2 3)
  
(defun rec-every (fun lst-1 lst-2)
  (if (and lst-1 lst-1) ; Получаем T, переходим на следующую строку
    (and
      (eval
        (list
          fun
          (car lst-1) ; Получаем 2
          (car lst-2) ; Получаем 2
        ) ; (list '= 2 2)
      ) ; Вычисляем выражение (= 2 2) и получаем T
  ; Переходим к следующему выражению
      (rec-every
        fun
        (cdr lst-1) ; Получаем NIL
        (cdr lst-2) ; Получаем '(3)
      ) ; самовызов, переходим на шаг 3
    ) ;_  and
    T ; не дошли
  ) ;_  if
) ;_  defun

;; Шаг 3.

  ; fun   = (function =)
  ; lst-1 = NIL
  ; lst-2 = '(3)
  
(defun rec-every (fun lst-1 lst-2)
  (if (and lst-1 lst-1) ; Получаем NIL, пропускаем первое выражение и переходим ко второму
    (and ; Пропустили
      (eval
        (list
          fun
          (car lst-1)
          (car lst-2)
        ) ;_  list
      ) ;_  eval
      (rec-every
        fun
        (cdr lst-1)
        (cdr lst-2)
      ) ;_  rec-every
    ) ;_  and
    T ; Возвращаем T
  ) ;  Получаем T
) ; Возвращаем T и переходим к шагу 2 подставляя вычисленный результат

;; Шаг 2.

  ; fun   = (function =)
  ; lst-1 = '(2)
  ; lst-2 = '(2 3)
  
(defun rec-every (fun lst-1 lst-2)
  (if (and lst-1 lst-1) ; Уже вычислено = T
    (and
      (eval ; Уже вычислено = T
        (list
          fun
          (car lst-1)
          (car lst-2)
        ) ;_  list
      ) ;_  eval
      (rec-every ; Уже вычислено = T
        fun
        (cdr lst-1)
        (cdr lst-2)
      ) ;_  rec-every
    ) ; (and T T) Получаем T
    T ; не дошли
  ) ;  Получаем T
) ; возвращаем T и переходим к шагу 1

;; Шаг 1.

  ; fun   = (function =)
  ; lst-1 = '(1 2)
  ; lst-2 = '(1 2 3)
  
(defun rec-every (fun lst-1 lst-2)
  (if (and lst-1 lst-1) ; Уже вычислено = T
    (and
      (eval ; Уже вычислено = T
        (list
          fun
          (car lst-1)
          (car lst-2)
        ) ;_  list
      ) ;_  eval
      (rec-every ; Уже вычислено = T
        fun
        (cdr lst-1)
        (cdr lst-2)
      ) ;_  rec-every
    ) ; (and T T) Получаем T
    T ; не дошли
  ) ;  Получаем T
) ; возвращаем T

Великому и могучему языку посвящается...

Рекурсии, урок 4