Размещено на http://www.allbest.ru/

Негосударственное образовательное учреждение высшего образования

Московский технологический институт

Кафедра Информатики и Автоматизации

Уровень образования Бакалавриат ФГОС3+

Направление Информатика и вычислительная техника

Профиль Технологии разработки программного обеспечения

КУРСОВАЯ РАБОТА

на тему "Рекурсивные процедуры и функции. Механизм рекурсивных вызовов. Виды рекурсивных программ"

по дисциплине «Программирование на языке высокого уровня»

Выполнил (а) студент 4 курса

Семятнев Андрей

Москва 2017



Оглавление

Введение

1. Языки программирования высокого уровня

1.1 Понятие и основные термины

1.2 Преимущества и основные компоненты

1.3 Классификация

2. Рекурсия

2.1 Понятие рекурсии и её виды

2.2 Механизм рекурсивных вызовов

2.3 Преимущества и недостатки использования рекурсии

3. Примеры задач, решаемых при помощи рекурсии и разработка программного модуля на ЯПВУ C++

3.1 Примеры решения задач при помощи рекурсии

3.1.1 Задача 1. Числа Фибоначчи

3.1.2 Задача 2. Нахождение факториала

3.2 Постановка задачи

3.3 Разработка программного модуля

3.3.1 Входные и выходные данные

3.3.2 Порядок работы с программой и исходный код

3.3.3 Результат работы программы на контрольном примере

Заключение

Список использованной литературы

Приложение А

Приложение Б



Введение

программирование язык рекурсия модуль

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

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

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

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

Цель исследования, проведенного в рамках данного курсового проекта, заключается в разработке и реализации программ на высокоуровневом языке программирования C++.

Объектом исследования данного курсового проекта являются языки программирования высокого уровня.

Предметом исследования данного курсового проекта являются рекурсивные процедуры и функции, а также механизм и виды рекурсивных вызовов.

Задачи исследования:

1) анализ объекта исследования;

2) анализ теоретических сведений по теме исследования;

3) изучение практических примеров;

4) практическое применение полученных в ходе исследования знаний и навыков, в том числе, разработка программного модуля с применением рекурсивных механизмов;

5) формирование отчета о проведенном исследовании и решении поставленных задач, в том числе описание разработанного программного модуля, а также формулировка выводов.

В качестве языка программирования для решения поставленной задачи выбран язык C++, с учетом следующих его преимуществ:

·--доступность для понимания (в т.ч. осмысленность наименований конструкций);

·--масштабируемость;

·--возможность взаимодействия с памятью, портами и адресацией на низком уровне

·--возможность разработки общих алгоритмов для различных типов данных, их специализации, и вычисления на этапе компиляции, с использованием шаблонов.



1. Языки программирования высокого уровня

1.1 Понятие и основные термины

Язык программирования представляет собой систему обозначений, предназначенную для четкого описания алгоритма (т.е упорядоченного набора действий) для вычислительной машины. "Слова" такого языка называют командами (или операторами). Из ключевого отличия языков программирования от естественных автоматически вытекает еще одно отличие - свободное толкование выражений, которое характерно для естественных языков, в языках программирования недопустимо.

К языкам программирования предъявляются очень строгие требования. Основными из них являются:

·--наглядность - в языке, насколько это возможно, должны использоваться уже существующие символы, являющиеся хорошо известными и понятными для разработчиков и пользователей;

·--единство - в различных фрагментах алгоритма, при обозначении идентичных или родственных терминов, необходимо использовать одни и те же символы. При этом необходимо, по возможности, минимизировать количество этих символов;

·--гибкость - имеющийся в языке ограниченный набор средств представления должен обеспечивать сравнительно удобное, несложное описание известных методов математических вычислений;

·--модульность - должна обеспечивать возможность описывать сложные алгоритмы в формате комплекса элементарных модулей, которые, в свою очередь, можно составлять по отдельности и использовать в алгоритмах различной сложности;

