Размещено на http://allbest.ru/

Размещено на http://allbest.ru/

Муниципальное общеобразовательное бюджетное учреждение «Гимназия № 3»

Секция: информатика

ТЕМА: «РЕКУРСИОННЫЕ И ИТЕРАЦИОНАЛЬНЫЕ АЛГОРИТМЫ НА ЯЗЫКЕ ПАСКАЛЬ»

Автор: ученик 11«Г» класса Климов Сергей Николаевич

Учитель информатики: Плотников Максим Вадимович

г. Кудымкар, 2012



СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. РЕКУРСИЯ

1.1 СЛОЖНАЯ РЕКУРСИЯ

1.2 СТЕК

2. ИТЕРАЦИЯ

2.1 ЦИКЛЫ

3. СРАВНЕНИЕ РЕКУРСИИ И ИТЕРАЦИИ

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ



ВВЕДЕНИЕ

Не так давно человечество вступило в новый XXI век - век информации и компьютеров. Благодаря бурному развитию научных, технических и технологических исследований стало возможным хранить огромные объёмы данных и преобразовывать их со скоростями, которые ещё несколько десятилетий назад могли только сниться. При создании сложных информационных систем перед проектировщиками стали задачи, требующие разработки новых концепций программирования.

Программы и продукты реализованные на рекурсивном и итерационных алгоритмах применяются в разных сферах, таких как программирование, экономика, математика, в сфере высоких технологий.

Объектом исследования является программирование в среде Турбо Паскаль, а также изучение рекурсивных и итерационных алгоритмов и их сравнение.

Цель работы: сравнить рекурсивные и итерационные алгоритмы, рассмотреть примеры их применения.

Задачи:

- рассмотреть определение рекурсии и рекурсивные алгоритмы в среде Турбо Паскаль;

- рассмотреть определение итерацию и итерационные алгоритмы в среде Турбо Паскаль;

- сравнить их на ряде примеров в среде Турбо Паскаль.

Методы исследования:

- описательный;

- метод практического сравнительного анализа.



1. РЕКУРСИЯ

Рекурсия -- это такой способ организации вспомогательного алгоритма (подпрограммы), при котором эта подпрограмма (процедура или функция) в ходе выполнения ее операторов обращается сама к себе. Вообще, рекурсивным называется любой объект, который частично определяется через себя.

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

Пример рекурсивной процедуры:

procedure Rec(a: integer);

begin

if a>0 then

Rec(a-1);

writeln(a);

end;

Рассмотрим, что произойдет, если в основной программе поставить вызов, например, вида Rec(3). Ниже представлена блок-схема, показывающая последовательность выполнения операторов.



Рис. 1. Блок схема работы рекурсивной процедуры.

Процедура Rec вызывается с параметром a = 3. В ней содержится вызов процедуры Rec с параметром a = 2. Предыдущий вызов еще не завершился, поэтому можете представить себе, что создается еще одна процедура и до окончания ее работы первая свою работу не заканчивает. Процесс вызова заканчивается, когда параметр a = 0. В этот момент одновременно выполняются 4 экземпляра процедуры. Количество одновременно выполняемых процедур называют глубиной рекурсии.

Четвертая вызванная процедура (Rec(0)) напечатает число 0 и закончит свою работу. После этого управление возвращается к процедуре, которая ее вызвала (Rec(1)) и печатается число 1. И так далее пока не завершатся все процедуры. Результатом исходного вызова будет печать четырех чисел: 0, 1, 2, 3.

Еще один визуальный образ происходящего представлен на рис. 2.



Рис. 2

Выполнение процедуры Rec с параметром 3 состоит из выполнения процедуры Rec с параметром 2 и печати числа 3. В свою очередь выполнение процедуры Rec с параметром 2 состоит из выполнения процедуры Rec с параметром 1 и печати числа 2. И т. д.

В приведенных примерах рекурсивный вызов стоит внутри условного оператора. Это необходимое условие для того, чтобы рекурсия когда-нибудь закончилась. Сама себя процедура вызывает с другим параметром, не таким, с каким была вызвана она сама. Если в процедуре не используются глобальные переменные, то это также необходимо, чтобы рекурсия не продолжалась до бесконечности.

Обычную рекурсию можно уподобить Уроборосу (рис. 3)



Рис. 3. Уроборос - змей, пожирающий свой хвост.

Рисунок из алхимического трактата «Synosius» Теодора Пелеканоса (1478г).

Ханойские башни

