САОД. Лабораторная работа №2. Лабораторная работа 2 1
 Скачать 163.43 Kb.
|
|
САОД Лабораторная работа № 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. Опишите древовидную рекурсию. |