·--однозначность - запись одного алгоритма должна приводить только к одному результату.

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

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

Уровень языка определяется степенью детализации последовательных действий (предписаний), и уровень тем выше, чем менее детализированы предписания.

Данный критерий подразумевает разделение языков программирования на следующие три уровня[4:

·--машинные языки;

·--машинно-оpиентиpованные языки (ассемблеры);

·--машинно-независимые (высокоуровневые) языки.

Машинно-ориентированные и машинные языки условно относят к низкоуровневым языкам. Такие языки требуют описания процесса обработки информации в мельчайших деталях. В свое время, высокоуровневые языки больше напоминают имитацию естественных языков. В них используются некоторые наборы слов разговорных языков, а также множество общепринятых математических символов. Разумеется, такие языки гораздо удобнее для человека и ориентированы именно на разработчика, в то время как низкоуровневые языки ориентированы на команды процессора.[12]

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

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

1.2 Преимущества и основные компоненты

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

Исходя из вышесказанного, следует сформулировать ключевые преимущества высокоуровневых языков программирования[14]:

·--алфавит высокоуровневого языка программирования значительно шире машинного алфавита, что способствует существенному повышению наглядности исходного кода программы;

·--набор допустимых к применению операций, является независимым от набора операций процессора, его выбор основывается на соображениях удобства формулировки алгоритма решения поставленной задачи, в зависимости от класса задачи;

·--предложения имеют достаточно гибкий и удобный в использовании формат, таким образом, появляется возможность формирования достаточно содержательного этапа обработки данных при помощи всего одного предложения;

·--для задания требуемых операций используются общепринятые математические обозначения;

·--в высокоуровневых языках всем данным присваиваются персональные имена, которые выбираются самим разработчиком, что крайне удобно для восприятия при условии, что все имена являются осмысленными;

·--как правило, в высокоуровневых языках существует возможность предусмотреть гораздо более широкий диапазон типов данных, в сравнение с набором типов данных низкоуровневых языков.

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

Основными компонентами высокоуровневых языков являются[16]:

·--Алфавит;

·--Семантика;

·--Синтаксис.

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

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

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

1.3 Классификация

Высокоуровневые языки программирования подразделяются на[13]:

·--процедурные языки;

·--логические языки;

·--объектно-ориентированные языки.

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

Развитие процедурных языков началось с появления проблемно-ориентированных языков. Эти языки получили свое название в виду того факта, что в основу их создания легла не "машина" а "задача" - это значит, что первостепенную роль в языке играет специфика класса задач, для которых предполагается разработка решения. К примеру, решение большинства научно-технических задач связано с осуществлением характерно емких расчетов по формулам, имеющим высокую степень сложности; в связи с этим, языки, ориентированные на подобного рода задачи, как правило, имеют удобные средства записи таких формул. Применение понятий, символов и терминов, которые являются привычными для специалистов соответствующей сферы знаний, значительно упрощает изучение и восприятие языка и позволяет облегчить и ускорить процесс разработки и отладки программного кода.

Многообразие классов задач способствовало активной разработке алгоритмических языков, в итоге, на сегодняшний день, их число достигло нескольких сотен. Но, в действительности, международное признание и широкое распространение смогли получить лишь 10-15 из них. Среди лидеров следует особо отметить Algol и Fortran - языки, основным назначением которых является решение научно-технических задач, Basic - создание решений для мелких вычислительных задач в режиме диалога, Cobol - разработка решений для задач из области экономики. Разумеется, любой процедурный язык может быть использован не только для решения задач того класса, для которого предназначен, но и других классов задач. Но на практике, такое использование языка может оказаться крайне неудобным, а иногда и весьма затруднительным.

Вместе с тем, в середине 60-х были начаты разработки алгоритмических языков широкой направленности - универсальных языков. Как правило, в основу разработки этих языков закладывался принцип объединения функционала узко-ориентированных языков. Среди таких языков наибольшее распространение получил C, Ruby, Pascal . Но разумеется, как и всякий универсальный инструмент, в множестве конкретных случаев, такие языки оказались менее эффективными, чем узко-ориентированные. [20]

Логические языки (Prolog, Lisp, Mercury, KLO и др.) ориентированы не на запись алгоритма решения задачи, а на систематическое и формализованное описание задачи с тем, чтобы решение следовало из составленного описания. В этих языках указывается что дано и что требуется получить. При этом поиск решения задачи возлагается непосредственно на ЭВМ.

Объектно-ориентированные языки (Object Pascal, C++, Java, Ruby и пр.). Руководящая идея объектно-ориентированных языков заключается в стремлении связать данные с обрабатывающими эти данные процедурами в единое целое - объект.

Объектно-ориентированный подход использует следующие базовые понятия[6]:

·--объект;

·--свойство объекта;

·--метод обработки;

·--событие;

·--класс объектов.

Объект -- совокупность свойств (параметров) определенных сущностей и методов их обработки (программных средств).

Свойство -- это характеристика объекта и его параметров. Все объекты наделены определенными свойствами, совокупность которых выделяют (определяют) объект.

Метод -- это набор действий над объектом или его свойствами.

Событие -- это характеристика изменения состояния объекта.

Класс -- это совокупность объектов, характеризующихся общностью применяемых к ним методов обработки или свойств.

Существуют различные объектно-ориентированные технологии, которые обеспечивают выполнение важнейших принципов объектного подхода:

·--инкапсуляция;

·--наследование.

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

Класс может иметь образованные от него подклассы. При построении подклассов осуществляется наследование данных и методов обработки объектов исходного класса. [17]

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

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



2. Рекурсия

2.1 Понятие рекурсии и её виды

Рекурсия является методом определения класса объектов или методов, предварительного задания одного или нескольких базовых методов класса или случаев, а затем, задания на этой основе критерия формирования определяемого класса, который ссылается, прямо или косвенно, на заданные базовые случаи[6].

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

Алгоритм (процедура, функция) является рекурсивным, только в том случае, когда в его определение включен прямой или косвенный вызов самого себя[10].

Адаптивным рекурсивным алгоритмом называется алгоритм, который посредством рекурсивного вызова учитывает некие субъективные характеристики задачи из области определения алгоритма.

Базисом рекурсии называется предложение, которое определяет некоторую исходную ситуацию или ситуацию в момент завершения. Как правило, такое предложение содержит некоторый простейший случай, в результате которого ответ предоставляется сразу, без использования рекурсии[19].

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

Подпрограммой называется все, что входит в состав рекурсивной функции.

Ключевое правило рекурсии можно выразить следующим предложением: перед рекурсивным вызовом должна осуществляться проверка на возврат из рекурсии[18].

Рекурсия бывает следующих видов:

·--прямая рекурсия - прямой вызов алгоритма (метода, процедуры или функции) в тексте самого алгоритма. В таком случае говорят, что функция, скажем, f1( ) осуществляет вызов самой себя.

·--косвенная рекурсия - включает циклическую последовательность вызовов некоторого количества алгоритмов (больше одного). На практике это выглядит следующим образом - функция f1( ) осуществляет вызов функции f2( ), которая, в свою очередь осуществляет вызов функции f3( ), после чего функция f3( ) снова осуществляет вызов функции f1( ).

Кроме того, как прямая, так и косвенная рекурсия может быть следующих типов[7]:

·--линейная - выполнение алгоритма влечет за собой еденичный вызов самого алгоритма;

·--ветвящаяся (нелинейная) - все экземпляры процедуры могу вызывать себя несколько раз.

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

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

Ярким примером такой программы является следующая функция[14]:

int Funс (int n)

{

if (n > 0)

{

Func (n++); return n;

}

else return 0;

}

Из кода хорошо видно, что при начальном значении n>0 функция будет увеличивать число n на +1 до тех пор, пока не закончится память, таким образом, условие выхода из рекурсии в данной подпрограмме никогда не выполняется.

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

2.2 Механизм рекурсивных вызовов

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

Вся мощь рекурсивного определения объекта заключается в том, что с помощью подобного конечного определения можно описать бесконечное количество объектов. Что же касается программ, то при помощи рекурсивной программы можно описывать бесконечные вычисления, при этом, исключается явное повторение фрагментов программы[1].

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

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

Примером таких программ, являются программы, подобные той, которая используется для генерирования чисел Фибоначчи. На каждом уровне рекурсии в подобной функции удваивается число вызовов, таким образом, число рекурсивных вызовов, необходимое для определения n-го числа Фибоначчи, является числом порядка 2N.

При увеличении числа n объем вычислений увеличивается в геометрической прогрессии. В итоге, чтобы вычислить 20-е число Фибоначчи требуется 2N вызовов или около миллиона, а чтобы вычислить 30-е число требуется 3N или примерно миллиард вызовов и т.д. Такое явление называется экспоненциальной сложностью[3].

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

Особенно, если вспомнить тот факт, что любая задача, которая может быть решена при помощи рекурсивного механизма, так или иначе, может быть решена и с применением итеративных методов (не рекурсивно). Как правило, предпочтение рекурсивному подходу отдается в тех случаях, когда он естественнее отражает суть задачи и результаты ее решения, то есть является более наглядным и легче подвержен отладке. Кроме того, итеративное решение не всегда может быть очевидным[5].

В основе использования механизма рекурсии лежит использование стека.

Стек, о котором уже упоминалось выше, представляет собой связную структуру данных, построенную по принципу FIFO (Fiгst In - Fiгst Out). В соответствии с этим принципом, вновь добавленные объекты размещаются в начале (вершине) стека, и выборка начинает осуществляться из вершины. На практике, это значит, что первый, попавший в стек, объект будет обработан последним, и наоборот, последний - первым. Стек представляет собой очень удобную структуру данных и используется в решении многих задач вычислительной техники.

Механизм вызова процедуры или функции в языках высокого уровня в высокой степени зависит от архитектуры аппаратной и программной платформ. В большинстве современных платформ используется аппаратный стек.

Аппаратный стек находится в ОЗУ, указатель стека расположен в паре особых регистров - SS:SP, эти регистры доступны программисту. Расширение аппаратного стека осуществляется в направлении уменьшения адресов, а указатель его адресует первый свободный элемент [2]. Схематично данный механизм изображен на рисунке 1.

Рисунок 1 - Аппаратный стек. Механизм вызова функции

Многие языки программирования, включая C, C++ и PASCAL, размещают в стеке локальные переменные процедур и других программных блоков. Стек представляет собой структуру, разбитую на фрагменты, каждый из которых представляет собой блок последовательных ячеек. При каждом вызове подпрограммы используется фрагмент стека, размер которого напрямую зависит от вызывающей функции. Каждая активизация процедуру сопровождается выделением в стеке памяти под ее локальные переменные; эта память освобождается при завершении процедуры. С учетом того, что при осуществлении вызовов процедур неминуемо соблюдается принцип вложенности, вершина стека всегда содержит локальные переменные, которые принадлежат процедуре, которая активна в настоящий момент[15].

Это значит, что если процедура r1( ) вызывает процедуру r2( ), то происходит следующее[8]:

1) В вершине стека размещается фрагмент необходимого размера. Он содержит следующие данные:

