Файл: Лабораторная работа 2 1.pdf

САОД
Лабораторная работа № 2 1
Лабораторная работа № 2
Рекурсия
Цель работы: изучение рекурсии.
Общие сведения
В математике строгое определение некоторых понятий может опираться на то же понятие.
Такие определения называют рекурсивными (или индуктивными). Например, рекурсивно определяется факториал:







0
,
)!
1
(
0
,
1
!
N
если
N
N
N
если
N
Данное определение состоит из двух утверждений. Первое утверждение носит название базисного. Базисное утверждение нерекурсивно. Второе утверждение носит название рекурсивного или индуктивного. Оно строится так, чтобы полученная в результате повторных применений цепочка определений сходилась к базисному утверждению.
Рекурсия – это способ организации процесса вычисления, когда алгоритм обращается сам к себе.
Одну и ту же задачу часто можно решить двумя способами: с помощью итерации (с использованием цикла) и с помощью рекурсии.
В программировании рекурсивной называется подпрограмма, которая в процессе выполнения вызывает сама себя. Рекурсивная подпрограмма может быть реализована и как процедура, и как функция.
Принцип рекурсии позволяет решить сложную задачу путем последовательного решения более простых подзадач (например, вычисление факториала, определение натуральных чисел и некоторых функций).
Рекурсия необходима в тех случаях, когда требуется перебрать слишком много вариантов. Рекурсию принято считать одной из разновидностей циклического
алгоритма.
Рекурсивная форма организации позволяет придать алгоритму более компактный вид и экономить оперативную память компьютера. Содержание рекурсивного алгоритма отражает более сложный объект через более простой такого же типа.
Обычно рекурсивный алгоритм содержит следующие основные части:
 условие для завершения цикла;
 тело рекурсии, которое содержит действия – операторы, предназначенные для выполнения на каждой итерации;

САОД
Лабораторная работа № 2 2
 шаг рекурсии, на котором рекурсивный алгоритм вызывает сам себя.
Если каждая рекурсивная подпрограмма вызывает саму себя один раз, то такая организация рекурсии называется линейной (рисунок 1).
Рисунок 1. Структура подпрограммы R с линейной рекурсией
Различают два вида рекурсии подпрограмм:
1)
прямая или явная рекурсия — характеризуется существованием в теле подпрограммы оператора обращения к самой себе;
2)
косвенная или неявная рекурсия — образуется при наличии цепочки вызовов других подпрограмм, которые в конечном итоге приведут к вызову исходной.
Каждое обращение к рекурсивной подпрограмме вызывает независимую активацию этой подпрограммы. Совокупность данных, необходимых для одной активации рекурсивной подпрограммы, называется фреймом активации.
Фрейм активации включает:
• копии всех локальных переменных подпрограммы;
• копии параметров-значений;
• четырехбайтовые адреса параметров-переменных и параметров- констант;
• копию строки результата (для функций типа string);
Вход R(...)
Выход?
Выход
Базисная ветвь
Операторы " до вызова"
R(...)
Операторы "после вызова"
Нет
Да

САОД
Лабораторная работа № 2 3
• служебную информацию.
Сначала в каждой активации выполняются операторы, расположенные до рекурсивного вызова, затем (при достижении условия выхода) – нерекурсивная часть очередной активации, а затем – операторы, записанные после рекурсивного вызова.
Кроме линейной, достаточно часто встречается рекурсия, получившая название
древовидной. При древовидной рекурсии подпрограмма в течение одной активации вызывает саму себя более одного раза. Полученная в данном случае последовательность вызовов имеет форму дерева.
Основное требование к рекурсивным алгоритмам – процесс обращения не должен быть бесконечным. Другими словами, должна быть реализована проверка завершения вызова или в рекурсивном определении должно присутствовать ограничение или граничное условие, при котором дальнейшая инициализация рекурсии прекращается. Достаточно часто в рекурсивных алгоритмах используют некоторую управляющую переменную, при достижении определенного значения которой алгоритм прекращает свою работу.
Обращение к рекурсивному алгоритму, реализованному в виде функции или процедуры, ничем не отличается от обычной подпрограммы. При каждом новом рекурсивном обращении к памяти создается новая копия подпрограммы со всеми локальными переменными. Увеличение числа копий будет происходить до тех пор, пока не действует ограничение. Максимально возможное количество копий рекурсивной подпрограммы, которое может находиться в памяти компьютера, называется глубиной рекурсии.
Примером классической рекурсивной функции является возведение некоторого действительного числа x в целую степень N.
Рекурсивно степень можно определить:







