Контрольные вопросы Задачи




Скачать 473.88 Kb.
НазваниеКонтрольные вопросы Задачи
страница1/4
ТипКонтрольные вопросы
rykovodstvo.ru > Руководство эксплуатация > Контрольные вопросы
  1   2   3   4

Рекурсия и рекурсивные алгоритмы




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

Содержание

1. Сущность рекурсии

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

3. Имитация работы цикла с помощью рекурсии

4. Рекуррентные соотношения. Рекурсия и итерация

5. Деревья

5.1. Основные определения. Способы изображения деревьев

5.2. Прохождение деревьев

5.3. Представление дерева в памяти компьютера

6. Примеры рекурсивных алгоритмов

6.1. Рисование дерева

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

6.3. Синтаксический анализ арифметических выражений

6.4. Быстрые сортировки

6.5. Произвольное количество вложенных циклов

6.6. Задачи на графах

6.7. Фракталы

7. Избавление от рекурсии

7.1. Явное использование стека

7.2. Запоминание последовательности рекурсивных вызовов

7.3. Определение узла дерева по его номеру

Контрольные вопросы

Задачи

Литература

1. Сущность рекурсии

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

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

1

2

3

4

5

6

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. И т. д.

В качестве самостоятельного упражнения подумайте, что получится при вызове Rec(4). Также подумайте, что получится при вызове описанной ниже процедуры Rec2(4), где операторы поменялись местами.

1

2

3

4

5

6

procedure Rec2(a: integer);

begin

  writeln(a);

  if a>0 then

    Rec2(a-1);

end;

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

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

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

Пример:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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. Опережающее описание процедуры A в данном примере не требуется и добавлено из эстетических соображений.

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

уроборос - змей, пожирающий свой хвост

Рис. 3. Уроборос – змей, пожирающий свой хвост. Рисунок из алхимического трактата «Synosius» Теодора Пелеканоса (1478г).

сложная рекурсия

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

3. Имитация работы цикла с помощью рекурсии

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

Для примера сымитируем работу цикла for. Для этого нам потребуется переменная счетчик шагов, которую можно реализовать, например, как параметр процедуры.

Пример 1.

1

2

3

4

5

6

7

8

procedure LoopImitation(i, n: integer);

{Первый параметр – счетчик шагов, второй параметр – общее количество шагов}

begin

  writeln('Hello N ', i);  //Здесь любые инструкции, которые будут повторятся

  if i<=n then             //Пока счетчик цикла не станет равным максимальному

    LoopImitation(i+1, n); //значению n, повторяем инструкции путем вызова

                           //нового экземпляра процедуры

end;

Результатом вызова вида LoopImitation(1, 10) станет десятикратное выполнение инструкций с изменением счетчика от 1 до 10. В данном случае будет напечатано:

Hello N 1
Hello N 2

Hello N 10

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

Можно поменять местами рекурсивный вызов и подлежащие повторению инструкции, как в следующем примере.

Пример 2.

1

2

3

4

5

6

procedure LoopImitation2(i, n: integer);

begin

  if i<=n then

    LoopImitation2(i+1, n);

  writeln('Hello N ', i);

end;

В этом случае, прежде чем начнут выполняться инструкции, произойдет рекурсивный вызов процедуры. Новый экземпляр процедуры также, прежде всего, вызовет еще один экземпляр и так далее, пока не дойдем до максимального значения счетчика. Только после этого последняя из вызванных процедур выполнит свои инструкции, затем выполнит свои инструкции предпоследняя и т.д. Результатом вызова LoopImitation2(1, 10) будет печать приветствий в обратном порядке:

Hello N 10

Hello N 1

Если представить себе цепочку из рекурсивно вызванных процедур, то в примере 1 мы проходим ее от раньше вызванных процедур к более поздним. В примере 2 наоборот от более поздних к ранним.

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

1

2

3

4

5

6

7

procedure LoopImitation3(i, n: integer);

begin

  writeln('Hello N ', i); {Здесь может располагаться первый блок инструкций}

  if i<=n then

    LoopImitation3(i+1, n);

  writeln('Hello N ', i); {Здесь может располагаться второй блок инструкций}

end;

Здесь сначала последовательно выполнятся инструкции из первого блока затем в обратном порядке инструкции второго блока. При вызове LoopImitation3(1, 10) получим:

Hello N 1

Hello N 10
Hello N 10

Hello N 1

Потребуется сразу два цикла, чтобы сделать то же самое без рекурсии.

Тем, что выполнение частей одной и той же процедуры разнесено по времени можно воспользоваться. Например:

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

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

c_1=x~\mathrm{mod}~2.

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

