1. Проверка на вхождения атома в список

>(defun checkA (at lst) (cond ((null lst) nil) ((eql at (car lst)) T) (T (checkA at (cdr lst))) )) CHECKA >(checkA 'A '(b c)) NIL >(checkA 'A '(a b c)) T

2. Удаление из списка n-ного элемента

>(defun delAt (pos lst) (cond ((null lst) nil) ((eql pos 0) (cdr lst)) (T (cons (car lst) (delat (- pos 1) (cdr lst)))) ) ) DELAT >(delAt 2 '(a b c d)) (A B D) >(delAt 5 '(a b c d)) (A B C D)

3. Добавление в список элемента в позицию n

>(defun insAt (pos lst at) (cond ((null lst) (cons at nil)) ((eql pos 0) (cons at lst)) (T (cons (car lst) (insAt (- pos 1) (cdr lst) at))) ) ) INSAT >(insat 3 '(a b c d e) 'f) (A B C F D E) >(insat 30 '(a b c d e) 'f) (A B C D E F)

В приведённых примерах рассматривалась рекурсия как таковая, однако в Lisp различают несколько вариантов рекурсии. Рассмотрим их подробнее.

• Параллельная рекурсия. Такая рекурсия возникает, когда в теле некоторой функции f1 содержится вызов функции f2, в качестве аргументов которой используется вызов функции f1.

• Взаимная рекурсия. Возникает при вызове в теле функции f1 функции f2, в теле которой, в свою очередь, существует вызов функции f1.

• Вложенная рекурсия - возникает, когда функция в своём теле вызывает саму себя, используя себя же в качестве параметра этого вызова.

Очевидно, что функции INSAT, DELAT и CHECKA, рассмотренные выше, имеют параллельную рекурсивную схему. В качестве ещё одного примера параллельной рекурсии приведём следующий код, осуществляющий инверсию списка любой глубины вложенности:

>(defun ReversePlus (List) (cond ((atom List) List) ((null (cdr List)) (cons (ReversePlus (car List)) nil)) (T (append (ReversePlus (cdr List)) (ReversePlus (cons (car List) nil)))))) REVERSEPLUS >(ReversePlus '(1 (2 3) (4 (5 6)) 7)) (7 ((6 5) 4) (3 2) 1)

Тем самым, мы видим, что функция развернула списки в обратном порядке на всех своих уровнях. То же самое можно выполнить с помощью взаимной рекурсии:

>(defun ReversePlus (List) (cond ((atom List) List) (T (Change List nil)) ) ) REVERSEPLUS >(defun Change (List Result) (cond ((null List) Result) (T (change (cdr List) (cons (ReversePlus (car List)) Result))) ) ) CHANGE >(ReversePlus '(1 (2 3) (4 (5 6)) 7)) (7 ((6 5) 4) (3 2) 1)

Вложенная рекурсия является достаточно редкой. Обычно этот вид рекурсии иллюстрируется с помощью специализированных математических функций, таких как функции Аккермана (Вирт, 1986). Такая функция определяется следующим образом:

A(0,n)=n+1;

A(m,0)=A(m-1,1); (m>0)

A(m,n)=A(m-1,A(m,n-1)); (m,n>0)

Очевидно, что функция Lisp, вычисляющая функцию Аккермана, будет построена в соответствии с определением:

> (defun akk (m n) (cond ((eql m 0) (+ 1 n)) ((eql n 0) (akk (- m 1) 1)) (T (akk (- m 1) (akk m (- n 1)))))) AKK >(akk 2 2) 7

Автор рекомендует выполнить вызов (akk 2 2) после вызова (trace akk) и рассмотреть дерево функций, имеющее достаточно любопытный вид.