o фактические параметры вызова процедуры r2( );

o пустые ячейки, предназначенные для хранения локальных переменных процедуры r2( );

o адрес возврата, то есть адрес, выполняемой по завершению процедуры r2( ), команды процедуры r1( ). Если r2( ) является функцией, то фрагмент стека r2( ) содержит указатель ячейки фрагмента стека r1( ), которая предназначена для размещения в ней значения данной функции (адреса значения) ;

2) Управление получает первый оператор процедуры r2( );

3) После завершения работы процедуры r2( ), процедура r1( ) получает управление при помощи следующих последовательных шагов:

o из вершины стека извлекается адрес возврата;

o из стека извлекается фрагмент стека r2( ), фрагмент стека r1( ) ставится в вершину;

o возобновляется выполнение процедуры r1( ) начиная с команды, которая указана в адресе возврата.

Данная последовательность осуществляется и при прямой рекурсии, то есть при вызове процедурой r1 () самой себя.

Данный прием существенно упрощает реализацию рекурсии. При вызове процедурой самой себя, все ее локальные переменные записываются в новый блок стека, и вложенное обращение взаимодействует с собственным представлением локальных переменных. После завершения вызова, фрагмент стека, занимаемый локальными переменными вызова, освобождается, и актуальность приобретает представление предыдущего уровня[9].



