Вопрос 18) простая рекурсия. (Lisp)

    Будем говорить, что рекурсия простая, если вызов функции встречается в некоторой ветви программы лишь один раз. Простой рекурсии в императивном программировании соответствует обыкновенный цикл.

    Если в качестве результата функция возвращает значение другой функции, и рекурсивный вызов участвует в вычислении аргументов этой функции, то будем говорить о присутствии в функции рекурсии по аргументам.

   

Пример 1. Вычисление факториала натурального числа X. Поставленная задача решается с помощью функции, которая принимает значение, равное единице при равенстве аргумента нулю, а во всех остальных случаях равна произведению аргумента на значение этой же функции от аргумента, уменьшенного на единицу.

(DEFUN FACT (LAMBDA (X)

(COND ( (ZEROP X) 1 )

( T (* X (FACT (- X 1))) )

)

))

Текст этой функции можно взять здесь.

   

Пример 2. Функция COPY, которая строит копию самого "верхнего" уровня списка LST:

(DEFUN COPY (LAMBDA (LST)

(COND ( (NULL LST) NIL )

( T (CONS (CAR LST) (COPY (CDR LST))))

)

))

Текст этой функции можно взять здесь.

    Построенная функция COPY является рекурсивной по аргументу, т.к. рекурсивный вызов является аргументом функции CONS. Функция COND в теле функции содержит две ветви: ветвь с условием окончания и ветвь с рекурсией, с помощью которой функция проходит список, копируя и укорачивая в процессе этого список по направлению CDR или, как говорят, в ширину.

    Копирование списков представляет собой одно из основных действий над списками, и поэтому соответствующая функция входит в число встроенных функций практически во всех LISP-системах.    

Пример 3. Определите функцию, удаляющую из списка последний элемент.

(DEFUN DROPLAST (LAMBDA (LST)

(REVERSE (CDR (REVERSE LST)))

))

Текст этой функции можно взять здесь.