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

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

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

Каноническим примером рекурсивных функций является функция вычисления факториала числа. Число n! (n факториал) определяется как (n)*(n-1)*(n-2)*... *(1). Факториал числа 0 равен 1. Заметьте также, что
n! = (n)*(n-1)!.

Математическое определение факториала рекурсивно и его реализация через рекурсивную функцию совершенно естественна. Ниже приведена программная реализация функции вычисления факториала числа на языке Паскаль.

function Factorial(n:integer):integer;

Begin

if n = 0 then Factorial := 1

else Factorial := n * Factorial(n-1);

end;

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

Ниже приведена программная реализация функции вычисления факториала числа на языке Лисп.

(defun factorial (n)

(if (= n 0) 1

(* n (factorial (- n 1)))

)

)

>(factorial 3)

Основная идея рекурсивного определения заключается в том, что функцию можно с помощью рекурентных формул свести к некоторым начальным значениям, к ранее определенным функциям или к самой определяемой функции, но с более «простыми» аргументами. Вычисление такой функции заканчивается в тот момент, когда оно сводится к известным начальным значениям.

Можно понаблюдать за работой рекурсивной функции при помощи содержащихся в интерпретаторе средств трассировки. Трассировка функции включается с помощью директивы TRACE: (trace factorial).

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

>(factorial 3)

0 FACTORIAL > (3)

1 FACTORIAL > (2)

2 FACTORIAL > (1)

3 FACTORIAL > (0)

3 FACTORIAL < (1)

2 FACTORIAL < (1)

1 FACTORIAL < (2)

0 FACTORIAL < (6)

Формат каждой записи, распечатываемой интерпретатором, рассмотрим на примере следующей записи:

0 FACTORIAL > (3)

Здесь, число 0 показывает уровень вызова функции, FACTORIAL – имя вызываемой функции, знак > говорит о том, что в функцию передаются параметры (знак < индицирует возврат функцией значения), (3) – в данном случае значение передаваемое в функцию FACTORIAL.

Ту же самую функцию вычисления факториала числа можно реализовать используя рассмотренные выше итеративные конструкции. Пример программной реализации функции вычисления факториала числа на языке Паскаль итерационным методом:

function Factorial(n:integer):integer;

var i,result:integer;

Begin

result := 1;

for i := 1 to n do

result := result*i;

Factorial := result;

end;

Ниже приведена программная реализация функции вычисления факториала числа итерационным методом на языке Лисп:

(defun factorial (n)

(do ((i 1 (+ i 1)) (result 1 (* result i)))

((> i n) result)

)

Обработка рекурсивных структур данных

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

В качестве примера работы с рекурсивными структурами данных рассмотрим процедуру поиска элемента в списке. Поиск представляет собой просмотр списка на предмет выявления соответствия между элементом данных (объектом поиска) и элементом просматриваемого списка. Если такое соответствие найдено, то поиск заканчивается успехом. В противном случае поиск заканчивается неуспехом. Элемент принадлежит списку, если выполняется одно из условий:

1. Элемент совпадает с головой списка.

2. Элемент принадлежит хвосту списка.

На языке Паскаль алгоритм поиска элемента в списке можно реализовать следующим образом:

typeTList = ^TElemList;

TElemList = record;

Inf: char;

Next: TList;.

end;

function Find(Elem:Сhar; List:TList):boolean;

Begin

{Проверяется случай, когда список пуст}

if (List = Nil) then Find:=false

else{список не пуст}

{искомый элемент совпадает с головой списка}

if List^.Inf = Elem then Find := true

{иначе ищем элемент в хвосте списка}

else Find := Find(Elem, List^.Next);

end;

Функция Find получает два аргумента: искомый элемент и список, в котором производится поиск.

На языке Лисп алгоритм поиска элемента в списке можно записать следующим образом:

(defun find(elem list)

(cond ((null list) nil)

((eql (car list) elem) t)

(t (find elem (cdr list)))))

Тело функции состоит из условного предложения, содержащего три ветви. Они участвуют в процессе вычисления в зависимости от возникающей ситуации:

1. ((null list) nil) – если список пустой, то ответ ­– nil (ложь). Переданный в качестве аргумента список может оказаться пустым либо с самого начала, либо список будет пустым при окончании его просмотра.

2. ((eql (car list) elem) t) – если первым элементом списка является искомый элемент, то ответом будет t (истина).

3. (t (find elem (cdr list))) – это условие выполнится только в случае, если ни одно из предыдущих условий не верно. В таком случае либо искомый элемент содержится в хвосте списка, либо вовсе не входит в список.

Понаблюдаем с помощью трассировки за вычислением функции find.

>(trace find)

FIND

>(find 3 ’(1 2 3 4))

0 FIND > (3 (1 2 3 4)) ; вызов уровня 1

1 FIND > (3 (2 3 4)) ; вызов уровня 2

2 FIND > (3 (3 4)) ; вызов уровня 3

2 FIND < (T) ; значение уровня 3

1 FIND < (T) ; значение уровня 2

0 FIND < (T) ; значение уровня 1

T

На первых двух уровнях рекурсии вычисление осуществляется по третьей, рекурсивной ветви. В рекурсивном вызове первым аргументом является искомый элемент, вторым аргументом – хвост текущего списка list –(cdr list). На третьем уровне выполняется предикат (eql (car list) elem) и значением вызова на третьем уровне становится T. Затем начинается возврат из рекурсии и значение T выдается пользователю.