2.3 Преимущества и недостатки использования рекурсии

Разумеется, у любого метода или способа есть свои плюсы и минусы.

В случае с рекурсией следует выделить следующие преимущества[8]:

·--рекурсия часто является самым легким методом разработки алгоритма решения многих задач (например нахождение факториала, расчет числа Фибоначчи);

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

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

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

·--рекурсия позволяет избежать ошибки "неверного порядка действий", "использования неинициализированных переменных» и прочие аналогичные ошибки.

Впрочем, недостатков у рекурсии тоже немало. Среди них следует отметить следующие:

·--высокая вероятность ввести программу в бесконечный цикл;

·--применение некоторых формул связано с несоизмеримо большими затратами ресурсов вычислительной машины;

·--высокая вероятность переполнения стека при слишком большом количестве вызываемых функций.

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

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



3. Примеры задач, решаемых при помощи рекурсии и разработка программного модуля на языке C++

3.1 Примеры решения задач при помощи рекурсии

3.1.1 Задача 1. Числа Фибоначчи

Рекурсия по своей сути схожа с методом математической индукции. В данном случае база индукции соответствует базе рекурсии. А в основе предположения индукции лежит предположение о том, что необходимая процедура подготовлена заранее. Шагу индукции можно сопоставить вызов генерируемой рекурсивной процедуры. И, разумеется, существует необходимость предусматривать хотя бы одно условие прерывания процесса.

