Студопедия — Выполнение работы. Определение рекурсивных и итерационных функций
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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






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

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

Каноническим примером рекурсивных функций является функция вычисления факториала числа. Число 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. Элемент принадлежит хвосту списка.

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

type TList = ^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 выдается пользователю.







Дата добавления: 2015-08-17; просмотров: 640. Нарушение авторских прав; Мы поможем в написании вашей работы!



Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...

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

Важнейшие способы обработки и анализа рядов динамики Не во всех случаях эмпирические данные рядов динамики позволяют определить тенденцию изменения явления во времени...

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...

ТЕХНИКА ПОСЕВА, МЕТОДЫ ВЫДЕЛЕНИЯ ЧИСТЫХ КУЛЬТУР И КУЛЬТУРАЛЬНЫЕ СВОЙСТВА МИКРООРГАНИЗМОВ. ОПРЕДЕЛЕНИЕ КОЛИЧЕСТВА БАКТЕРИЙ Цель занятия. Освоить технику посева микроорганизмов на плотные и жидкие питательные среды и методы выделения чис­тых бактериальных культур. Ознакомить студентов с основными культуральными характеристиками микроорганизмов и методами определения...

САНИТАРНО-МИКРОБИОЛОГИЧЕСКОЕ ИССЛЕДОВАНИЕ ВОДЫ, ВОЗДУХА И ПОЧВЫ Цель занятия.Ознакомить студентов с основными методами и показателями...

Меры безопасности при обращении с оружием и боеприпасами 64. Получение (сдача) оружия и боеприпасов для проведения стрельб осуществляется в установленном порядке[1]. 65. Безопасность при проведении стрельб обеспечивается...

Кран машиниста усл. № 394 – назначение и устройство Кран машиниста условный номер 394 предназначен для управления тормозами поезда...

Приложение Г: Особенности заполнение справки формы ву-45   После выполнения полного опробования тормозов, а так же после сокращенного, если предварительно на станции было произведено полное опробование тормозов состава от стационарной установки с автоматической регистрацией параметров или без...

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

Studopedia.info - Студопедия - 2014-2024 год . (0.009 сек.) русская версия | украинская версия