Задать рекурсивную функцию обращения элементов списка - Lisp

Формулировка задачи:

Задать рекурсивную функцию обращения элементов списка (не используя встроенную функцию reverse). Оценить сложность реализации. Можно ли реализовать обращение списка за линейное время?

Решение задачи: «Задать рекурсивную функцию обращения элементов списка»

Листинг программы

(defun rev (lst &optional (r nil))
  (if lst (rev (cdr lst) (cons (car lst) r)) r))
 
==> REV
 
(rev '(1 2 3 4 5))
 
==> (5 4 3 2 1)

Объяснение кода листинга программы

В коде определена рекурсивная функция rev с двумя аргументами: lst и опциональным r. Если lst не равно nil, то вызывается рекурсивный вызов функции rev с аргументами cdr lst и cons (car lst) r. Если lst равно nil, то в качестве результата возвращается r. При вызове функции rev с аргументом '(1 2 3 4 5)' будет выполнено следующее:

rev вызывает себя рекурсивно с аргументами cdr lst и cons (car lst) r.
cdr lst равен nil, поэтому рекурсивный вызов прекращается и в качестве результата возвращается r, который равен nil.
cons (car lst) r возвращает '(5 4 3 2 1). Таким образом, результатом выполнения кода будет `'(5 4 3 2 1)'.