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




Рекурсия - часть 4


/p>


6.4.1 Вычисление (list-sum '(2 5 3)).


6.5 Несколько терминальных ветвей.

Мы рассмотрели случай рекурсии с одной терминальной и одной рекурсивной ветвью.

Однако в определении рекурсивной функции может быть несколько терминальных ветвей.

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

Ветвь 1. Цель найдена и надо вернуть ответ

Ветвь 2. Цель не найдена и нет больше элементов.

Пример. Написать функцию greaternum.

Она имеет два аргумента : список чисел и заданное число. Функция возвращает первое число в списке превышающее заданное. Если этого числа нет - возвращается заданное число.

Программа.

(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))




Содержание  Назад  Вперед