x_2=x~\mathrm{div}~2,

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

1

2

3

4

5

6

while x>0 do

begin

  c:=x mod 2;

  x:=x div 2;

  write(c);

end;

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

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

1

2

3

4

5

6

7

8

9

10

11

12

13

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. Тем не менее, такое решение кажется мне красивым.

4. Рекуррентные соотношения. Рекурсия и итерация

Говорят, что последовательность векторов \{\vec{x}_n\} задана рекуррентным соотношением, если задан начальный вектор \vec{x}_0=(x_0^1, \ldots, x_0^d) и функциональная зависимость последующего вектора от предыдущего

\vec{x}_n=\vec{f}(\vec{x}_{n-1})~~~~~(1)

Простым примером величины, вычисляемой с помощью рекуррентных соотношений, является факториал

n!=1 \cdot 2 \cdot 3 \cdot \ldots \cdot n

Очередной факториал n! можно вычислить по предыдущему как:

n!=(n-1)! \cdot n~~~~~(2)

Введя обозначение x_n=n! , получим соотношение:

x_n=x_{n-1} \cdot n,~x_0=1~~~~~(3)

Вектора \vec{x}_n из формулы (1) можно интерпретировать как наборы значений переменных. Тогда вычисление требуемого элемента последовательности будет состоять в повторяющемся обновлении их значений. В частности для факториала:

1

2

3

4

x := 1;

for i := 2 to n do

  x := x * i;

writeln(x);

Каждое такое обновление (x := x * i) называется итерацией, а процесс повторения итераций – итерированием.

Обратим, однако, внимание, что соотношение (1) является чисто рекурсивным определением последовательности и вычисление n-го элемента есть на самом деле многократное взятие функции f от самой себя:

x_n=\displaystyle{\underbrace{f(f(...f(x_0)))}_n}~~~~~(4)

В частности для факториала можно написать:

1

2

3

4

5

6

7

function Factorial(n: integer): integer;

begin

  if n > 1 then

    Factorial := n * Factorial(n-1)

  else

    Factorial := 1;

end;

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

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

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

x_n=x_{n-1}+x_{n-2},~x_0=1,~x_1=1~~~~~(5)

При «лобовом» подходе можно написать:

1

2

3

4

5

6

7

function Fib(n: integer): integer;

begin

  if n > 1 then

    Fib := Fib(n-1) + Fib(n-2)

  else

    Fib := 1;

end;

Каждый вызов Fib создает сразу две копии себя, каждая из копий – еще две и т.д. Количество операций растет с номером n экспоненциально, хотя при итерационном решении достаточно линейного по n количества операций.

На самом деле, приведенный пример учит нас не КОГДА рекурсию не следует использовать, а тому КАК ее не следует использовать. В конце концов, если существует быстрое итерационное (на базе циклов) решение, то тот же цикл можно реализовать с помощью рекурсивной процедуры или функции. Например:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

// x1, x2 – начальные условия (1, 1)

// n – номер требуемого числа Фибоначчи

function Fib(x1, x2, n: integer): integer;

var

  x3: integer;

begin

  if n > 1 then

  begin

    x3 := x2 + x1;

    x1 := x2;

    x2 := x3;

    Fib := Fib(x1, x2, n-1);

  end else

    Fib := x2;

end;

И все же итерационные решения предпочтительны. Спрашивается, когда же в таком случае, следует пользоваться рекурсией?

Любые рекурсивные процедуры и функции, содержащие всего один рекурсивный вызов самих себя, легко заменяются итерационными циклами. Чтобы получить что-то, не имеющее простого нерекурсивного аналога, следует обратиться к процедурам и функциям, вызывающим себя два и более раз. В этом случае множество вызываемых процедур образует уже не цепочку, как на рис. 1, а целое дерево. Существуют широкие классы задач, когда вычислительный процесс должен быть организован именно таким образом. Как раз для них рекурсия будет наиболее простым и естественным способом решения.

5. Деревья

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

5.1. Основные определения. Способы изображения деревьев

Определение: Деревом будем называть конечное множество T, состоящее из одного или более узлов, таких что:
   а) Имеется один специальный узел, называемый корнем данного дерева.
   б) Остальные узлы (исключая корень) содержатся в m \geq 0 попарно непересекающихся подмножествах t_1, t_2, \ldots, t_m, каждое из которых в свою очередь является деревом. Деревья t_1, t_2, \ldots, t_m называются поддеревьями данного дерева.

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

дерево

Рис. 3. Дерево.

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

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