Согласно легенде в Великом храме города Бенарас, под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены 3 алмазных стержня, высотой в один локоть и толщиной с пчелу. Давным-давно, в самом начале времен монахи этого монастыря провинились перед богом Брамой. Разгневанный, Брама воздвиг три высоких стержня и на один из них поместил 64 диска из чистого золота, причем так, что каждый меньший диск лежит на большем. Как только все 64 диска будут переложены со стержня, на который Бог Брама сложил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир.

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

Независимо от Брамы данную головоломку в конце 19 века предложил французский математик Эдуард Люка. В продаваемом варианте обычно использовалось 7-8 дисков (рис. 4).

Рис. 4. Головоломка «Ханойские башни».

Предположим, что существует решение для n-1 диска. Тогда для перекладывания n дисков надо действовать следующим образом:

1) Перекладываем n-1 диск.

2) Перекладываем n-й диск на оставшийся свободным штырь.

3) Перекладываем стопку из n-1 диска, полученную в пункте (1) поверх n-го диска.

Поскольку для случая n = 1 алгоритм перекладывания очевиден, то по индукции с помощью выполнения действий (1) - (3) можем переложить произвольное количество дисков.

Создадим рекурсивную процедуру, печатающую всю последовательность перекладываний для заданного количества дисков. Такая процедура при каждом своем вызове должна печатать информацию об одном перекладывании (из пункта 2 алгоритма). Для перекладываний из пунктов (1) и (3) процедура вызовет сама себя с уменьшенным на единицу количеством дисков.

//n - количество дисков

//a, b, c - номера штырьков. Перекладывание производится со штырька a,

//на штырек b при вспомогательном штырьке c.

procedure Hanoi(n, a, b, c: integer);

begin

if n > 1 then

begin

Hanoi(n-1, a, c, b);

writeln(a, ' -> ', b);

Hanoi(n-1, c, b, a);

end else

writeln(a, ' -> ', b);

end;

1.1 СЛОЖНАЯ РЕКУРСИЯ

Возможна чуть более сложная схема: функция A вызывает функцию B, а та в свою очередь вызывает A. Это называется сложной рекурсией. При этом оказывается, что описываемая первой процедура должна вызывать еще не описанную. Чтобы это было возможно, требуется использовать опережающее описание.

procedure A(n: integer); {Опережающее описание (заголовок) первой процедуры}

procedure B(n: integer); {Опережающее описание второй процедуры}

procedure A(n: integer); {Полное описание процедуры A}

begin

writeln(n);

B(n-1);

end;

procedure B(n: integer); {Полное описание процедуры B}

begin

writeln(n);

if n<10 then

A(n+2);

end;

Опережающее описание процедуры B позволяет вызывать ее из процедуры A.

Если обычную рекурсию можно уподобить Уроборосу (рис.3), то образ сложной рекурсии можно почерпнуть из известного детского стихотворения, где «Волки с перепуга, скушали друг друга». Представьте себе двух съевших друг друга волков, и вы поймете сложную рекурсию или образ дракона кусающего змею за хвост, а змея кусает за хвост дракона (рис.5).

Рис. 5. Сложная рекурсия.

Н.Вирт отмечает, что "...мощность рекурсии связана с тем, что она позволяет определить бесконечное множество объектов с помощью конечного высказывания".

1.2 СТЕК

Стеком называется структура данных, в которой добавление и извлечение данных происходит с одного конца, называемого вершиной стека (рис. 6). Наглядным образом стека может служить стопка тарелок - добавлять или забрать тарелки можно только сверху. Каждая тарелка соответствует элементу данных.

Рис. 6. Наглядное представление стека.

Push (проталкивание) - традиционное название для операции добавления данных в стек, Pop (выталкивание) - традиционное название для операции извлечения данных из стека.

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

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



2. ИТЕРАЦИЯ

Итерация (лат. iteratio -- повторяю) в широком смысле слова -- термин, обозначающий повторение какого-либо действия, явления или процесса. В программировании Итерация -- это организация обработки данных, при которой действия повторяются многократно, не приводя при этом к вызовам самих себя.

Рис. 7. Арт-изображение итерации.

2.1 ЦИКЛЫ

рекурсия итерация алгоритм паскаль

При решении задач может возникнуть необходимость повторить одни и те же действия несколько или множество раз. В программировании блоки кода, которые требуется повторять не единожды, оборачиваются в специальные конструкции - циклы. У циклов выделяют заголовок и тело. Заголовок определяет, до каких пор или сколько раз тело цикла будет выполняться. Тело содержит выражения, которые выполняются, если в заголовке цикла выражение вернуло логическую истину (True, не ноль). После того как достигнута последняя инструкция тела, поток выполнения снова возвращается к заголовку цикла. Снова проверяется условие выполнения цикла. В зависимости от результата тело цикла либо повторяется, либо поток выполнения переходит к следующему выражению после всего цикла.

