Новая версия сайта, доступна здесь.
Рекурсии, урок 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)