Графически дерево можно изобразить и некоторыми другими способами. Некоторые из них представлены на рис. 4. Согласно определению дерево представляет собой систему вложенных множеств, где эти множества или не пересекаются или полностью содержатся одно в другом. Такие множества можно изобразить как области на плоскости (рис. 4а). На рис. 4б вложенные множества располагаются не на плоскости, а вытянуты в одну линию. Рис. 4б также можно рассматривать как схему некоторой алгебраической формулы, содержащей вложенные скобки. Рис. 4в дает еще один популярный способ изображения древовидной структуры в виде уступчатого списка.

способы изображения древовидных структур

Рис. 4. Другие способы изображения древовидных структур: (а) вложенные множества; (б) вложенные скобки; (в) уступчатый список.

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

Также можно провести аналогию между уступчатым списком и внешним видом оглавлений в книгах, где разделы содержат подразделы, те в свою очередь поподразделы и т.д. Традиционный способ нумерации таких разделов (раздел 1, подразделы 1.1 и 1.2, подподраздел 1.1.2 и т.п.) называется десятичной системой Дьюи. В применении к дереву на рис. 3 и 4 эта система даст:

1. A; 1.1 B; 1.2 C; 1.2.1 D; 1.2.2 E; 1.2.3 F; 1.2.3.1 G;

5.2. Прохождение деревьев

Во всех алгоритмах, связанных с древовидными структурами неизменно встречается одна и та же идея, а именно идеяпрохождения или обхода дерева. Это – такой способ посещения узлов дерева, при котором каждый узел проходится точно один раз. При этом получается линейная расстановка узлов дерева. В частности существует три способа: можно проходить узлы в прямом, обратном и концевом порядке.
  1   2   3   4

Похожие:

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

Контрольные вопросы Задачи iconКонтрольные вопросы тестового государственного междисциплинарного экзамена
Учеб пособие. Контрольные вопросы тестового государственного междисциплинарного экзамена. Под редакцией В. И. Козлова

Контрольные вопросы Задачи icon8. Контрольные вопросы
Введение ?

Контрольные вопросы Задачи iconТеория электрических цепей
Задание: изучить § 4, 5, 6 и письменно ответить на контрольные вопросы 23-26 на странице 137

Контрольные вопросы Задачи iconКонтрольные вопросы
Изучение принципов гигиенического нормирования и санитарно-гигиенической оценки параметров вибрации

Контрольные вопросы Задачи iconКонтрольные вопросы 23
Информационные технологии: Учеб для вузов / Б. Я. Советов, В. В. Цехановский. — М.: Высш шк., 2003.— 263 с

Контрольные вопросы Задачи iconОренбург 2015 Контрольные вопросы: Организация дозиметрического контроля
«Оренбургский государственный медицинский университет» Министерства здравоохранения РФ

Контрольные вопросы Задачи icon§ Общие вопросы Винберг Г. Г
Винберг Г. Г. Концептуальные основы, перспективные задачи и вопросы кадрового обеспечения гидробиологических исследований // Гидробиологический...

Контрольные вопросы Задачи iconКонтрольные вопросы Темы для сообщений
Структурная организация мк. Память и регистры мк. Ассемблер. Группа команд передачи данных

Контрольные вопросы Задачи iconКонтрольные вопросы Экзамен
Государственное автономное профессиональное образовательное учреждение «Ташлинский политехнический техникум» с. Ташла Оренбургской...

Контрольные вопросы Задачи icon3 Литература 12 1 Контрольные вопросы. 12
Государственное учреждение "Чувашский республиканский радиологический центр" Министерства природных ресурсов и экологии Чувашской...

Контрольные вопросы Задачи iconЗарегистрирована
Мчс россии органа, специально уполномоченного решать задачи гражданской обороны и задачи по предупреждению и ликвидации чрезвычайных...

Контрольные вопросы Задачи iconЗарегистрирована
Мчс россии органа, специально уполномоченного решать задачи гражданской обороны и задачи по предупреждению и ликвидации чрезвычайных...

Контрольные вопросы Задачи iconЗарегистрирована
Мчс россии органа, специально уполномоченного решать задачи гражданской обороны и задачи по предупреждению и ликвидации чрезвычайных...

Контрольные вопросы Задачи iconЗарегистрирована
Мчс россии органа, специально уполномоченного решать задачи гражданской обороны и задачи по предупреждению и ликвидации чрезвычайных...

Контрольные вопросы Задачи iconЗарегистрирована
Мчс россии органа, специально уполномоченного решать задачи гражданской обороны и задачи по предупреждению и ликвидации чрезвычайных...


Руководство, инструкция по применению






При копировании материала укажите ссылку © 2018
контакты
rykovodstvo.ru
Поиск