![]() Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву ![]() Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Техника построения рекурсивных алгоритмовСодержание книги
Похожие статьи вашей тематики
Поиск на нашем сайте
В общем случае для правильной организации рекурсивных алгоритмов необходимо выполнение двух условий: • должно быть найдено представление общей задачи в терминах «более простой» задачи того же класса, которое определит последовательность рекурсивных вызовов; • рекурсивные вычисления не должны создавать бесконечную цепочку вызовов; для этого, во-первых, алгоритм должен включать хотя бы одно предписание, в котором при определенных условиях вычисление производится непосредственно, без рекурсивного вызова {терминальную ситуацию), а во-вторых, рекурсивные построения в конце В общем виде рекурсивное описание подпрограммы должно иметь одну из следующих структур или некоторую эквивалентную форму: if <условие> then <терминальная ситуация> else <рекурсивные вызовы> или while <условие> do Begin <рекурсивные вызовы> end; <терминальная ситуация> Существует два разных стиля построения рекурсивных алгоритмов, называемые восходящей и нисходящей рекурсией. Нисходящая рекурсия последовательно разбивает данную задачу на более простые, пока не доходит до терминальной ситуации. Только после этого она начинает строить ответ, а промежуточные результаты передаются обратно вызывающим функциям. Пример 7.1 Вычисление факториала. {Нисходящая рекурсия} Program Factorial; Var n: byte; Function Fact(n: byte): longint; Begin {Fact} if n = 0 then fact:= 1 {Терминальная ветвь } Else fact:= n*fact(n-1){Рекурсивная ветвь } End; {Fact} Begin {Factorial} Writeln('Введите n'); ReadLn(n); Writeln('Факториал', n:2, '=', fact(n)) End. {Factorial} Вызов, например, fact (5) означает, что функция fact вызывает себя раз $а разом: fact (4), fact(3),... до тех пор, пока не будет достигнута терминальная ситуация. При каждом вызове текущие вычисления «откладываются», локальные переменные и адрес возврата сохраняются в стеке. Tерминальная ситуация fact:= 1 достигается при п = 0. По достижении терминальной ситуации рекурсивный спуск заканчивается, начинается рекурсивный возврат изо всех вызванных на данный момент копий функции: начинает строиться ответ: n*fact(n-1), сохраненные локальные параметры выбираются из стека в обратной последовательности, а получаемые промежуточные результаты: 1*1, 2*1, 3*2*1, 4*3*2*1, 5*4*3*2*1 -передаются вызывающим функциям. Латинское recurrere означает «возвращение назад».
В восходящей рекурсии ответ строится на каждой стадии рекурсивного вызова, получаемые промежуточные результаты вычисляются перед рекурсивным вызовом и передаются в виде дополнительного рабочего параметра подпрограммы до тех пор, пока не будет достигнута терминальная ситуация. К этому моменту ответ уже готов и нужно только передать его вызывающей функции верхнего уровня. Пример 7.2 Вычисление факториала. { Восходящая рекурсия} Program Factorial; Var N: byte; Function Fact (n: byte, w: longint): longint; Begin {Fact} if n = 0 then fact:= w {Терминальная ветвь } Else fact:= fact(n-1, n*w) {Рекурсивная ветвь } End; {Fact} Begin {Factorial} Writeln('Введите N'); ReadLn(N): WriteLn(‘Фaктopиaл', N:2, '=', fact(N, 1)) End. {Factorial} Здесь w - рабочий параметр, применяемый для формирования результата. При первом вызове функции этот параметр надо инициализировать (придать ему начальное значение - 1), далее при каждом рекурсивном вызове, например при вычислении 5!, он принимает последовательно значения: 5*1,4*5*1, 3*4*5*1, 2*3*4*5*1, 1*2*3*4*5*1. Сравнивая нисходящий и восходящий варианты рекурсивного определения факториала, видим: результат вычисляется в разном порядке. Поскольку умножение коммутативно, это не влияет на окончательный ответ. Однако есть классы задач, при решении которых программисту требуется сознательно управлять ходом работы рекурсивных процедур и функций. Такими, в частности, являются задачи, использующие списковые и древовидные структуры данных. Например, при разработке трансляторов применяются так называемые атрибутированные деревья разбора, работа с которыми требует от программиста умения направлять ход рекурсии: одни действия можно выполнить только на спуске, другие -только на возврате. Поэтому понимание рекурсивного механизма и умение управлять им - это необходимые качества квалифицированного программиста. В следующем примере показана рекурсивная процедура с выполнением действий как до, так и после рекурсивного вызова (с выполнением действий как на рекурсивном спуске, так и на рекурсивном возврате). Пример 7.3 Счет от и до 1 на рекурсивном спуске и от 1 до и на рекурсивном возврате. При этом видно, как заполняется и освобождается стек.
{Выполнения рекурсивных действий до и после рекурсивного вызова} Program Stack; Var n: integer; Procedure Rekursion (i: integer); Begin {Rekursion} WriteLn(i:30); {Вывод на рекурсивном спуске } If i>1 Then Rekursion(i-1); WriteLn(i:3); {Вывод на рекурсивном возврате} End; {Rekursion} Begin {Stack} WriteLn ('Введите n:'); ReadLn(n); WriteLn; WriteLn ('Рекурсия:'); Rekursion(n); End. {Stack} В процедуре Rekursion операция WriteLn(i:30) выполняется перед рекурсивным вызовом, после чего WriteLn(*:3) освобождает стек. Поскольку рекурсия выполняется от и до 1, вывод по WriteLn(i:30) выполняется в обратной последовательности: п, п- 1,..., 1, а вывод по writeln(i:3) -в прямой: 1, 2,..., п (согласно принципу LIFO - «последним пришел, первым обслужен»). Возможная глубина рекурсивных вычислений определяется размером используемого стека. Насколько велик стек, можно установить с помощью бесконечной рекурсии. Причем использование директивы {$S+} при переполнении стека приведет к прерыванию программы с выдачей сообщения «Error 202: stack overflow error» («Ошибка 202: переполнение стека»). Пример 7.4 Определение размера стека. {Программа проверки размера стека} Program Stack_test; {$S+} {Включить контроль переполнения стека} Procedure proc(i: integer); Begin {proc} if i mod 1024 = 0 then WriteLn(i:6); proc(i+l); End; {proc} Begin {Stackjest} proc(l); End. {Stackjest} Стек связан с другой структурой памяти - с динамической облает С помощью директивы {$М} можно управлять размером стека. Формы рекурсий Простая линейная рекурсия Если в описании подпрограммы рекурсивный вызов в каждой из возможных ветвей различения случаев встречается не более одного раза, то такая рекурсия называется простой или линейной. Рассмотренные ранее рекурсивные функции/процедуры представляли простую рекурсию и содержали одну рекурсивную ветвь с одним рекурсивным вызовом. Рассмотрим простую рекурсивную функцию, содержащую две рекурсивные ветви. Пример 7.5 Нахождение НОД двух натуральных чисел по алгоритму Евклида. Алгоритм заключается в следующем: если т является точным делителем и, то НОД = т, в противном случае нужно брать функцию НОД от т и от остатка деления п на т. {Линейная рекурсия } {Алгоритм Евклида} Function NOD(n, m: byte): byte; Begin {NOD} if m >n then NOD:= NOD(m,n) {Рекурсивная ветвь } Else if m = 0 then NOD:= n {Терминальная ветвь } Else NOD:= NOD(m, n mod m) {Рекурсивная ветвь } End; {NOD} Первая рекурсивная ветвь в описании функции позволяет писать аргументы в любом порядке. В линейной рекурсии каждый рекурсивный вызов приводит непосредственно к одному дальнейшему рекурсивному вызову. Возникает простая линейная последовательность рекурсивных вызовов. Параллельная рекурсия Если в описании подпрограммы по меньшей мере в одной рекурсивной ветви встречаются два или более рекурсивных вызова, то говорят о нелинейной, или параллельной, рекурсии. Один из наиболее ярких примеров такой рекурсии дают числа Фибоначчи: F(0) = 0, F(1) = 1,F(N) = F(N-1) + F(N-2). Каждый элемент ряда Фибоначчи является суммой двух предшествующих элементов: 1 1 2 3 5 8 13 21 34 55... Пример 7.6 Вычислить n-й член ряда Фибоначчи. {Параллельная рекурсия. Числа Фибоначчи} Function fib(n: integer): integer; Begin {fib} If n = 0 then fib:= 0 {Терминальная ветвь } Else if n = 1 then fib:= 1 {Терминальная ветвь } Else fib:= fib(n-1)+ fib (n-2){Рекурсивная ветвь } End; {fib} Для определения текущего значения F(N) функциями вызывает себя дважды в одной и той же рекурсивной ветви - параллельно. Заметим, что параллельность является лишь текстуальной, но никак не временной: вычисление ветвей в стеке производится последовательно. В отличие от линейной рекурсии, при которой структура рекурсивных вызовов линейна, нелинейная рекурсия ведет к древовидной структуре вызовов. Вызовы лавинообразно ведут к экспоненциальному нарастанию возникающих рекурсивных вызовов - «каскаду вызовов», отсюда еще одно название - каскадная рекурсия.
Взаимная рекурсия Если процедура или функция вызывает себя сама, это называют прямой рекурсией. Но может встретиться ситуация, когда подпрограмма обращается к себе опосредованно, путем вызова другой подпрограммы, в которой содержится обращение к первой. В этом случае мы имеем дело с косвенной, или взаимной, рекурсией. Пример 7.7 Программа выдает простые числа от 1 до и, для чего используются функции next и prim, которые вызываются перекрестно. {Взаимная рекурсия. Простые числа} Program Primzahlen; Var n, i: integer; {Опережающее описание} Function Next (i: integer): integer; forward; {Prim определяет: j - простое число или нет} Function Prim(j: integer): Boolean; Var к: integer; Begin {Prim} k:=2; while (k*k <= j) and (j mod к <> 0) do к:= Next(k);{Prim вызывает Next} if j mod к = 0 then Prim:= false Else Prim:= true; end{Prim}; {Next вычисляет, каково следующее за j простое число. Параметры функции уже стоят в ссылке вперед} Function Next, Var k: integer; Begin {Next} k:= i+l; While not(Prim(k)) do k:= k+1; {Next вызывает, в свою очередь, Prim} next:= k; End {Next}; Begin {Primzahlen} Writeln('Введите положительное число п,'); ReadLn(n); Writeln('Предшествующие ему простые числа'); for i:= 2 to n do If Prim(i) then Write(i:6) End. {Primzahlen} Функция Prim определяет, является ли j простым числом, для этого просматриваются все простые числа начиная с двух, вплоть до корня изу, и проверяется, делится ли у на одно из таких простых чисел. Для поиска следующего простого числа используется функция Next, которая, в свою очередь, для идентификации простых чисел использует функцию Prim. Однако в Паскале любой идентификатор перед употреблением должен быть описан и при использовании подобных функций возникает проблема ссылок вперед. Для того чтобы такого рода вызовы стали возможны, вводится опережающее описание функции Next, которое предшествует обращению к ней и состоит из ее заголовка с указанием директивы forward, заменяющей тело функции. Теперь в функции Prim можно ис: пользовать обращение к Next - ее формальные параметры уже известны и компилятор может правильно организовать ее вызов. Полное описание функции Next помещается в программе после описания Prim, и в этом описании уже можно не указывать объявленные ранее формальные параметры.
|
||||||||
Последнее изменение этой страницы: 2017-02-17; просмотров: 890; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.148.103.214 (0.009 с.) |