4_рекурсия

1. Функциональное программирование

Лекция 4.
Функциональная рекурсия.

2. Рекурсивные процессы

Рекурсия – самоповторяющееся обращение.
Применение рекурсии:
Построение дерева решений
Толкование слов
1. Задать исходные данные
1. Найти определение слова в
2. Вычислить очередные
словаре
значения
2. Прочитать толкование слова
3. Назначить вычисленные
3. Выбрать неизвестные понятия
значения исходными
4. Для п.3 применить
4. Для п.3 применить
Толкование слов
Построение дерева решений

3. Структура рекурсивной функции

◼
именование функции – необходимо для
реализации самовызова
◼
терминальные ветки – необходимы для
остановки процесса вычисления (сечение)
◼
рекурсивные ветки – непосредственный
процесс работы функции

4. Правила построения рекурсии

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

5. Правила построения рекурсии

Структура рекурсивной функции
терминальн ая ветка_1
. . .
терминальн ая ветка_n
f ( x1 x2 ...x p ) = x1 x2 ...x p .
рекурсивна я ветка_1
. . .
рекурсивна я ветка_m

6. Структура рекурсивной функции

(defun <имя> <параметры>
(cond (терминальная ветка_1)
...................
(терминальная ветка_n)
(рекурсивная ветка_1)
....................
(рекурсивная ветка_m)))

7. Структура рекурсивной функции

Числовая рекурсия
◼ Вычислить факториал числа n
1. n=0 f=1
2. f(n)=n*f(n-1)
1, если n = 0
f (n) = n.
n * f (n − 1) в остальных случаях
(defun f(n)
(cond ((= n 0) 1)
(t (* n (f (- n 1))))
)
)

8. Числовая рекурсия

Трассировка функции
Вызов (f 3)
шаг 1: n=3 рекурсивная ветка
=3*2=6
(* 3 (f (- 3 1)))= 3* f(2)
шаг 2: n=2 рекурсивная ветка
=2*1=2
(* 2 (f (- 2 1)))= 2* f(1)
шаг 3: n=1 рекурсивная ветка
(* 1 (f (- 1 1)))= 1* f(0)
=1*1=1
шаг 4: n=0 терминальная ветка – f=1

9. Трассировка функции

Рекурсия списка
◼
Найти произведение элементов числового списка
(defun f (lis)
(cond ((null lis) 1)
(t (*
(car lis)
(f (cdr lis))
)
)
)
)

10. Рекурсия списка

Рекурсия списка:
две рекурсивные ветки
◼
Найти произведение числовых элементов
списка
(defun f (lis)
(cond ((null lis) 1)
((numberp (car lis)) (* (car lis) (f (cdr lis))))
(t (f (cdr lis)))
)
)

11. Рекурсия списка: две рекурсивные ветки

Рекурсия списка:
две терминальные ветки
Найти первый числовой элемент списка. Если
такого нет, то вернуть nil.
(defun f (lis)
(cond ((null lis) nil)
((numberp (car lis)) (car lis))
(t (f (cdr lis)))
)
)
◼

12. Рекурсия списка: две терминальные ветки

Виды рекурсии
◼ Простая рекурсия
◼ Параллельная рекурсия
◼ Взаимная рекурсия
◼ Рекурсия высших порядков

13. Виды рекурсии

Простая рекурсия
◼ Соединить два списка в один
(defun append (l1 l2)
(cond ((null l1) l2)
((null l2) l1)
(t (cons (car l1) (append (cdr l1) l2)))
)
)

14. Простая рекурсия

Параллельная рекурсия
◼ Перевернуть список вместе с подсписками
(defun rev(lis)
(cond ((atom lis) lis)
((null (cdr lis)) (cons (rev (car lis)) nil))
(t (append (rev (cdr lis))
(rev (cons (car lis) nil))))
)
)

15. Параллельная рекурсия

Взаимная рекурсия
◼ Перевернуть список вместе с подсписками
(defun rev (lis)
(cond ((atom lis) lis)
(t (conv lis nil))))
(defun conv (lis res)
(cond ((null lis) res)
(t (conv (cdr lis) (cons (rev (car lis)) res)))))

16. Взаимная рекурсия

Рекурсия первого порядка
◼ Превратить составной список в простой
(defun simp (lis) (f lis nil))
(defun f (lis res)
(cond ((null lis) res)
((atom lis) (cons lis res))
(t (f (car lis) (f (cdr lis) res))))
)

17. Рекурсия первого порядка

Рекурсия второго порядка
◼ Перевернуть список, используя только
базисные функции
(defun rvs (lis)
(cond ((null lis) lis)
((null (cdr lis)) lis)
(t (cons (car (rvs (cdr lis)))
(rvs (cons (car lis)
(rvs (cdr (rvs (cdr lis)))))))))