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

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




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

Рассмотрим функцию, работающую подобно vl-remove ее назначение смотрите в справке. Привожу пример стандартного применения:

 
(vl-remove 10 '(5 10 15 20))
;Возвращает:
;'(5 15 20)
 

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

 
(defun rec-remove (el lst)
  (cond
    ((not lst)
     nil
    )
    ((= el (car lst))
     (rec-remove el (cdr lst))
    )
    (T
     (cons (car lst)
           (rec-remove el (cdr lst))
     ) ;_  cons
    ) ;_  T
  ) ;_  cond
) ;_  defun
;Вызывать:
(setq el 10
      lst '(5 10 15 20)
) ;_  setq
(rec-remove el lst)
; Вернет '(5 15 20)
 

Пусть не смущает то, что есть два места в рекурсии, из которых, она может вызвать сама себя. А теперь разберем, как работает рекурсия: В первой строке, как всегда, пишем проверку для выхода.

 
((not lst) nil)
 

Здесь мы проверяем переменную LST на наличие данных и если результат отличен от NIL переходим на вторую строку. Во второй строке мы проверяем равенство удаляемого элемента и первого элемента в списке LST

 
(= el (car lst))
 

Если EL равен первому элементу в LST переходим на третью строку, иначе на пятую (четвертая — закрывающая скобка). В третьей строке

 
(rec-remove el (cdr lst))
 

мы вызываем рекурсию, с укороченным списком — без первого элемента, т.е. если удаляемый элемент равен первому элементу в списке, то продолжаем программу, просто его пропустив. В пятой строке, вместо проверки, у нас стоит T — это значит, что если программа дошла до проверки, то она всегда верна. Другими словами, если у нас есть непустой список и его первый элемент не равен удаляемому, то переходим на шестую строку. В шестой мы добавляем к списку полученному в результате вычислений в седьмой строке первый элемент списка LST

 
(cons (car lst)
 

В седьмой строке самовызов функции без первого элемента

 
(rec-remove el (cdr lst))
 

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

 
  ; Сама рекурсия
(defun rec-remove (el lst)
  (cond
    ((not lst)
     nil
    )
    ((= el (car lst))
     (rec-remove el (cdr lst))
    )
    (T
     (cons (car lst)
           (rec-remove el (cdr lst))
     ) ;_  cons
    ) ;_  T
  ) ;_  cond
) ;_  defun

  ; Аргументы
(setq el 10
      lst '(5 10 15 20)
) ;_  setq

  ; Вызывать
(rec-remove el lst)


;; Шаг 1.
  ;el = 10
  ;lst = '(5 10 15 20)

(defun rec-remove (el lst)
  (cond
    ((not lst) ; Получаем Nil переходим на следующую проверку
     nil ; Пропускаем
    )
    ((= el (car lst)) ; (= 10 5) Получаем Nil переходим на следующую проверку
     (rec-remove el (cdr lst)) ; Пропускаем
    )
    (T
     (cons
       (car lst) ; Получаем 5
       (rec-remove
         el
         (cdr lst) ; Получаем '(10 15 20)
       ) ; Переходим на шаг 2 для вычислений
     ) ;_  cons
    ) ;_  T
  ) ;_  cond
) ;_  defun



;; Шаг 2.
  ;el = 10
  ;lst = '(10 15 20)

(defun rec-remove (el lst)
  (cond
    ((not lst) ; Получаем Nil переходим на следующую проверку
     nil ; Пропускаем
    )
    ((= el (car lst)) ; (= 10 10) Получаем  T переходим на следующую строку
     (rec-remove
       el
       (cdr lst) ; Получаем '(15 20)
     ) ;Переходим на шаг 3 для вычислений
    )
    (T ; не дошли
     (cons
       (car lst) ; не дошли
       (rec-remove
         el
         (cdr lst) ; не дошли
       ) ; не дошли
     ) ;_  cons
    ) ;_  T
  ) ;_  cond
) ;_  defun



;; Шаг 3.
  ;el = 10
  ;lst = '(15 20)
(defun rec-remove (el lst)
  (cond
    ((not lst) ; Получаем Nil переходим на следующую проверку
     nil ; Пропускаем
    )
    ((= el (car lst)) ; (= 10 15) Получаем Nil переходим на следующую проверку
     (rec-remove ; Пропускаем
       el
       (cdr lst) ; Пропускаем
     ) ; Пропускаем
    )
    (T
     (cons
       (car lst) ; Получаем 15
       (rec-remove
         el
         (cdr lst) ; Получаем '(20)
       ) ; Переходим на шаг 4 для вычислений
     ) ;_  cons
    ) ;_  T
  ) ;_  cond
) ;_  defun



;; Шаг 4.
  ;el = 10
  ;lst = '(20)
(defun rec-remove (el lst)
  (cond
    ((not lst) ; Получаем Nil переходим на следующую проверку
     nil ; Пропускаем
    )
    ((= el (car lst)) ; (= 10 20) Получаем NIL переходим на следующую проверку
     (rec-remove ; Пропускаем
       el
       (cdr lst) ; Пропускаем
     ) ;  Пропускаем
    )
    (T
     (cons
       (car lst) ; Получаем 20
       (rec-remove
         el
         (cdr lst) ; Получаем NIL
       ) ; Переходим на шаг 5 для вычислений
     ) ;_  cons
    ) ;_  T
  ) ;_  cond
) ;_  defun



;; Шаг 5.
  ;el = 10
  ;lst = NIL
(defun rec-remove (el lst)
  (cond
    ((not lst) ; Получаем T переходим на следующую строку
     nil
    ) ; Возвращаем NIL
    ((= el (car lst)) ; не дошли
     (rec-remove ; не дошли
       el
       (cdr lst) ; не дошли
     ) ; не дошли
    )
    (T ; не дошли
     (cons
       (car lst) ; не дошли
       (rec-remove
         el
         (cdr lst) ; не дошли
       ) ; не дошли
     ) ; не дошли
    ) ; не дошли
  ) ; Возвращаем NIL
) ; Возвращаем NIL переходим на шаг 4



;; Шаг 4.
  ;el = 10
  ;lst = '(20)
(defun rec-remove (el lst)
  (cond
    ((not lst) ; Пропускаем — уже вычислено
     nil
    )
    ((= el (car lst)) ; Пропускаем — уже вычислено
     (rec-remove
       el
       (cdr lst)
     ) ;_  rec-remove
    )
    (T
     (cons
       (car lst) ; Уже вычислено 20
       (rec-remove ; Уже вычислено NIL
         el
         (cdr lst)
       ) ; Уже вычисленно NIL
     ) ; (cons 20 nil) Получаем '(20)
    ) ; Возвращаем '(20)
  ) ; Возвращаем '(20)
) ; Возвращаем '(20) и переходим на шаг 3



;; Шаг 3.
  ;el = 10
  ;lst = '(15 20)
(defun rec-remove (el lst)
  (cond
    ((not lst) ; Пропускаем — уже вычислено
     nil
    )
    ((= el (car lst)) ; Пропускаем — уже вычислено
     (rec-remove
       el
       (cdr lst)
     ) ;_  rec-remove
    )
    (T
     (cons
       (car lst) ; Уже вычислено 15
       (rec-remove ; Уже вычислено '(20)
         el
         (cdr lst)
       ) ; Уже вычислено '(20)
     ) ; (cons 15 '(20)) Получаем '(15 20)
    ) ; Возвращаем '(15 20)
  ) ; Возвращаем '(15 20)
) ; Возвращаем '(15 20) и переходим на шаг 2



;; Шаг 2.
  ;el = 10
  ;lst = '(10 15 20)
(defun rec-remove (el lst)
  (cond
    ((not lst) ; Пропускаем — уже вычислено
     nil
    )
    ((= el (car lst)) ; переходим на следующую строку — уже вычислено
     (rec-remove ; Уже вычислено '(15 20)
       el
       (cdr lst)
     ) ; Уже вычислено '(15 20)
    ) ; Возвращаем '(15 20)
    (T ; не дошли
     (cons
       (car lst)
       (rec-remove
         el
         (cdr lst)
       ) ;_  rec-remove
     ) ;_  cons
    ) ; не дошли
  ) ; Возвращаем '(15 20)
) ; Возвращаем '(15 20) и переходим на шаг 1



;; Шаг 1.
  ;el = 10
  ;lst = '(5 10 15 20)
(defun rec-remove (el lst)
  (cond
    ((not lst) ; Пропускаем — уже вычислено
     nil
    )
    ((= el (car lst)) ; Пропускаем — уже вычислено
     (rec-remove
       el
       (cdr lst)
     ) ;_  rec-remove
    )
    (T
     (cons
       (car lst) ; Уже вычислено 5
       (rec-remove ; Уже вычислено '(15 20)
         el
         (cdr lst)
       ) ; Уже вычислено '(15 20)
     ) ; (cons 5 '(15 20)) Получаем '(5 15 20)
    ) ; Возвращаем '(5 15 20)
  ) ; Возвращаем '(5 15 20)
) ; Возвращаем '(5 15 20)