Далее следует рассмотреть конкретные примеры решения практических задач.

Числа ряда Фибоначчи представляют собой последовательность, каждый следующий элемент равен сумме двух предыдущих элементов. Таким образом, зная два предшествующих элемента, искомый элемент последовательности можно вычислить по следующей формуле (1):

(1),

Где Fn - искомый элемент последовательности

Исходный код программы нахождения N-го числа ряда Фибоначчи будет выглядеть следующим образом:

#include "stdafx.h"

#include <iostream>

using namespace std;

int Fn(int n)

{

if(n < 3)

return 1;

return Fn(n - 2) + Fn(n - 1);

}

int main()

{

setlocale(LC_ALL, "Russian");

int n = 0;

cout << "Введите порядковый номер числа: ";

cin >> n;

cout << n <<"-м числом в ряде Фибоначчи является число " << Fn(n) << endl;

system ("pause");

return 0;

}

С результатом работы представленного кода можно ознакомиться на рисунке 3.

Рисунок 3 - Число Фибоначчи



На данном примере, достаточно просто проследить увеличение затрат ресурсов на исполнение. Если на одной и той же машине результаты для чисел до 30-го числа включительно выдаются практически мгновенно, а для 35-го числа задержка составляет значительно меньше одной секунды, то для 40-го числа программа выдает результат, лишь спустя две секунды, а для 41-го через 6 секунд.

3.1.2 Задача 2. Нахождение факториала

#include "stdafx.h"

#include <iostream>

using namespace std;

int fact (int n)

{

if (n==1 || n==0) return 1;

return n* fact (n - 1);

}

int main()

{

setlocale(LC_ALL, "Russian");

int n = 0;

cout << "Введите число ";

cin >> n;

cout << "Факториал числа " << n << " равен " << fact (n) << "\n";

system ("pause");

return 0;

}



Результат работы кода представлен на рисунке 4.