В языке программирования Паскаль существует три вида циклических конструкций:

ЦИКЛ for

Часто цикл for называют циклом со счетчиком. Этот цикл используется, когда число повторений не связано с тем, что происходит в теле цикла. Т.е. количество повторений может быть вычислено заранее

for счетчик:=значение to конечное_значение do

тело_цикла;

ЦИКЛ while

Цикл while является циклом с предусловием. В заголовке цикла находится логическое выражение. Если оно возвращает true, то тело цикла выполняется, если false - то нет.

Var i, n: integer;

begin

write ('Количество знаков: ');

readln (n);

i := 1;

while i <= n do begin

write ('(*) ');

i := i + 1

end;

readln

end.



ЦИКЛ repeat

В цикле repeat логическое выражение стоит после тела цикла. Причем, в отличие от цикла while, здесь всё наоборот: в случае true происходит выход из цикла, в случае false - его повторение.

var

i, n: integer;

begin

write ('Количество знаков: ');

readln (n);

i := 1;

repeat

write ('(*) ');

i := i + 1

until i > n;

readln

end.

Рис 8. Операторы циклов в Паскале



3. СРАВНЕНИЕ РЕКУРСИИ И ИТЕРАЦИИ

Вычисление факториала.

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

Через иттерацию:

Program p1;

Var n,s,i: integer;

begin

s:=1;

writeln('n');

readln(n);

if n >= 0 then

Begin

for i:=1 to n do

S:=S*i;

writeln(s);

end

else

writeln('ошибка');

readln;

end.

Через рекурсию:

Program Factorial;

var n: Integer;

function Fac (n: Integer): Real;

begin

if n<0 then

