Рекурсивные процедуры и функции

Вид работы: Проект

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Наглядность – в языке, насколько это возможно, должны использоваться уже существующие символы, являющиеся хорошо известными и понятными для разработчиков и пользователей;
2. Единство – в различных фрагментах алгоритма, при обозначении идентичных или родственных терминов, необходимо использовать одни и те же символы. При этом необходимо, по возможности, минимизировать количество этих символов;
3. Гибкость – имеющийся в языке ограниченный набор средств представления должен обеспечивать сравнительно удобное, несложное описание известных методов математических вычислений;
4. Модульность – должна обеспечивать возможность описывать сложные алгоритмы в формате комплекса элементарных модулей, которые, в свою очередь, можно составлять по отдельности и использовать в алгоритмах различной сложности;
5. Однозначность – запись одного алгоритма должна приводить только к одному результату.

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

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

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

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

1. Машинные языки;
2. Машинно-ориентированные языки (ассемблеры);
3. Машинно-независимые (высокоуровневые) языки.

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

— алфавит;

— семантика;

— синтаксис.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

— объект;

— свойство объекта;

— метод обработки;

— событие;

— класс объектов.

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

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

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

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

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

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

— инкапсуляция;

— наследование.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

int Funс (int n)

{if (n > 0){Func (n++); return n;}

else return 0;}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

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

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

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

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

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

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

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

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

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

[10] 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.

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

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

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

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

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

Прикрепленные файлы:

_funkcii