Разработка программ рекурсивной структуры

Федеральное государственное бюджетное 
образовательное учреждение высшего образования 
«Московский государственный технический университет имени Н.Э. Баумана 
(национальный исследовательский университет)»
Т.Н. Ничушкина
Разработка программ 
рекурсивной структуры
Учебное пособие

УДК 004.432
ББК 32.81
        Н70
Издание доступно в электронном виде по адресу 
ebooks.bmstu.press/catalog/255/book1913.html
Факультет «Информатика и системы управления»
Кафедра «Компьютерные системы и сети»
Рекомендовано Научно-методическим советом
МГТУ им. Н.Э. Баумана в качестве учебного пособия
Ничушкина, Т. Н.
Разработка программ рекурсивной структуры : учебное пособие /
Н70
Т
. Н. Ничушкина. — Москва : Издательство МГТУ им. Н. Э. Баумана, 
2018. — 42, [6] с. : ил.
ISBN 978-5-7038-5004-6
Издание содержит теоретические сведения о разработке рекурсивных 
программ на языке С++. Приведены примеры рекурсивных программ и 
соответствующих алгоритмов.
Для студентов МГТУ им. Н.Э. Баумана, обучающихся по программе 
бакалавриата в рамках направлений подготовки «Математика и компьютерные науки», «Информатика и вычислительная техника» и изучающих 
дисциплину «Информатика». 
	
УДК 004.432
	
ББК 32.81
	
	
© МГТУ им. Н.Э. Баумана, 2018
© Оформление. Издательство
ISBN 978-5-7038-5004-6	
МГТУ им. Н.Э. Баумана, 2018

ПРЕДИСЛОВИЕ
Учебное пособие предназначено для углубления знаний, полученных 
студентами при освоении лекционного материала и в процессе семинарских занятий, а также самостоятельного изучения ими темы «Разработка программ рекурсивной структуры» по дисциплине «Информатика», 
входящей в основную образовательную программу бакалавриата по направлениям подготовки «Математика и компьютерные науки», «Информатика и вычислительная техника».
Цель учебного пособия — закрепление теоретических знаний и практических навыков, необходимых при разработке программ рекурсивной 
структуры и соответствующих алгоритмов, формирование умений и 
навыков распознавания и реализации таких алгоритмов.
После изучения темы «Разработка программ рекурсивной структуры» 
дисциплины студенты овладеют:
•
• базовыми знаниями по теории рекурсивных алгоритмов, необходимыми для разработки математических моделей объектов и формализации задач создания сложных программ;
•
• практическими навыками разработки рекурсивных алгоритмов;
•
• приемами тестирования и отладки программ рекурсивной структуры.
Планируемые результаты обучения. Студент должен:
знать
•
• виды задач рекурсивной структуры;
•
• способы решения задач с применением рекурсивных алгоритмов;
•
• области применения рекурсивных алгоритмов;
•
• способы оценки необходимости применения рекурсивных алгоритмов;
уметь
•
• выполнять анализ задачи и обосновывать необходимость применения рекурсивных алгоритмов для ее решения;
•
• разрабатывать алгоритм решения задачи;
•
• выбирать способ реализации рекурсивного алгоритма на языке 
С++;
•
• разрабатывать и отлаживать рекурсивные программы;
иметь навыки
•
• анализа предметных областей решаемых задач;
3

•
• анализа содержания задач и получения их формальной постановки;
•
• анализа и применения методов решения задач рекурсивной 
структуры.
Для изучения указанной темы необходимы знания, умения и навыки, полученные обучающимися при освоении школьной программы.
Основной целью освоения материала учебного пособия является 
самостоятельное изучение студентами темы «Разработка программ 
рекурсивной структуры». 
Учебное пособие состоит из трех глав.
В первой главе разъяснено понятие рекурсии, рассмотрены применения рекурсии в программировании и особенности разработки рекурсивных программ. Приведены структуры рекурсивных программ и 
подпрограмм, представлены способы их реализации, особенности выполнения и отладки. Даны примеры рекурсивных программ.
Во второй главе рассмотрены особенности задач, требующих полного перебора всех возможных вариантов для получения окончательного решения. Приведены способы реализации полного перебора и 
применения рекурсивных программ для сокращения числа рассматриваемых вариантов. 
В третьей главе даны определение и описание древовидных структур данных на примере бинарных деревьев. Продемонстрированы 
возможность и необходимость применения рекурсивных программ для 
обработки таких структур данных. Приведены примеры реальных 
программ обработки.
Главы учебного пособия следует прорабатывать последовательно, 
так как усвоение каждой из них обеспечивает успешное восприятие 
материала последующих глав.
Основные понятия и положения проиллюстрированы примерами, 
которые необходимо внимательно разобрать. 
В конце каждой главы приведены задания, которые нужно выполнить самостоятельно. Это обеспечит приобретение умений и навыков, 
необходимых для решения задач рекурсивной структуры в различных 
предметных областях. Ответы на контрольные вопросы, приведенные 
в конце пособия, позволят обучающемуся оценить степень понимания 
и усвоения им теоретических положений. 

ВВЕДЕНИЕ
Рекурсия (лат. recursio — возвращение) — определение, описание, 
изображение какого-либо объекта или процесса посредством самого 
этого объекта или процесса, при этом объект является частью самого 
себя. 
Термин «рекурсия» используется в различных специальных областях знания — от лингвистики до логики, но наиболее широкое применение рекурсия находит в математике и информатике, в частности 
в теории алгоритмов. На рекурсии построен язык Пролог, который 
используется в системах искусственного интеллекта. Рекурсия применяется в языках параллельного и динамического программирования. 
Возможности разработки рекурсивных алгоритмов заложены в современных универсальных языках программирования, таких как Паскаль 
и С++. Кроме того, в теории структур данных широкий класс структур относят к рекурсивным как по описанию, так и по алгоритмам 
обработки (например, списки и деревья). В программировании рекурсия используется при определении структур данных и разработке 
алгоритмов.
Все это делает изучение рекурсивных структур и алгоритмов очень 
важным для понимания многих дисциплин профессионального цикла.