Lisp Часть 2 Языковые конструкции и примеры.

Вопросы, касающиеся некоторых приёмов программирования на Lisp и примеры кода.

Как в Lisp'е работать с массивами?

Тема была достаточно подробно рассмотрена на форуме в теме Lisp и массивы

Что такое хвостовая рекурсия?

Хвостовая рекурсия (концевая рекурсия, tail recursion, tail-end recursion) - специальная форма рекурсии для которой на каждом шаге достаточно запоминать лишь текущие значения состояния рекурсивного процесса, а не всю цепочку отложенных состояний. Использование хвостовой рекурсии компилятором превращает рекурсию в итерационный процесс, сокращает расход памяти, которая не тратится на запоминание всех состояний рекурсивного алгоритма и увеличивает скорость работы.

Подробнее про хвостовую рекурсию можно прочесть в wikipedia Tail recursion

Язык Scheme всегда с самого своего возникновения поддерживает хвостовую рекурсию. Её поддержка требуется стандартами языка. В тоже время, стандарт Common Lisp не содержит требования поддерживать хвостовую рекурсию, тем не менее, многие компиляторы Lisp её поддерживают. Например, SBCL - её поддерживает, а CLISP - нет.

Пример хвостовой рекурсии на языке Common Lisp

;;; вычисление факториала


(defun factorial (x)
  (labels ((factorial-rec (number acc)
	     (if (zerop number)
		 acc
		 (factorial-rec (- number 1) (* acc number)))))
    (factorial-rec x 1)))

(print (factorial 100000))
(quit)