Файл: Рекурсивные и итерационные алгоритмы: Особенности и примеры использования (История развития языка программирования Pascal).pdf

ВВЕДЕНИЕ

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

Для наблюдаемого в современном мире явления, заключающегося в постоянном росте скорости и объема публикаций, применяется специальный термин «информационный взрыв», который показывает силу и охват процесса. Этот термин увидел свет в 1975 году, и с тех пор активно используется в научных публикациях. Ученые считают, что значительная часть населения Земли уже живет в условиях информационного общества, то есть общества, основной деятельностью которого является сбор, производство, обработка и использование информации.[6]

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

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

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

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

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

Наиболее активное применение рекурсивные методы находят в программировании. Использование рекурсивного подхода является одним из методов элегантного решения задач программирования использование рекурсивного подхода.

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

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

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

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

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

Задачи курсовой работы:

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

1. РЕКУРСИЯ. РЕКУРСИВНЫЕ ПРОЦЕДУРЫ И ФУНКЦИИ

1.1 Понятие рекурсии

На запрос «Рекурсия» Google выдает 5 миллионов результатов при частоте показа 14 тысяч ежемесячно.

Определение, которое находится на сайте Открытой энциклопедии Википедия, гласит:

«Рекурсия — определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя».

Рекурсия (от лат. recurrere — «возвращаться»):

• самоповторение;
• способ выражения понятия через само себя;
• введение некоторого предмета или события в самого себя, как элемента.

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

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

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

1.1.1 Рекурсия в лингвистике

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

Пример рекурсии из русского фольклора:

Вот море,

А на море – суша,

А на суше – пальма,

А на пальме клоп сидит

И видит море,

А на море – суша ...

Так же примером рекурсивного подхода в лингвистике служит стихотворная форма английского поэта Роберта Бернса, известная в России в переводе С.Я. Маршака – «Дом, который построил Джек».

На рекурсивную конструкцию для усиления яркости и сюжетной завершенности опираются многие писатели. Например, такой подход реализован в известном стихотворении А.Блока:

Ночь, улица, фонарь, аптека.

Бессмысленный и тусклый свет.

Живи еще хоть четверть века –

Все будет так. Исхода нет.

Умрешь – начнешь опять сначала,

И повторится все, как встарь:

Ночь, ледяная рябь канала,

Аптека, улица, фонарь.

1.1.2 Рекурсия в искусстве

Многочисленные примеры рекурсивного подхода можно найти в искусстве.

Классическим примером рекурсивного изображения является одна из визуальных форм рекурсии, названная «Эффект Дросте» в соответствии с наименованием марки какао Droste, использовавшей вышеописанный эффект в рекламе [19]. Картинка с «эффектом Дросте» представлена на рисунке 1.

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

Рисунок – Эффект Дросте

Рисунок – Рекурсивный объект – матрешка

1.1.3 Рекурсия в физике

Известны рекурсивные явления и в физике.

Одним из классических примеров бесконечной рекурсии являются два зеркала, находящиеся друг напротив друга: в каждом из них образуется коридор из уменьшающихся отражений зеркал. Пример «зеркальной рекурсии» представлен на рисунке 3.

Рисунок – Пример бесконечной рекурсии с зеркалом

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

1.1.4 Рекурсия в математике

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

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

Натуральное число – это либо 1, либо целое число, следующее за натуральным.

n-й степенью целого числа является 1, если n = 0 и число = a* a^n-1 при n отличном от 0.

Факториалом целого неотрицательного числа n является число 1, если n = 0, т.е. 0! = 1 или число n!=n*(n-1)! в противном случае. Иначе говоря,

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

• базовый,
• рекурсивный.[13]

В рекурсивном случае определение (или функция) обращается само к себе. В базовом случае такого обращения не происходит.

Для математики характерны также рекурсивные последовательности.[1]

Классическими, но неединственными, примерами рекуррентных последовательностей являются:

• числа Фибоначчи;
• формула золотой пропорции.

Числовой ряд, носящий сегодня итальянского математики Фибоначчи (Леонардо Пизанского), вырос из проблемы с кроликами, которая была изложена ученым в книге «Liber abacci» (1202 год):

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

Последовательность Фибоначчи определяется следующим рекуррентным соотношением:

Пе5рвые члены последовательности Фибоначчи:

1, 1, 2, 3, 5, 8, 13, 21,34,…

Золотая пропорция выражается с помощью рекуррентной формулы

Интересным математическим объектом, которые строятся на рекурсивной основе по принципу самоподобия, являются фракталы. Они подробнее рассмотрены в главе 3.

1.2 Рекурсия в программировании

В программировании рекурсией является вызов функции (процедуры) из самой процедуры (функции).

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

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

Рекурсия — это свойство объекта подражать самому себе. Объект является рекурсивным, если его части выглядят также как весь объект. Рекурсия очень широко применяется в математике и программировании:

• структуры данных:
  • • граф (в частности деревья и списки) можно рассматривать как совокупность отдельного узла и подграфа (меньшего графа);
    • строка состоит из первого символа и подстроки (меньшей строки);
• некоторые методы сортировки данных (например, QuikSort);
• построение фрактальных объектов;
• построение рекурсивных математических последовательностей;
• шаблоны проектирования, например декоратор, при реализации многопоточного сервера. Объект декоратора может включать в себя другие объекты, также являющиеся декораторами. [16]