writeln (`Ошибка в задании N')

else

if n=0 then

Fac:=1

else Fac:=n*Fac(n-1)

end {Fac};

begin {main}

ReadLn(n);

WriteLn(`n! = ',Fac(n))

End. {main}

Рекурсивная форма организации алгоритма обычно выглядит изящнее итерационной и даёт более компактный текст программы, но при выполнении, как правило, медленнее и может вызвать переполнение стека (при каждом входе в программу её локальные переменные размещаются в особым образом организованной области памяти, называемой программным стеком). Переполнение стека особенно ощутимо сказывается при работе с сопроцессором: если программа использует арифметический сопроцессор, результат любой вещественной функции возвращается через аппаратный стек сопроцессора, рассчитанный всего на 8 уровней. Если, например, попытаться заменить тип REAL функции FAC (см. листинг 3) на EXTENDED, программа перестанет работать уже при N=8.

Архитектура стека непосредственно поддерживает рекурсию, поскольку каждый вызов процедуры автоматически размещает новую копию локальных переменных. Например, при каждом рекурсивном вызове функции факториала требуется одно слово памяти для параметра и одно слово памяти для адреса возврата. То, что издержки на рекурсию больше, чем на итерацию, связано с дополнительными командами, затраченными на вход в процедуру и выход из неё. Некоторые компиляторы пытаются выполнить оптимизацию, называемую оптимизацией хвостовой рекурсии (tail-recursion) или оптимизацией последнего вызова (last-call). Если единственный рекурсивный вызов в процедуре - последний оператор процедуры, то можно автоматически перевести рекурсию в итерацию.

Вычисление чисел Фибоначчи

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

Рассмотрим ещё один пример использования рекурсии - вычисление N-ого по счёту числа Фибоначчи. Числа Фибоначчи составляют последовательность, очередной элемент которой вычисляется по двум предыдущим значениям:

F_n=F_n-1 + F_n-2 .

Нулевое и первое значения должны быть заданы, их значения равны единице. Последовательности такого рода применяются, например, в программах генераторах случайных чисел. Вычисление 20-ого числа Фибоначчи реализовано в программе Fibonacci. Впрочем, номер числа можно изменить, задав в описании константы другое значение. Программа вычисления 20-ого числа Фибоначчи.

program Fibonacci;

uses Crt;

const n=20;

function F(n: word): longint;

begin

if (n=0) or (n=1) then

F:=1

else F:=F(n-1)+F(n-2); {рекурсивный вызов}

end;

function G(n: word): longint;

var x,y,t: longint; k: integer;

begin

x:=1;

y:=1;

for k:=2 to n do

begin

t:=y;

y:=x+y;

x:=t;

end;

G:=y; {итерация}

end;

begin

clrscr;

textcolor(lightgray +128);

write(`Считаю...');

textcolor(lightgray);

writeln(`--Ждите ответа--');

writeln;

writeln(`Рекурсивный алгоритм : F(`, n, ')= ', F(n));

writeln;

writeln(`Итерационный алгоритм : F(`, n, ')= ', G(n));

gotoxy(1,1);

clreol;

gotoxy(1,7);

write(`Нажмите <Enter>');

end.

В этой программе реализованы два метода решения задачи вычисления числа Фибоначчи. Один назовём итерационным методом - он заключается в прямом программировании итерационной формулы для чисел Фибоначчи. В функции G для этого используются три вспомогательные переменные типа LongInt. Решение с использованием рекурсивных вызовов запрограммировано с помощью функции F. Оператор, вычисляющий её значение, два раза вызывает саму эту функцию. Текст рекурсивной функции короче, лаконичнее итерационной функции.

Перевод числа в двоичную систему.

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

Взяв же целую часть от деления на 2:

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

while x>0 do

begin

c:=x mod 2;

x:=x div 2;

end;



Проблема здесь в том, что цифры двоичного представления вычисляются в обратном порядке (сначала последние). Чтобы напечатать число в нормальном виде придется запомнить все цифры в элементах массива и выводить в отдельном цикле.

С помощью рекурсии нетрудно добиться вывода в правильном порядке без массива и второго цикла. А именно:

procedure BinaryRepresentation(x: integer);

var

c, x: integer;

begin

{Первый блок. Выполняется в порядке вызова процедур}

c := x mod 2;

x := x div 2;

{Рекурсивный вызов}

if x>0 then

BinaryRepresentation(x);

{Второй блок. Выполняется в обратном порядке}

write(c);

end;

Вообще говоря, никакого выигрыша мы не получили. Цифры двоичного представления хранятся в локальных переменных, которые свои для каждого работающего экземпляра рекурсивной процедуры. То есть, память сэкономить не удалось. Даже наоборот, тратим лишнюю память на хранение многих локальных переменных x. Тем не менее, такое решение кажется мне красивым.



ЗАКЛЮЧЕНИЕ

В результате сравнения рекурсивных и итерационных алгоритмов можно сделать вывод: рекурсивная форма организации алгоритма обычно выглядит изящнее итерационной и даёт более компактный текст программы, но при выполнении, как правило, медленнее и может вызвать переполнение стека. Н.Вирт считает, что “... обычно понятие рекурсивных алгоритмов объяснялось на неподходящих примерах, из-за чего возникло широкое распространенное предубеждение против рекурсии в программировании”. То, что издержки на рекурсию больше, чем на итерацию, связано с дополнительными командами, затраченными на вход в процедуру и выход из неё. Если единственный рекурсивный вызов в процедуре - последний оператор процедуры, то можно автоматически перевести рекурсию в итерацию.

Н.Вирт отмечает, что "...мощность рекурсии связана с тем, что она позволяет определить бесконечное множество объектов с помощью конечного высказывания". Удобство же итерации заключается в том, что алгоритм по сути остается линейным.

Что выбрать: рекурсию или итерацию? Выбор зависит от конкретной задачи. В общем случае рекурсия требует дополнительных расходов памяти, т.к. она реализуется с использованием стеков, однако, если задача или используемые данные определены рекурсивно, применение рекурсии часто дает более простое решение и реализация алгоритма выглядит изящнее, чем итерация.



Список использованной литературы

1. Грызлов В.И., Грызлова Т.П. Турбо Паскаль 7.0. - М.: "ДМК", 2000. - 416 с.

2. Зуев Е.А. Turbo Pascal. Практическое программирование. - Приор,1997. - 336с.

3. Зуев Е.А. Язык программирования Turbo Pascal 6.0. - М.: Унитех, 1992. - 298с.,ил.

4. Лилитко Е.П. Практикум по программированию. Начальный курс. - Переяславль-Залесский, 1997.

5. Поляков Д.Б., Круглов И.Ю. Программирование в среде Турбо Паскаль 5.5. - М:., МАИ, 1992. - 576 с.

6. Фаронов В.В. Turbo Pascal 7.0. Начальный курс. - Нолидж, 1998. -620 с.

7. Федоренко Ю. Алгоритмы и программы на Турбо Паскале.

Список использованных интернет ресурсов

1. http://www.maxref.ru/referat_424_755.html

2. http://www.pas1.ru/cycles

3. http://www.pascal.com

4. http://www.tvd-home.ru/recursion#p1

Размещено на Allbest.ru

...