Рисунок 4 - Факториал

3.2 Постановка задачи

Обоснование выбора задачи: Задача расчета выплат по вкладу является одной из наиболее востребованных операций в области экономики. Кроме того, на примере решения данной задачи можно эффективно показать действие работы рекурсивного алгоритма, а сам алгоритм является довольно простым для восприятия.

Формулировка задачи:

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



3.3. Разработка программного модуля

3.3.1 Входные и выходные данные

Исходные данные:

s - стартовая сумма вклада (руб.);

p - ставка (в % годовых);

m - срок вклада (мес.)

i - порядковый номер месяца

Выходные данные:

Программа записывает результат вычислений в переменную s и выводит ее на экран.

3.3.2 Порядок работы с программой и исходный код

Запуск программы осуществляется посредством открытия файла 1.exe.

Программа представляет собой консольное приложение. Взаимодействие с программой ведется в режиме диалога.

Ввод исходных данных осуществляется в три шага. Каждый шаг соответствует одной переменной. Каждая переменная вводится после приглашения и завершается нажатием клавиши «Enter».

После ввода последней переменной программа выводит в окно консольного приложения результат расчета.

Очередное нажатие на клавишу «Enter» завершает работу приложения.

Исходный код программы представлен в Приложении А.

3.3.3 Результат работы программы на контрольном примере

Результат работы программы на контрольном примере изображен на рисунке 5.

Рисунок 5 - Контрольный пример

Кроме того, в программе предусмотрена проверка правильности ввода, таким образом, что нельзя ввести отрицательные или нулевые значения (рисунок 6).

Рисунок 6 - Проверка правильности ввода.



Заключение

На основании проведенного исследования можно сделать несколько выводов:

·--во-первых, рекурсивные алгоритмы есть универсальное средство решения разнообразных алгоритмических проблем. Любая разрешимая задача такого рода имеет рекурсивное решение, которое при этом отличается изяществом и простотой для восприятия человеком;

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

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

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

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

В процессе решения поставленных задач курсовой работы использовались прикладные системы программирования и необходимые методы решения. Было разработано программное приложение. В качестве инструментальной среды разработки была выбрана платформа С++ Builder.

В результате проведения исследования и решения поставленных задач были закреплены следующие, полученные в ходе изучения курса, навыки:

·--изучение теоретических сведений курса и применение их для решения практических задач;

·--постановка задачи и разработка алгоритма её решения;

·--применение прикладных систем программирования;

·--разработка основных программных документов;

·--работа с современными объектно-ориентированными системами программирования;

·--разработка и отладка программных приложений на объектно-ориентированном языке программирования высокого уровня C++.



Список использованной литературы

1. Баррон Д. Рекурсивные методы в программировании - М.: Вильямс, 2017. - 221 c.

2. Броницкая Н.А., Дармосюк В.Н., Бережецкая В.Г. КОМБИНАТОРНЫЕ МЕТОДЫ: РЕКУРСИЯ И ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ // Естественные и математические науки в современном мире: сб. ст. по матер. VI междунар. науч.-практ. конф. - Новосибирск: СибАК, 2013. - с.12-15

3. Вирт Н. Алгоритмы+структуры данных=программы: моногр. - М.: Вильямс, 2015. - 707 c.

4. Голицына, О.Л. Языки программирования: Учебное пособие / О.Л. Голицына, Т.Л. Партыка, И.И. Попов. -- М.: Форум, НИЦ ИНФРА-М, 2013. -- 400 c.

5. Грин Д., Кнут Д. Математические методы анализа алгоритмов - М.: Вильямс , 2015. - 398 c.

6. Катленд, Н. Вычислимость. Введение в теорию рекурсивных функций / Н. Катленд. - М.: Вильямс, 2015. - 952 c.

7. Кнут Д. Э. Искусство программирования, том 4, A. Комбинаторные алгоритмы, часть 1 = The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1 / под ред. Ю. В. Козаченко. -- 1. -- М.: Вильямс, 2013. -- Т. 4. -- 960 p.