0
,
*
0
,
1 1
N
если
x
x
N
если
x
N
N
Пример решения с помощью рекурсии function StepN(n: integer; x: real): real; begin if n=0 then
StepN := 1 else StepN := x*stepN(n-1, x); end;
Пример решения с помощью итерации function StepN(n: integer; x: real): real; var i:integer; y:real; begin y:=1; for i:=1 to N do y:=y*x;
StepN := y; end;

САОД
Лабораторная работа № 2 4
Задание
1. Задание должно быть выполнено обязательно двумя способами:
- без использования рекурсии;
- с использованием рекурсии.
Примечание. Для вариантов 7-10 достаточно выполнить задание с использованием рекурсии.
2. Некоторые задания допускают различные способы интерпретации - выбор за студентом!
Вариант 1.
Перевод десятичного числа в двоичную систему.
Вариант 2.
Разработать программу для вычисления n-го члена последовательности
Фибоначчи



1
=
Ф
1,
=
Ф
1
>
n при
,
Ф
+
Ф
=
Ф
1 0
2
- n
1
- n
n
Вариант 3.
Дано натуральное число N. Выведите слово ДА, если число N является точной степенью двойки, или слово НЕТ в противном случае.
Вариант 4.
Дано натуральное число N. Вычислите сумму его цифр.
Вариант 5.
Дано число n, десятичная запись которого не содержит нулей.
Получите число, записанное теми же цифрами, но в обратном порядке.

САОД
Лабораторная работа № 2 5
Вариант 6.
Разработать программу поиска элемента в упорядоченном массиве
Вариант 7.
Разработать программу, в которой рекурсивная функция, проверяет правильность расстановки скобок в строке. При правильной расстановке выполняются условия:
(а) количество открывающих и закрывающих скобок равно.
(б) внутри любой пары открывающая – соответствующая закрывающая скобка, скобки расставлены правильно.
Примеры неправильной расстановки: )(, ())(, ())(() и т.п.
Вариант 8.
В строке могут присутствовать скобки как круглые, так и квадратные скобки. Каждой открывающей скобке соответствует закрывающая того же типа (круглой – круглая, квадратной- квадратная). Напишите рекурсивную функцию, проверяющую правильность расстановки скобок в этом случае.
Пример неправильной расстановки: ( [ ) ].
Вариант 9.
Число правильных скобочных структур длины 6 равно 5: ()()(), (())(),
()(()), ((())), (()()).
Напишите рекурсивную программу генерации всех правильных скобочных структур длины 2n.
Указание: Правильная скобочная структура минимальной длины «()». Структуры большей длины получаются из структур меньшей длины, двумя способами:
(а) если меньшую структуру взять в скобки,

САОД
Лабораторная работа № 2 6
(б) если две меньших структуры записать последовательно.
Вариант 10.
Разработать программу, которая содержит процедуру, выводящую на экран все возможные перестановки для целых чисел от 1 до N.
Содержание отчета
Титульный лист.
Задание.
Теоретические положения.
Текст проекта (проектов).
Результаты работы программы, не использующей рекурсию.
Результаты работы программы, использующей рекурсию.
Список использованных источников.
Отчет оформляется в электронном виде с обязательным
приложением проекта.

САОД
Лабораторная работа № 2 7
Контрольные вопросы

1. Дайте определение рекурсии?
2. Сравните использование рекурсии и итераций.
3. Назовите основные части рекурсивного алгоритма.
4. Сравните прямую и косвенную рекурсии.
5. Сформулируйте основное требование к рекурсивным алгоритмам.

6. Что такое фреймом активации?
7. Что включает фрейм активации?
8. Опишите линейную рекурсию.
9. Опишите древовидную рекурсию.