Рекурсивные алгоритмы (преимущества и недостатки)

Министерство  образования и науки РФ

Красноярский  государственный педагогический университет 

им. В. П. Астафьева 

Филиал КГПУ им. В. П. Астафьева в г. Канске

 

 

 

 

Рекурсивные алгоритмы (преимущества и недостатки)

Реферат

 

 

 

                                                                        Выполнила: Бакасова Е. И.

                                                        студентка 3 курса

                                                                      Проверил: Баранов Ю. С.

                                                                                преподаватель информатики

 

 

 

 

КАНСК, 2012

СОДЕРЖАНИЕ

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

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

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

Объект называется рекурсивным, если для своего определения  или функционирования он прямо или  косвенно обращается к объекту в  некотором смысле такого же типа.

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

Понятие рекурсии очень широко и многогранно.

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

Задачами реферата являются:

1. Рассмотреть понятия «рекурсия», «алгоритм», «рекурсивный алгоритм».
2. Выявить преимущества и недостатки рекурсивного алгоритма.
3. Рассмотреть примеры задач с рекурсивным алгоритмом.

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

 

Что такое  рекурсия?

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

Типичная конструкция  такого рода:

      procedure proc(i:integer);

      begin

          anweisungen1;

          if bedingung then proc(i+1);

          anweisungen2;

      end;

Различают две  формы рекурсии: прямую и косвенную.

При прямой рекурсии процедура содержит оператор обращения  к самой себе: А→А (Рис. 1).

Рис. 1 Схема «Прямая рекурсия»

При косвенной  рекурсии одна процедура вызывает другую, которая сама либо посредством других процедур вызывает исходную процедуру: A→B→C→A (Рис. 2).

Рис. 2 Схема «Косвенная рекурсия»

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

 

Что такое алгоритм?

Одним из фундаментальных  понятий в информатике является понятие алгоритма. Происхождение  самого термина «алгоритм» связано  с математикой. Это слово происходит от Algorithmi – латинского написания имени Мухаммеда аль-Хорезми (787-850) выдающегося математика средневекового Востока. В своей книге «Об индийском счете» он сформулировал правила записи натуральных чисел с помощью арабских цифр и правила действий над ними столбиком. В дальнейшем алгоритмом стали называть точное предписание, определяющее последовательность действий, обеспечивающую получение требуемого результата из исходных данных. 

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

Такими свойствами являются:

• Дискретность (прерывность, раздельность) - алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов. Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.
• Определенность - каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.
• Результативность (конечность) - алгоритм должен приводить к решению задачи за конечное число шагов.
• Массовость - алгоритм решения задачи разрабатывается в общем виде, то есть, он должен быть применим для некоторого класса задач, различающихся только исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.

Чтобы алгоритм выполнил свое предназначение, его необходимо

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

• Первое правило – при построении алгоритма прежде всего необходимо задать множество объектов, с которыми будет работать алгоритм. Алгоритм приступает к работе с некоторым набором данных, которые называются входными, и в результате своей работы выдает данные, которые называются выходными. Таким образом, алгоритм преобразует входные данные в выходные.
• Второе правило – для работы алгоритма требуется память. В памяти размещаются входные данные, с которыми алгоритм начинает работать, промежуточные данные и выходные данные, которые являются результатом работы алгоритма. Память является дискретной, т.е. состоящей из отдельных ячеек. Поименованная ячейка памяти носит название переменной. В теории алгоритмов размеры памяти не ограничиваются, т. е. считается, что мы можем предоставить алгоритму любой необходимый для работы объем памяти.
• Третье правило – дискретность. Алгоритм строится из отдельных шагов (действий, операций, команд). Множество шагов, из которых составлен алгоритм, конечно.
• Четвертое правило – детерменированность. После каждого шага необходимо указывать, какой шаг выполняется следующим, либо давать команду остановки.
• Пятое правило – сходимость (результативность). Алгоритм должен завершать работу после конечного числа шагов. При этом необходимо указать, что считать результатом работы алгоритма.

Алгоритм должен быть формализован по некоторым правилам

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

• словесная (записи на естественном языке);
• графическая (изображения из графических символов);
• псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);
• программная (тексты на языках программирования).

При записи алгоритма  в словесной форме, в виде блок-схемы или на

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

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

Следовательно, язык для записи алгоритмов должен быть формализован. Такой язык принято  называть языком программирования, а  запись алгоритма на этом языке —  программой для компьютера. 

Что такое рекурсивный алгоритм?

Рекурсивный алгоритм – это алгоритм, в описании которого прямо или косвенно содержится обращение к самому себе.

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

 

Список

Список относится к особой группе структур - это так называемые рекурсивные структуры.

Приведем рекурсивное  определение списка: Списком называется совокупность связанных элементов, из которых один является особым элементом (первым, «головой»), а все остальные образуют список. Рекурсивные структуры в программировании замечательны тем, что многие операции по их обработке можно эффективно реализовать с использованием рекурсивных процедур, которые отличаются большой лаконичностью и наглядностью. В качестве примера приведём процедуру проверки, является ли Н1 подсписком списка Н:

 TYPE   Указатель = POINTER TO Элемент;

         Элемент = RECORD

                      INFO : Информация;

                      LINK : Указатель;

                   END

  PROCEDURE  Проверка (Н,Н1 : Указатель) : BOOLEAN;

         BEGIN

            IF H # NIL THEN

               RETURN (Н = Н1) OR Проверка (Н^.LINK, Н1)

            ELSE RETURN (Н = Н1)

            END

  END  Проверка.

Проверка (H # NIL) в этом примере нужна только для того, чтобы предотвратить попытку интерпретировать пустую ссылку как элемент списка при вызове Проверка (H^.LINK, H1). Ситуация (H=H1=NIL) рассматривается как положительный результат проверки.

Набор

Другим примером рекурсивной структуры является структура набора, которая определяется следующим образом: Набором называется совокупность связанных элементов, каждый из которых может быть либо атомом, либо набором. Атом определяет «неделимый» элемент набора, предназначенный для хранения элементарной порции информации. Реализация наборов основана на использовании разнородных списков. Например, ниже приведена (см. рис. 3) одна из возможных структур наборов. В этой структуре H1 - набор из четырех элементов (a, b, H2, c), из них H2 - набор, остальные - атомы. H2 состоит в свою очередь из трех элементов - атома c и двух наборов H3 и H4, причем набор H3 - пуст (не содержит элементов), а H4 содержит два атома (d и f).

Элементы H2, H3, H4 определяют «головы» новых наборов и одновременно являются членами наборов «верхнего уровня» - при этом структура набора оказывается адекватной для реализации динамических «вложенных» понятий предметной области. Например, в ассоциацию H1-«Акционеры» могут входить как отдельные частные лица, так и коллективы - организации, которые являются ассоциациями собственных акционеров.

                           H2

 

      H1

 

 

 

 

 

                                       H3       H4

                                      

 

 

 

 

 

                                       

 

 

 

 

 

 

 

Рис. 3 Схема «Структура набора»

 

Элементы H2, H3, H4 на приведенной иллюстрации участвуют  в двух связях - горизонтальной (связь  между членами одного набора) и  вертикальной (связь с членами «своего собственного» набора). Эта терминология часто используется для организации так называемых ортогональных списков, моделирующих структуры динамически изменяющегося плоского «игрового поля»: «разреженных» матриц, «кроссвордов», цепей «домино» и т.д. Понятие «игрового поля», разумеется, не означает, что ортогональные списки используются лишь в игровых задачах.