8. Колмогоров А.Н. Теория информации и теория алгоритмов - М.: Вильямс, 2017. - 240 c.

9. Коротков М.А., Степанов Е.О. Основы теории алгоритмов - М.: Вильямс, 2016. - 174 c.

10. Мальцев, А.И. Алгоритмы и рекурсивные функции: моногр. / А.И. Мальцев. - М.: Вильямс, 2016. - 346 c.

11. Мейерс С. Эффективный и современный С++: 42 рекомендации по использованию C++11 и C++14 -- М. Вильямс, 2016. -- 304 с.

12. Орлов С. Теория и практика языков программирования: Учебник для вузов. Стандарт 3-го поколения. (рус.) - СПб.: Питер, 2013 - 688 с.

13. Пирс Б. Типы в языках программирования. -- Добросвет, 2012. -- 680 с.

14. Страуступ, Б. Язык программирования С++. Специальное издание / Б. Страуступ. -- М.: Бином, 2015. -- 1136 c.

15. Уэзерелл Ч. Этюды для программистов - М.: Вильямс, 2015. - 801 c.

16. Фридман, А.Л. Основы объектно-ориентированного программирования на языке Си++ / А.Л. Фридман. -- М.: Гор. линия-Телеком, 2012. -- 234 c.

17. Языки программирования и компиляторы -- 2017: труды конференции / Южный федеральный университет; под ред. Д. В. Дуброва. -- Ростов-на-Дону: Издательство Южного федерального университета, 2017. -- 282 с.

18. Рекурсивные функции - Библиотека MSDN, 2015. [Электронный ресурс] URL: https://msdn.microsoft.com/ru-ru/library/4bftz997.aspx дата обращения 04.07.17

19. Незнанов А.А. Рекурсия. вебинар программы «Предуниверсарий НИУ ВШЭ» к.т.н., доц. Незнанов Алексей Андреевич 2017-03-09 МНУЛ ИССА, ФКН НИУ ВШЭ, 2017 [Электронный ресурс] URL: https://www.slideshare.net/alexneznanov/2017-72978273 дата обращения 05.07.17

20. Robert Harper. Practical Foundations for Programming Languages. -- version 1.37 -- licensed under the Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 United States License., 2012. -- 544 p.



Приложение А

Исходный код программы

#include "stdafx.h"

#include <iostream>

#include <windows.h>

using namespace std;

double funk(double s, double p, int m, int i)

{

if(m==i)

return s;

s+=(s*(p/100/12));

return funk(s, p, m, i+1);

}

int main ()

{

setlocale(LC_ALL, "Russian");

int m;

double s, p;

cout<<"Сумма вклада (руб.): "<< endl;

cin>>s;

while (s<=0) {cout<<"Неверное значение. Cумма вклада не может быть меньше или равняться 0. Повторите ввод"<<endl; cin>>s;}

cout<<""<<endl;

cout<<"Ставка (% годовых): "<< endl;

cin>>p;

while (p<=0) {cout<<"Неверное значение. Ставка не может быть меньше или равняться 0. Повторите ввод"<<endl; cin>>p;}

cout<<"Срок (мес.): "<< endl;

cin>>m;

while (m<1) {cout<<"Неверное значение. Срок не может быть менее 1 месяца. Повторите ввод"<<endl; cin>>m;}

cout<<""<<endl;

if (m==1) cout<<"По истечении "<<m<<" месяцa сумма по вкладу составит "<<funk(s, p, m, 0)<<" рублей."<<endl;

else cout<<"По истечении "<<m<<" месяцев сумма по вкладу составит "<<funk(s, p, m, 0)<<" рублей."<<endl;

cout<<""<< endl;

cout<<""<< endl;

cout<<""<< endl;

system("pause");

return 0;

}



Приложение Б

Проверка решения в MS Excel

Рисунок 8 - Формулы Excel, использованные при проверке вычислений

Размещено на Allbest.ru

...