Рекурсия
ЛЕКЦИЯ 6.
РЕКУРСИЯ.
6. Р Е К У Р С И Я
Функция является рекурсивной, если в ее определении содержится вызов самой этой функции.
 |
Рекурсия основной и самый эффективный способ организации повторяющихся вычислений в функциональном программировании и в лиспе.
ПРИМЕР.
Определим функцию MEMBER
 |
(defun MEMBER (item list) (cond ((null list) nil) ((eql (car list) item) list) (t (MEMBER item (cdr list))))) |
6.1 Численная рекурсия
Предположим, что необходимо написать функцию sumall, которая имеет один аргумент, целое положительное число и возвращает сумму всех целых чисел между нулем и этим числом.
Например (sumall 9) должно вернуть 45
Это можно решить циклически; мы решим рекурсивно.
Отметим два факта:
1. Если n=0, сумма чисел между 0 и n равна 0.
2. Если n>0, сумма чисел между 0 и n
равна n плюс сумма чисел между 0 и n-1.
 |
Эти два факта переводятся непосредственно в определение функции:
| |
(defun sumall (n) (cond ((zerop n) 0) (t (+ n (sumall (- n 1)))))) |
Производится проверка n : равно нулю или нет.
Если значение n=0, то функция возвращает 0 .
В противном случае , функция вызывает сама себя для вычисления суммы чисел между 0 и n-1 и и добавляет n к этой сумме.
6.2 Как работает рекурсивная функция.
Посмотрим как работает рекурсивная функция. Проследим за несколькими вызовами.
Как работает (sumall 0) все ясно. Функция возвращает 0.
Эта ветвь в cond называется терминальной (terminating) завершающей, так как функция дает значение без рекурсивного вызова.
Если (sumall 1), то идет расчет по второй ветке,
которая называется рекурсивной, так как идет вызов самой себя.
В этом случае (+ 1 (sumall 0) и значение 1.
Если (sumall 2) , то по рекурсивной ветке (+ 2 (sumall 1)) и возвращает 3.
Если посмотреть,
(sumall 3) вызывает (sumall 2)
(sumall 1) вызывает (sumall 0).
После того как (sumall 0) вернет 0,
(sumall 1) вернет 1,
(sumall 2) вернет 3,
(sumall 3) это вызов верхнего уровня даст значение 6.
6.2.1 Трасса.
 |
6.2.2 Правила записи рекурсивной функции.
Этот простой случай иллюстрирует несколько
правил в записи рекурсивной функции.
| 1. Терминальная ветвь необходима для окончания вызова. Без терминальной ветви рекурсивный вызов был бы бесконечным. Терминальная ветвь возвращает результат, который является базой для вычисления результатов рекурсивных вызовов. |  |
| 2. После каждого вызова функцией самой себя, мы должны приближаться к терминальной ветви. В нашем случае вызовы уменьшали n и и была гарантия, что на некотором шаге будет вызов (sumall 0). Всегда должна быть уверенность, что рекурсивные вызовы ведут к терминальной ветви. |  |
Таким образом мы должны уметь писать рекурсивные функции, без того чтобы представлять точно порядок вычисления.
Как писать рекурсивные функции.
При написании рекурсивных функций мы должны планировать терминальные и рекурсивные ветви.
Таблица. Рекурсивная функция SUMALL
Шаг 1. Завершение (Терминальная ветвь)
n=0 - аргумент
(sumall 0) = 0 - значение
Шаг 2. Рекурсивная ветвь
Рекурсивные отношения между (sumall n) и (sumall(- n 1 )
2а. Примеры рекурсии
| (sumall n) | (sumall(- n 1) |
| (sumall 5)=15 | (sumall 4)=10 |
| (sumall 1)=1 | (sumall 0)=0 |
(sumall n) может быть получена из (sumall (- n 1)
прибавлением N
1. Планирование терминальной ветви.
При написании рекурсивной функции мы должны решить, когда функция может вернуть значение без рекурсивного вызова.
2. Планирование рекурсивной ветви.
В этом случае мы вызываем функцию рекурсивно с упрощенным аргументом и используем результат для расчета значения при текущем аргументе.
Таким образом мы должны решить:
1. Как упрощать аргумент, приближая его шаг за шагом к конечному значению.
2. Кроме этого необходимо построить форму, называемую рекурсивным отношением, которая связывает правильное значение текущего вызова со значением рекурсивного вызова.
В нашем случае это (sumall n) и (sumall (- n 1)).
Иногда просто найти это отношение, а если не получается надо выполнить следующую последовательность шагов.
a. Определить значение некоторого простого вызова функции и ее соответствующего рекурсивного вызова.
b. Определить соотношение между парой этих функций.
Пример. Определим функцию power. Она берет два численных аргумента m и n вычисляет значение m в степени n.
(power 2 3) возвращает 8
Вначале составим рекурсивную таблицу.
Шаг 1. Завершение (Терминальная ветвь)
n=0 - аргумент
(power 2 0) = 1 - значение
Шаг 2. Рекурсивная ветвь
Рекурсивные отношения между
(power m n) и (power m (- n 1 ))
2а. Примеры рекурсии
(power 5 3) =125 (power 5 2) = 25
(power 3 1)=3 (power 3 0 )=1
2b. Характеристическое рекурсивное отношение
(power m n) может быть получена из (power m (- n 1)
умножением на m
| |
(defun power (m n) (cond ((zerop n) 1) (t (* m (power m (- n 1)))))) |
6.4 CDR рекурсия.
Рассмотрена рекурсивная обработка чисел. Когда информация представлена в виде списка, то появляется необходимость рекурсивной обработки списков. Основная рекурсия над списками CDR рекурсия.
Пример. Написать функцию list-sum
которая берет один аргумент, список чисел, и возвращает сумму этих чисел.
Последовательно упрощающимся аргументом в этом случае будет список. Упрощение списка (cdr lis). Последнее значение аргумента nil.
Составим рекурсивную таблицу для (list-sum lis)
(list-sum nil) = 0 - значение
Шаг 2. Рекурсивная ветвь
Рекурсивные отношения между
(list-sum lis) и (list-sum (cdr lis))
2а. Примеры рекурсии
(list-sum '(2 5 3)) =10 (list-sum '(5 3)) = 8
(list-sum '(3)) =3 (list-sum nil )=0
2b. Характеристическое рекурсивное отношение (list-sum lis) может быть получена из
(list-sum (cdr lis))
сложением с (car lis).
Текст функции.
| |
(defun list-sum (lis ) (cond ((null lis) 0) (t (+ (car lis) (list-sum (cdr lis)))))) |
/p>
6.4.1 Вычисление (list-sum '(2 5 3)).
 |
6.5 Несколько терминальных ветвей.
Мы рассмотрели случай рекурсии с одной терминальной и одной рекурсивной ветвью.
Однако в определении рекурсивной функции может быть несколько терминальных ветвей.
Две терминальные ветви будут в том случае, когда ведется поиск цели в последовательности значений и мы желаем получить результат, как только цель найдена.
Ветвь 1. Цель найдена и надо вернуть ответ
Ветвь 2. Цель не найдена и нет больше элементов.
 |
Она имеет два аргумента : список чисел и заданное число. Функция возвращает первое число в списке превышающее заданное. Если этого числа нет - возвращается заданное число.
Программа.
| |
(defun greaternum (lis num) (cond ((null lis) num) ((> (car lis) num) (car lis)) (t (greaternum (cdr lis) num)))) |
6.6 Несколько рекурсивных ветвей.
Несколько рекурсивных ветвей может понадобиться, если функция обрабатывает все элементы в структуре, но использует некоторые элементы отлично от других.
В этом случае составляются два рекурсионных отношения.
Пример. Напишите функцию negnums, которая получает список чисел и возвращает список, который содержит только отрицательные числа (0 положителен).
(negnums '(-1 5 -6 0 2)) возвращает (-1 -2)
Шаг 1. Завершение (Терминальная ветвь)
(negnums nil) = nil
Шаг 2. Рекурсивная ветвь
Рекурсивные отношения между (negnums l) и
(negnums (cdr l))
1. (car l ) < 0
2а. Примеры рекурсии
(negnums '(-5 3)) =(-5)
(negnums '(3)) = nil
(negnums '(-5 3 -6 0 )) =(-5 -6)
(negnums '( 3 -6 0 )) =(-6)
2b. Характеристическое рекурсивное отношение (negnums l) может быть получена из (negnums (cdr l))
(cons (car l) (negnums (cdr l))
2. (car l ) >= 0
2а. Примеры рекурсии
(negnums '(1 -5 3 -6 0 )) =(-5 -6)
(trace negnums) '(- 5 3 -6 0 )) = (-5 -6)
2b. Характеристическое рекурсивное отношение (negnums l) может быть получена из (negnums (cdr l))
(negnums l) = (negnums (cdr l)
Программа
| |
(defun negnums (l) (cond ((null l) nil) ((< (car l) 0) (cons (car l) (negnums (cdr l)))) (t (negnums (cdr l))))) |
6.7 Общая форма.
Общая форма определения рекурсионной функции
(defun <имя> <параметры>
(cond (терминальная ветвь1)
(терминальная ветвь2)
...................
(терминальная ветвьn)
(рекурсивная ветвь1)
(рекурсивная ветвь2)
....................
(рекурсивная ветвьn)))
