Рекурсивные алгоритмы

СОДЕРЖАНИЕ Введение 1. Рекурсивные алгоритмы 1.1. Рекурсивные определения 1.2. Рекурсивные подпрограммы
1.3. Косвенная рекурсия и опережающее описание 1.4. Рекурсивные структуры 1.4.1. Список 1.4.2. Набор 1.4.3. Дерево 1.5. Примеры решения задач с помощью рекурсии 1.5.1. “Ханойская башня”. 1.5.2. Двумерное множество Кантора 1.5.3. “Индийский алгоритм” возведения в степень 1.5.4. Вычисление факториала 1.5.5. Числа Фибоначчи 2. Представление данных в памяти ЭВМ 3. Разработка программы 3.1. Программа роста банковского вклада по месяцам 3.2. Блок-схема к программе Вывод Список использованных источников УСЛОВНЫЕ ОБОЗНАЧЕНИЯ, СИМВОЛЫ, НЕСТАНДАРТНЫЕ СОКРАЩЕНИЯ ПСЗ – полная скобочная запись НОД – наибольший общий делитель GCD – Greatest Common Divisor (англ. наибольший общий делитель) ПОЛИЗ – польская инверсная запись ВВЕДЕНИЕ Система программирования Турбо Паскаль представляет собой единство двух в известной степени самостоятельных начал: компилятора с языка программирования Паскаль (язык назван в честь выдающегося французского математика и философа Блеза Паскаля (1623-1662)) и некоторой инструментальной программной оболочки, способствующей повышению эффективности создания программ. Паскаль – замечательный язык программирования, который относительно прост в изучении, довольно ясен и логичен и, будучи первым изучаемым языком программирования, приучает к хорошему стилю. Паскаль воспитывает дисциплину структурного программирования и программирования вообще лучше, чем другие языки программирования, такие, как, например, БЕЙСИК. Паскаль – гибкий и развитый в отношении типов данных язык. Привлекательны его рекурсивные возможности, а также поддержка технологии объектно-ориентированного программирования. Изучение программирования на языке Паскаль может дать хороший старт в огромный и увлекательный мир программирования. Обучение языку программирования проходит намного более эффективно с изучением примеров. Чаще всего (процедурное) программирование использует итерации, то есть циклы; однако рекурсия – описание объекта или вычисления в терминах самого себя – является более простым математическим понятием, а также мощной, но мало используемой техникой программирования. Некоторые программисты считают (и не без оснований), что рекурсия – это сердце и душа языка Паскаль. В этой работе мы рассмотрим применение рекурсии в программах на Паскале. Здесь рассматриваются примеры рекурсивных алгоритмов и программирование комбинаторных вычислений. Ко всему прочему мы научимся представлять данные в памяти ЭВМ и разрабатывать программы в среде Турбо Паскаль. 1. РЕКУРСИВНЫЕ АЛГОРИТМЫ Я уверен, что всеобщее признание рекурсивных методов в конце концов будет иметь такое же значительное влияние на программирование, как и введение подпрограмм. Д. Баррон 1.1. Рекурсивные определения Часто говорят, что рекурсивные определения – это когда что-то определяется с его же помощью. Фраза эта не совсем точная, а вернее, совсем неточная. Каждое определение задаёт что-то, и этим чем-то являются, как правило, объекты, образующие некоторое множество. Определение называется рекурсивным, если оно задаёт элементы множества с помощью других элементов этого же множества. Объекты, заданные рекурсивным определением, также называются рекурсивными. И наконец, рекурсия – это использование рекурсивных определений. Пример 1 Значение функции факториал задаются выражением: 0!=1, n=n*(n-1)!. Они образуют множество {1,2,6,…}: 0!=1, 1=1*0!, 2=2*1!, 6=3*2! и т.д. Все его элементы, кроме первого, определяются рекурсивно. Как видим, функция факториал задаётся рекуррентным соотношением порядка 1 и начальным отрезком 0!=1. Вообще, любое рекуррентное соотношение порядка k вместе с заданием первых k элементов последовательности является примером рекурсивного определения. Пример 2 Арифметические выражения с константами и знаком операции “+” в полной скобочной записи (ПСЗ) задаются таким определением: 1) константа является выражением в ПСЗ; 2) если Е и F являются выражениями в ПСЗ, то (Е)+(F) также является выражением в ПСЗ. Такими выражениями являются, например, 1, 2, (1)+(2), ((1)+(2))+(1). Все они, кроме констант 1 и 2, определяются рекурсивно. Объекты, определённые в примерах 1 и 2, т.е. значения функции факториал и скобочные записи выражений, являются рекурсивными. В рекурсивном определении не должно быть “заколдованного круга”, когда объект определяется с помощью себя самого или с помощью других, но заданных через него же. Пример 3 Изменим определение функции факториал на следующее: n!=n*(n-1)! При n>0, 0!=1!. Сначала значение функции от 1 выражается через её же значение от 0, которое, в свою очередь, – через значение от 1. По такому определению так и не узнать, чему же равно 1!. Пример 4 “У попа была собака, поп её любил, она съела кусок мяса, поп её убил, в землю закопал и на камне написал, что у попа…” и т.д. Эта печальная история не имеет конца, и нельзя сказать, что же именно поп написал на камне. Пример 5 “Где ты деньги берёшь?” – “В тумбочке”. – “А там они откуда?” – “Жена кладёт”. – “А у неё откуда?” – “Я даю”. – “А где ты берёшь?” – “В тумбочке…” В этом старом анекдоте не называется настоящий источник хранения денег. Если через А, В, С обозначить мужа, его жену и тумбочку, то перемещение денег изображается так: АßСßВßАß…и настоящий источник денег остаётся неизвестным. Чтобы подобная “дурная бесконечность” не возникала в рекурсивном определении, должны выполняться следующие условия: 1) множество определяемых объектов является частично упорядоченным; 2) каждая убывающая по этому упорядочению последовательность элементов заканчивается некоторым минимальным элементом; 3) минимальные элементы определяются нерекурсивно; 4) неминимальные элементы определяются с помощью элементов, которые меньше их по этому упорядочению. Нетрудно прийти к убеждению, что определения из примеров 1 и 2 удовлетворяют этим условиям, а из примеров 3–5 – нет. Для тех, кому не знакомы термины “частично упорядоченное множество” и “минимальный элемент”, дадим небольшое пояснение. Любое множество пар, составленных из элементов некоторого множества, называется отношением на этом множестве. Например, множество пар {(1,1), (1,2), (2,1)} – на множестве {1,2}. Отношение называется отношением частичного порядка, если оно имеет такие свойства: 1. Для каждого элемента a множества в отношении есть пара (a, a). 2. Если в отношении есть пара (a, b) с различными элементами a и b, то пары (b, a) там нет. При этом мы говорим, что а меньше b. Во множестве могут быть и несравнимые элементы, которые друг с другом пары не образуют. 3. Если а меньше b, а b меньше c, то a меньше c. Впрочем, элементов a, b, c таких, что a меньше b, а b меньше с, во множестве может и не быть – при выполнении свойств (1) и (2) отношение будет отношением частичного порядка.
Множество с заданным на нём отношением частичного порядка называется частично упорядоченным. Элемент частично упорядоченного множества называется минимальным, если во множестве нет элементов, меньших его. Очевидно, что в примере 1 каждые два элемента множества {1, 2, 6,…} сравнимы между собою, а минимальным является 1. В примере 2 один идентификатор меньше другого, если тот образуется из него дописыванием символов в конце. Так, а меньше а1 и ааа, но а1 и аа несравнимы. Идентификатор а – минимальный. В примере 3 одно выражение меньше другого, если оно является его частью. Так, 1 и 2 меньше, чем (1)+(2), а (1)+(2) меньше, чем ((1)+(2))+(1); минимальными элементами являются все возможные константы, между собою несравнимые.
1.2. Рекурсивные подпрограммы Рекурсия не является чем-то сверхсложным, а просто является ещё одним способом программирования, которым можно пользоваться успешно или злоупотреблять, как и всем остальным. Д. Баррон По правилам языка Паскаль, задающим область действия определений, тело подпрограммы может содержать вызовы подпрограмм, заголовки которых записаны выше в тексте программы. Отсюда вытекает, что подпрограмма может содержать вызовы самой себя – рекурсивные вызовы. Выполнение такого вызова ничем не отличается от выполнения вызова любой другой подпрограммы. Подпрограмма с рекурсивными вызовами называется рекурсивной. Пример 6 Напишем рекурсивную функцию f по такому определению функции факториал: n!=n*(n-1)! при n>1, 1!=1 (считается, что n>0). function f(n:integer):integer; begin if n=1 then f:=1 else f:=n*f(n-1) end; При имитации выполнения вызовов рекурсивных подпрограмм их локальные переменные обозначают следующим образом. Если подпрограмма F вызвана из программы, то её локальная переменная Х обозначается F.X. При выполнении каждого рекурсивного вызова подпрограммы F, указанного в её теле, появляется новая переменная Х. Она обозначается добавлением префикса F. к обозначению переменной Х в предыдущем вызове: F.F.X, F.F.F.X и т.п. Пример 7 Имитацию выполнения вызова f(2) функции из примера 6 можно представить в виде таблицы: Что выполняется Состояние памяти Вызов f(2) f.n f.f 2 ? Вычисление n=1: false 2 ? начало f:=n*f(1) 2 ? Вызов f(1) 2 ? f.f.n f.f.f 2 ? 1 ? Вычисление n=1: true 2 ? 1 ? f:=1 2 ? 1 1 Возвращение из вызова f(1) 2 ? Окончание f:=n*f(1) 2 2 Пример 8 Наибольший общий делитель НОД(a, b) натуральных чисел a и b можно вычислить рекурсивно на основании таких равенств: § если b=0, то НОД(a, b)=a; § если а modb=0, то НОД(a, b)=b; § если а modb>0, то НОД(a, b)= НОД(b, а modb). Этому определению соответствует следующая рекурсивная функция вычисления НОД: function GCD(a, b:integer):integer; (Greatest Common Divisor – Наибольший Общий Делитель) begin if b=0 then GCD:=a else if a mod b=0 then GCD:=b else GCD:=GCD(b, a mod b) end; С рекурсивными подпрограммами связаны два важных понятия – глубина рекурсии и общее количество вызовов, порожденных вызовом рекурсивной подпрограммы. Рассмотрим первое из них. В примере 6 приведена функция вычисления n!. Очевидно, что её вызов с аргументом, например 4, заканчивается лишь по окончании вызова с аргументом 3, а тот, в свою очередь, после вызова с аргументом 2 и т.д. Такие вызовы называются вложенными. Таким образом, вызов с аргументом 4 порождает ещё три вложенных вызова. Вообще, при вызове этой функции с аргументом n порождается ещё n-1 вызов, и общее количество незаконченных вызовов достигает n. Таким образом, глубиной рекурсии вызова подпрограммы называется максимальное количество незаконченных рекурсивных вызовов при выполнении её вызова. При выполнении вызова с глубиной рекурсии т одновременно существует т экземпляров локальной памяти. Каждый экземпляр имеет определённый размер, и если глубина будет чересчур большой, то автоматической памяти, предоставленной процессу выполнения программы, может не хватить. Второе понятие можно назвать общим количеством вложенных вызовов, порождённых вызовом рекурсивной подпрограммы. Это количество влияет на время выполнения вызова. Пример 9 По свойствам треугольника Паскаля, биномиальный коэффициент C(m, n)=1 при тВ соответствии с этим равенством напишем рекурсивную функцию вычисления биномиального коэффициента C(m, n) по m, n, где 0function C(m, n:integer):integer; begin if (mor (n=0) or (n=m) then C:=1 else C:=C(m-1, n-1)+C(m-1, n) end; Как видим, каждый вызов, в котором значения аргументов m>1, 0Нетрудно понять, что чем больше т и чем ближе n к т/2, тем большим будет общее количество вложенных вызовов. Мы не будем точно определять его зависимость от аргументов. Скажем лишь, что при n=m div2 или n=m div2+1 оно больше, чем 2т/2. Например, при т=60 это 230, или примерно 109. Если даже предположить, что за секунду можно выполнить 106 вызовов, то нужно больше 1000 секунд, т.е. более четверти часа. Однако нетрудно написать рекурсивную функцию, вызов которой с аргументом т порождает не более т/2 вложенных вызовов.
Таким образом, употребление рекурсивных подпрограмм требует осторожности и умения оценить возможную глубину рекурсии и общее количество вызовов. Не всегда стоит писать рекурсивные подпрограммы непосредственно по рекурсивному определению. По крайней мере, для вычисления биномиальных коэффициентов вообще лучше воспользоваться циклом. Дело в том, что выполнение каждого вызова подпрограммы требует дополнительных действий компьютера. Поэтому циклический вариант описания вычислений выполняется, как правило, быстрее рекурсивного. Также не следует употреблять рекурсию для вычисления элементов рекуррентных последовательностей. При большой глубине рекурсии это вообще может привести к исчерпанию автоматической памяти и аварийному завершению программы.
1.3. Косвенная рекурсия и опережающее описание Рекурсивный вызов может быть косвенным. В этом случае подпрограмма обращается сама к себе опосредованно, путём вызова другой подпрограммы, в которой обращение к первой, например: Procedure A(i: Byte); Begin . B(i); . end; procedure B(j: Byte); . begin . A(j); . end; Если строго следовать правилу, согласно которому каждый идентификатор перед употреблением должен быть описан, то такую программную конструкцию использовать нельзя. Для того, чтобы такого рода вызовы стали возможны, вводится опережающее описание: Procedure B(j: Byte); forward; Procedure A(i: Byte); Begin . B(i); . end; procedure B; begin . A(j); . end; Как видим, опережающее описание заключается в том, что объявляется лишь заголовок процедуры В, а её тело заменяется стандартной директивой FORWARD. Теперь в процедуре А можно использовать обращение к процедуре В – ведь она уже описана, точнее, известны её формальные параметры, и компилятор может правильным образом организовать её вызов. Обратим внимание: тело процедуры В начинается заголовком, в котором уже не указываются описанные ранее формальные параметры. 1.4. Рекурсивные структуры 1.4.1. Список Список относится к особой группе структур - это так на­зы­ва­е­мые ре­курсивные структуры. Приведем рекурсивное определение списка: Списком называется со­­во­купность связанных элементов, из которых один является осо­бым элементом (первым, "головой"), а все остальные образуют спи­сок. Рекурсивные структуры в программировании замечательны тем, что мно­гие операции по их обработке можно эффективно реализовать с использованием рекурсивных процедур, которые отличаются боль­шой ла­коничностью и наглядностью. В качестве примера приведём про­це­ду­ру проверки, является ли Н1 подсписком списка Н: TYPE Указатель = POINTER TO Элемент; Элемент = RECORD INFO : Инфоpмация; LINK : Указатель; END PROCEDURE Проверка (Н,Н1 : Указатель) : BOOLEAN; BEGIN IF H # NIL THEN RETURN (Н = Н1) OR Проверка (Н^.LINK, Н1) ELSE RETURN (Н = Н1) END END Проверка. Проверка (H # NIL) в этом примере нужна только для того, что­бы предотвратить попытку интерпретировать пустую ссылку как эле­мент списка при вызове Проверка (H^.LINK, H1). Ситуация (H=H1=NIL) рассматривается как положительный результат проверки. 1.4.2. Набор Другим примером рекурсивной структуры является структура на­бора, которая определяется следующим образом: Набором называется совокупность связанных элементов, каждый из которых может быть ли­бо атомом, либо набором. Атом определяет "неделимый" элемент на­бора, предназначенный для хранения элементарной порции ин­фор­ма­ции. Реализация наборов основана на использовании разнородных списков. Например, ниже приведена (см. рис. 1) одна из возможных структур на­бо­ров. В этой структуре H1 - набор из четырех элементов (a, b, H2, c), из них H2 - набор, остальные - атомы. H2 состоит в свою очередь из тpех элементов - атома c и двух наборов H3 и H4, причем набор H3 - пуст (не содержит элементов), а H4 содержит два атома (d и f). H2

а

b


с H1 H3 H4



с

f
*

* Рис. 1 Элементы H2, H3, H4 определяют "головы" новых наборов и од­но­временно являются членами наборов "верхнего уровня" - при этом структура набора оказывается адекватной для реализации дина­ми­чес­ких "вложенных" понятий предметной области. Например, в ассо­ци­ацию H1-"Акционеры" могут входить как отдельные частные ли­ца, так и коллективы - организации, которые являются ассо­циа­ци­я­ми собственных акционеров. Элементы H2, H3, H4 на приведенной иллюстрации участвуют в двух связях - горизонтальной (связь между членами одного набора) и вертикальной (связь с членами "своего собственного" набора). Эта терминология часто используется для организации так назы­вае­мых ортогональных списков, моделирующих структуры динамически изме­няющегося плоского "игрового поля": "разреженных" матриц, "кроссвордов", цепей "домино" и т.д. Понятие "игрового поля", ра­­зу­меется, не означает, что ортогональные списки используются лишь в игровых задачах. 1.4.3. Дерево Еще один пример рекурсивной структуры, широко использующейся в программировании - структура дерева. Деревом называется сово­купность связанных элементов - вершин дерева, включающая в себя один особый элемент - корень, при этом все остальные эле­мен­ты образуют поддеревья. Наиболее широко используется струк­ту­ра бинарного дерева, все множество вершин которого делится (по отношению к корню) на два подмножества - два поддерева (левое и правое). Любая вершина бинарного дерева реализуется на связанной памяти элементом с двумя связями: с левым поддеревом и с правым. К


* Информационное поле Связь с левым потомком

* Связь с правым потомком

NIL


NIL

NIL
Л1 Л2 Л3
NIL

NIL

NIL Рис. 2 На этой иллюстрации изображена структура бинарного дерева на связанной памяти, здесь К – корень; Л1,Л2,Л3 – "листья" – вер­ши­ны с "пустыми" связями ("не выросшими" поддеревьями). Заметим, что в этой интерпретации дерево реализуется на одно­род­ных списках (в отличие от набора). Особое положение корня оп­ре­деляется единственным свойством – отсутствием вершин-предков, любой лист дерева характеризуется полным отсутствием вершин-потомков. Поскольку любая вершина в связанной структуре дерева от­крывает доступ только "вниз" (только к своим поддеревьям), она может интерпретироваться как корень соответствующего поддерева. В этом смысле лист является корнем "не выросшего" дерева и оп­ре­де­ляет его своеобразную "точку роста". Включение в дерево новой вершины и удаление старой не должно нарушать общего отношения по­ряд­ка на множестве вершин.
Примером такого отношения может служить отношение "больше- меньше", определяющее структуру бинарного дихотомического дере­ва. В таком дереве все вершины любого правого поддерева имеют значение инфор­маци­он­ного поля большее, чем значение такого же по­ля у корня, а веp­ши­ны соответствующего левого поддерева – мень­шее. Например, конструирование дихото­ми­ческого дерева по пос­ледовательности целых чисел 30, 70, 80, 21, 25, 17, 4, начиная с 30, должно приводить к созданию следующей структуры:
Рис. 3 Нетрудно заметить, что процесс конструирования такого дерева про­исходит сверху вниз, начиная с корня, путем последовательного сравнения числовых значений, размещаемых в вершинах, с целью определения места размещения соответствующей вершины в структуре дерева. Любая модификация дихотомического дерева (удаление вершины, вставка новой веpшины) не должна нарушать дихотомической структуры в целом. В об­щем случае трансформация произвольной информационной строки (пос­ледо­ва­тель­ности объектов) в структуру дерева и об­рат­но основана на использовании глубоких структурных межобъектных отно­шений в исходной строке. Такая трансформация позволяет наг­ляд­­но представить подобные отношения в форме дерева. В программировании дерево во многом рассматривается как формальная структура, наполняемая различным семантическим содержанием. Такой под­ход позволяет формально реализовать многие преобразования дан­ных на основе унифицированных процедур обхода деревьев. Нап­ри­мер, в теории трансляции широко используется понятие Поль­ской инверсной записи (ПОЛИЗ) – особой системы представления математических выражений символьными последовательностями. Так, например, выражение " a + b * c " будет представлено в ПОЛИЗЕ строкой " a b c * + ". Если представить исходное выражение в естественной иерархической форме бинарного дерева :

+ Рис. 4 то его восходящий обход (пунктир на рис. 4) приведет к стро­ке " a b c * + ", определяющей "польский" эквивалент исходной стро­ки. Формула восходящего обхода "Левый–Правый–Корень" (ЛПК) определяет правило обхода бинарного дерева: восходящий об­ход связан с обходом его левого поддерева, затем правого под­де­ре­ва, затем корня. Поскольку каждая вершина дерева может интер­пре­­тироваться как корень "вырастающего из нее" поддерева, это пра­­вило применяется рекурсивно к каждой вершине обходимого де­ре­ва. Правило ЛКП (Левый–Корень–Правый) определяет так на­зы­ва­е­­мый смешанный обход, правило КЛП – нисходящий обход и т.д. Нет­ру­дно заметить, что смешанный обход дерева дихотомии по пра­вилу ЛКП приведет к формированию строки чисел (хранящихся в вершинах этого дерева), упорядоченной по возрастанию, а такой же обход по правилу ПКЛ – к формированию строки, упорядоченной по убыванию соответствующих чисел. Таким образом, между структурой дерева, от­ношением порядка на множестве информационных компонент его вер­шин и видом обхода существует глубокая связь, определяемая ре­­курсивной природой структуры дерева. Рекурсивные процедуры об­хо­да бинарных деревьев пишутся прямо по формуле обхода с учетом спе­цификации представления вершин дерева. Например, ниже при­ве­де­на процедура смешанного обхода бинарного дерева дихотомии, ре­а­лизующего формулу ЛКП. TYPE Вершина = POINTER TO Элемент ; Элемент = RECORD Info : CARDINAL ; LLink,RLink : Вершина END ; PROCEDURE Смеш_Обход (K : Вершина); BEGIN IF K # NIL THEN Смеш_Обход (K^.LLink); (* Обход левого поддерева *) WriteCard (K^.Info); (* Обработка корня *) Смеш_Обход (K^.RLink); (* Обход правого поддерева *) END END Смеш_Обход. В традиционном программировании рекурсия часто рас­сма­три­ва­ет­ся как некоторый заменитель итерации. Причем в качестве примеров рас­сматривается вычисление рекуррентных последовательностей, ко­то­рые могут быть легко сформированы и обычными итераторами (цик­ла­ми WHILE, REPEAT и т.п.). Природа рекурсии значительно глубже, чем механизм итерации, поэтому ее использование практически не име­ет альтернатив в виде итераторов только тогда, когда решение за­дач проводится на рекурсивных структурах. Попробуйте написать про­цедуру Смеш-Обход без использования рекурсии, только на ос­но­ве циклов и, если Вам это удастся, сравните ее с приведенным вы­ше вариантом рекурсивной процедуры по наглядности, лаконичности, вы­разительности. 1.5. Примеры решения задач с помощью рекурсии
1.5.1. “Ханойская башня” При написании рекурсивных программ, следует помнить, что при рекурсивном вызове процедурой самой себя или другой процедуры следует соблюдать определённые “правила предосторожности”. Рекомендуется компилировать программу с директивой {$S+}. Эта директива включает проверку переполнения стека (области памяти, в которой хранится состояние вызывающей подпрограммы). Если в процессе выполнения программы происходит переполнение стека, вызов процедуры или функции, откомпилированной с опцией {$S+}, приводит к завершению работы программы, а на дисплей выдаётся сообщение об ошибке. Полезно также использовать директиву {$R+}, включающую проверку диапазона переменных. В начале каждой процедуры (функции), вызываемой рекурсивно, можно разместить строку if keypressed then Halt. В этом случае при зависании программы вместо перезагрузки будет достаточно нажать любую клавишу. Количество рекурсивных вызовов называется глубиной рекурсии. Глубина рекурсии должна быть конечной. Позаботиться об этом должен программист, выбирающий или разрабатывающий рекурсивный алгоритм. Рассмотрим пример. Правила головоломки “Ханойская башня” таковы. Имеется доска с тремя колышками. На первом из них нанизано несколько дисков убывающего диаметра (самый большой находится внизу – рис. 5).
Требуется расположить диски в том же порядке на третьем колышке, причём диски разрешается перекладывать только по одному, а класть большой диск на меньший нельзя. Один колышек используется в качестве вспомогательного. Ответим на вопрос – сколько перемещений дисков следует выполнить?
Алгоритм решения головоломки следующий: 1. Переместить верхние n-1 дисков на второй колышек. 2. Нижний диск с первого колышка переместить на третий. 3. Переместить n-1 дисков на третий колышек, используя первый в качестве вспомогательного. 4. Повторять, пока на третьем колышке не будет сформирована новая пирамида. Исходная задача сводится, таким образом, к двум задачам о переносе n-1 диска и одной задаче о переносе одного диска. Для n-1 требуется одно перемещение. Исходный текст программы для вычисления количества ходов приведён ниже (Листинг 1). Количество ходов здесь может быть вычислено как с применением рекурсии (функция hanoi1), так и без неё (функция hanoi2). В первом случае исходный текст функции короче. 1 2 3 Рис. 5. Головоломка “Ханойская башня” Листинг 1. Программа “Ханойская башня” {$S+} program hanoi_moves; function hanoi1(n: Word): LongInt; begin if n=1 then hanoi1:=1 else hanoi1:=2*hanoi1(n-1)+1; end; function hanoi2(n: Word): LongInt; var j: LongInt; k: Word; begin if n=1 then hanoi2:=1 else begin j:=1; for k:=2 to n do j:=2*j+1; hanoi2:=j; end; end; writeln(hanoi1(20)); writeln(hanoi2(20)); end. 1.5.2. Двумерное множество Кантора Ещё один пример использования рекурсии приводится в программе Cantor (Листинг 2), которая строит двумерное множество Кантора. Множество строится следующим образом. Имеется квадрат, внутренняя часть которого закрашена каким-то цветом. Этот квадрат делится на 16 равных частей (тоже квадратных). Затем удаляются 4 средних квадрата, причём изображения их границ остаются. Далее процедура повторяется для каждого оставшегося квадрата. Алгоритм построения квадратного множества Кантора следующий: 1. Построить квадрат размером L. 2. Вырезать расположенный в центре квадрат размером L/2. 3. Разделить исходный квадрат на четыре равные части размером L/2. 4. Для каждого из четырёх квадратов повторить шаги 2 и 3. В результате получается самоподобное множество – фрактал. В программе Cantor сохраняется изображение границы вырезанного квадрата, а построение множества идёт не от большего квадрата к меньшим, а наоборот. Процедура SetWriteMode модуля Graph устанавливает режим вывода линии. Режим задаётся с помощью логической операции. В нашем примере используется операция “исключающее ИЛИ” (ей соответствует константа xorput), поэтому изображение линии комбинируется с изображением, уже выведенным на экран. Листинг 2. Программа “Двумерное множество Кантора” {$S+} program Cantor; uses Crt, Graph, graphs; var ch: Char; const min_size=1; procedure draw(x,y: integer; size: Word); var s: Word; begin if size>min_size then begin s:=size div 2; draw(x-size, y+size, s); draw(x-size, y-size, s); draw(x+size, y+size, s); draw(x+size, y-size, s); end; rectangle(x-size, y-size, x+size, y+size,); bar(x-size+1, y-size+1, x+size-1, y+size-1); end; begin open_graph; SetFillStyle(solidfill, black); SetColor(White); draw(GetMaxX div 2, GetMaxY div 2, GetMaxY div 4); OutTextXY(265, 235, ‘Press ’); ch:=ReadKey; SetColor(Black); SetWriteMode(xorput); draw(getmaxx div 2, getmaxy div 2, getmaxy div 4); SetColor(White); OutTextXY(265, 235, ‘Press ’); ch:=ReadKey; close_graph; end. 1.5.3. “Индийский алгоритм” возведения в степень Этот алгоритм вычисления натуральной n-й (n>1) степени целого числа х выглядит совсем просто: § при n=1 xn=x; § при n>1 xn= xn mod2(xn div2)2. Основная цель этого алгоритма – сократить количество умножений при возведении в степень. Например, по этому алгоритму х5=х*(х2)2, т.е. достаточно трёх умножений вместо четырёх: х*х*х*х*х. Одно умножение экономится за счёт того, что х2 хранится как промежуточное значение и умножается само на себя. Точно так же х10=1*(х5)2=(х5)2, что требует лишь четырёх умножений (три из них для вычисления х5) вместо девяти “лобовых”. Но здесь придётся хранить сначала х2, а потом х5. Очевидно, что вычисление хn сводится к вычислению хn div2, запоминанию результата, возведению в квадрат и умножению его на х при нечётном n. Итак, вычисление xn описывается рекурсивной функцией: function pow(x,n:integer):integer; var t:integer; begin if odd(n) then t:=x else t:=1; if n=1 then pow:=x else pow:=t*sqr(pow(x,n div 2)) end; Как видим, промежуточные сомножители хранятся в локальной памяти процессов выполнения вызовов функции, а именно, в переменных, поставленных в соответствие её имени. Теперь опишем зависимость глубины рекурсии вызовов функции от значения аргумента. В каждом следующем вложенном вызове значение аргумента n меньше предыдущего значения, по крайней мере, вдвое. Поскольку при n=1 происходит возвращение из вызова, то таких уменьшений значения аргумента n не может быть больше чем log2n. Следовательно, глубина рекурсии вызова с аргументом n не превышает log2n.
Такую глубину можно считать хорошим свойством алгоритма. При каждом выполнении вызова происходит не более одного деления, возведения в квадрат и умножения, поэтому общее количество арифметических операций не больше 3log2n. При больших значениях n это существенно меньше “лобовых” n-1 умножений. Например, при n=1000 это примерно 30.
Отметим, что при некоторых значениях n приведённый алгоритм не даёт наименьшего количества умножений, необходимых для вычисления n-й степени. Например, при n=15 по этому алгоритму необходимо выполнить 6 умножений, хотя можно с помощью 3-х умножений вычислить х5, после чего помножить его на себя дважды (всего 5 умножений). Однако написать алгоритм, который задаёт вычисление произвольной степени с минимальным количеством умножений, – не совсем простая задача. Построим нерекурсивный аналог приведённого алгоритма. Представим вычисление по рекурсивному алгоритму в таком виде: х13=(х6)2*х1=((х3)2*х0)2*х1=(((х1)2*х1)2*х0)2*х1 Этому соответствует следующая обработка вычисляемых показателей степеней: 13=6*2+1=(3*2+0)*2+1=((1*2+1)*2+0)*2+1 Как видим, вычислению степеней соответствует вычисление значения 13, представленного полиномом относительно 2. Коэффициентами его являются цифры двоичного разложения числа 13. Нетрудно убедится, что вычислению степени с произвольным показателем n точно так же соответствует вычисление числа n, представленного двоичным разложением. Причём это разложение-полином записано по схеме Горнера. Раскроем в нём скобки: 1*23+1*22+0*21+1*20 Коэффициент при 20, 21, 22 и т.д. – это последовательные остатки от деления на 2 чисел: n, n div 2, (n div 2) div 2 и т.д. причём остатку 1 соответствует в рекурсивном алгоритме присваивание t:=x, а 0 – присваивание t:=1. Таким образом, двоичное разложение, например, числа 13 по степеням двойки соответствует такому представлению х13: х2^3*x2^2*1*x2^0 Итак, достаточно вычислять степени: x2^0= x, x2^1= x2, x2^2= (x2)2, x2^3= (x2^2)2 и т.д. и соответствующие им остатки от деления на 2 показателей: n, n div 2, (n div 2) div 2, ((n div 2) div 2) div 2 и т.д. накапливая в произведении лишь те степени двойки, которые соответствуют остаткам 1. В следующем алгоритме произведение степеней накапливается в переменной t, а степени двойки – в переменной х: function pow(x,n:integer):integer; var t:integer; notfin:boolean; begin t:=1; notfin:=true; while notfin do begin if odd(n) then t:=t*x; n:=n div 2; if n>0 then x:=x*x else notfin:=false end; pow:=t end. 1.5.4. Вычисление факториала Программируя формулы из комбинаторной математики, часто приходится использовать рекурсию. В качестве примера применения рекурсии в комбинаторике приведём, рассмотренную ранее, программу вычисления факториала (Листинг 3). Программа вводит с клавиатуры целое число N и выводит на экран значение N!, которое вычисляется с помощью рекурсивной функции FAC. Для выхода из программы необходимо либо ввести достаточно большое целое число, чтобы вызвать переполнение при умножении чисел с плавающей запятой, либо нажать Ctrl-Z и Enter. При выполнении правильно организованной рекурсивной подпрограммы осуществляется многократный переход от некоторого текущего уровня организации алгоритма к нижнему уровню последовательно до тех пор, пока, наконец, не будет получено тривиальное решение поставленной задачи. В приведённой ниже программе решение при N=0 тривиально и используется для остановки рекурсии. Листинг 3. Программа вычисления факториала. ProgramFactorial; {$S+} {Включаем контроль переполнения стека} var n: Integer; function Fac (n: Integer): Real; {Рекурсивная функция, вычисляющая n!} begin if nthen writeln (‘Ошибка в задании N’) else if n=0 then Fac:=1 else Fac:=n*Fac(n-1) end {Fac}; {----------} begin {main} repeat ReadLn(n); WriteLn(‘n! = ’,Fac(n)) untilEOF end{main}. Рекурсивная форма организации алгоритма обычно выглядит изящнее итерационной и даёт более компактный текст программы, но при выполнении, как правило, медленнее и может вызвать переполнение стека (при каждом входе в программу её локальные переменные размещаются в особым образом организованной области памяти, называемой программным стеком). Переполнение стека особенно ощутимо сказывается при работе с сопроцессором: если программа использует арифметический сопроцессор, результат любой вещественной функции возвращается через аппаратный стек сопроцессора, рассчитанный всего на 8 уровней. Если, например, попытаться заменить тип REAL функции FAC (см. листинг 3) на EXTENDED, программа перестанет работать уже при N=8. Чтобы избежать переполнения стека сопроцессора, следует размещать промежуточные результаты во вспомогательной переменной. Вот правильный вариант для работы с типом EXTENDED: ProgramFactorial; {$S+,N+,E+} {Включаем контроль стека и работу сопроцессора} var n: Integer; function Fac (n: Integer): extended; varF: extended; {Буферная переменная для разгрузки стека сопроцессора} {Рекурсивная функция, вычисляющая n!} begin{Fac} if nthen writeln (‘Ошибка в задании N’) else if n=0 then Fac:=1 else begin F:=Fac(n-1); Fac:=F*n end; end {Fac}; {----------} begin {main} repeat ReadLn(n); WriteLn(‘n! = ’,Fac(n)) untilEOF end{main}. Архитектура стека непосредственно поддерживает рекурсию, поскольку каждый вызов процедуры автоматически размещает новую копию локальных переменных. Например, при каждом рекурсивном вызове функции факториала требуется одно слово памяти для параметра и одно слово памяти для адреса возврата. То, что издержки на рекурсию больше, чем на итерацию, связано с дополнительными командами, затраченными на вход в процедуру и выход из неё. Некоторые компиляторы пытаются выполнить оптимизацию, называемую оптимизацией хвостовой рекурсии (tail-recursion) или оптимизацией последнего вызова (last-call). Если единственный рекурсивный вызов в процедуре – последний оператор процедуры, то можно автоматически перевести рекурсию в итерацию. 1.5.5. Числа Фибоначчи С идейной точки зрения рекурсия аналогична методу математической индукции. Базе индукции соответствует база рекурсии. Предположению индукции соответствует предположение о том, что нужная процедура уже написана. Наконец, шагу индукции соответствует вызов создаваемой рекурсивной процедуры. В любой рекурсии необходимо предусмотреть условие завершения процесса, т.е. когда вызова больше не происходит.
Рассмотрим ещё один пример использования рекурсии – вычисление N-ого по счёту числа Фибоначчи. Числа Фибоначчи составляют последовательность, очередной элемент которой вычисляется по двум предыдущим значениям: F­n=Fn-1 + Fn-2 . Нулевое и первое значения должны быть заданы, их значения равны единице. Последовательности такого рода применяются, например, в программах генераторах случайных чисел. Вычисление 20-ого числа Фибоначчи реализовано в программе Fibonacci (Листинг 4). Впрочем, номер числа можно изменить, задав в описании константы другое значение.
Листинг 4. Программа вычисления 20-ого числа Фибоначчи. program Fibonacci; uses Crt; const n=20; function F(n: word): longint; begin if keypressed then halt; if (n=0) or (n=1) then F:=1 else F:=F(n-1)+F(n-2); {рекурсивный вызов} end; function G(n: word): longint; var x,y,t: longint; k: word; begin x:=1; y:=1; for k:=2 to n do begin t:=y; y:=x+y; x:=t; end; G:=y; end; begin clrscr; textcolor(lightgray +128); write(‘Считаю .’); textcolor(lightgray); writeln(‘—Ждите ответа--’); writeln; writeln(‘Рекурсивный алгоритм : F(‘, n, ’)= ’, F(n)); writeln; writeln(‘Итерационный алгоритм : F(‘, n, ’)= ’, G(n)); gotoxy(1,1); clreol; gotoxy(1,7); write(‘Нажмите ’); end. В этой программе реализованы два метода решения задачи вычисления числа Фибоначчи. Один назовём итерационным методом – он заключается в прямом программировании итерационной формулы для чисел Фибоначчи. В функции G для этого используются три вспомогательные переменные типа LongInt. Решение с использованием рекурсивных вызовов запрограммировано с помощью функции F. Оператор, вычисляющий её значение, два раза вызывает саму эту функцию. Текст рекурсивной функции короче, лаконичнее итерационной функции. Процедура ClrEol из модуля Crt удаляет все символы строки от текущего положения курсора до её конца. 2. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ ЭВМ И ИХ ОБРАБОТКА СИМВОЛ КОД РАЗМЕР ДЕСЯТИЧНЫЙ ДВОИЧНЫЙ В 130 10000010 1 байт о 174 10101110 1 байт р 224 11100000 1 байт о 174 10101110 1 байт н 173 10101101 1 байт и 168 10101000 1 байт н 173 10101101 1 байт Пробел 32 00100000 1 байт A 128 10000000 1 байт л 171 10101011 1 байт е 165 10100101 1 байт к 170 10101010 1 байт с 225 11100001 1 байт а 160 10100000 1 байт н 173 10101101 1 байт д 164 10100100 1 байт р 224 11100000 1 байт Пробел 32 00100000 1 байт 1 49 00110001 1 байт 5 53 00110101 1 байт . 46 00101110 1 байт 0 48 00110000 1 байт 4 52 00110100 1 байт . 46 00101110 1 байт 1 49 00110001 1 байт 9 57 00111001 1 байт 8 56 00111000 1 байт 5 53 00110101 1 байт Личные данные займут в памяти ЭВМ 28 байтов. Сложение числа и месяца рождения в двоичном формате: +1111 0100 10011 (10011)2=(19)10 Вычитание месяца из числа рождения в двоичном формате: _1111 0100 1011 (1011)2=(11)10 3. РАЗРАБОТКА ПРОГРАММ 3.1. Программа роста банковского вклада по месяцам Программа спрашивает с защитой от неверного введения данных следующую информацию: § начальный размер вклада (1000 .10000); § размер периодических платежей (от 1% до 10% от начального вклада); § размер процентной ставки вклада (0.5% .4% в месяц).
Затем выводит во внешний файл таблицу роста вклада по месяцам, в которой включён дополнительный столбец роста вклада с предположением отсутствия периодических платежей. program Bank; var nach_vn, summa_bez_plat, prots_st, plat: real; i: integer;
rez: text; label 1,2,3; begin assign(rez,'rez.txt'); rewrite(rez); writeln('***************************************************'); 1: writeln('***************************************************'); writeln('vvedite summu nachalnogo vklada'); readln(nach_vn); if nach_vnthen begin writeln('neverno vvedeno znachenie'); goto 1; end; if nach_vn>10000 then begin writeln('neverno vvedeno znachenie'); goto 1; end; 2: writeln('***************************************************'); writeln('vvedite normu protsentnoy stavki'); readln(prots_st); if prots_stthen begin writeln('neverno vvedeno znachenie'); goto 2; end; if prots_st>4 then begin writeln('neverno vvedeno znachenie'); goto 2; end; 3: writeln('***************************************************'); writeln('vvedite protsent pereodicheskih platezhey'); readln(plat); if platthen begin writeln('neverno vvedeno znachenie'); goto 3; end; if plat>10 then begin writeln('neverno vvedeno znachenie'); goto 3; end; writeln(rez,'*******************************'); plat:=nach_vn/100*plat; i:=0; writeln(rez,'| mes |na schetu|bez platezhey '); writeln(rez,'----------------------------'); writeln(rez,'| ', i , ' | ', nach_vn:6:2, ' | '); writeln(rez,'----------------------------'); i:=1; summa_bez_plat:=nach_vn; for i:=1 to 18 do begin summa_bez_plat:=summa_bez_plat+nach_vn/100*prots_st; nach_vn:=nach_vn+nach_vn*0.01*prots_st-plat; if ithen writeln(rez,'| ',i, ' | ', nach_vn:6:2, ' | ', summa_bez_plat:6:2) else writeln(rez,'| ',i, ' | ', nach_vn:5:2, ' | ', summa_bez_plat:6:2); writeln(rez,'----------------------------'); end; readln; end. 3.2. Блок-схема к программе _+ 10000?"> + – + _ + _ 4?"> + – 10?"> – +
+ –
ВЫВОД Итак, подведём итоги. Мы научились разрабатывать программы в среде Турбо Паскаль, строить к ним блок-схемы и представлять данные в памяти ЭВМ. Также мы познакомились с “маленьким чудом” в программировании – рекурсией и рекурсивными алгоритмами. Так почему же используют рекурсию? Дело в том, что многие алгоритмы можно изящно и надёжно написать с помощью рекурсии, в то время как итерационное решение трудно запрограммировать и легко сделать ошибки. Примером тому служат алгоритм быстрой сортировки и алгоритмы обработки древовидных структур данных. Языковые понятия опираются исключительно на рекурсию, а не на итерацию. Даже для обычных языков типа С и Паскаль рекурсию, вероятно, следует использовать более часто, чем это делается, из-за краткости и ясности программ, которые получаются в результате. Рекурсия отражает черту абстрактного мышления, проявляющуюся в самых различных приложениях (в математике, синтаксическом анализе и трансляции, древовидной сортировке и обработке данных с динамической структурой, шахматных задачах и т.д.). Пользование ею избавляет от необходимости последовательного (и часто, утомительного) описания процессов. Таким образом, рекурсия не является чем-то нарочито усложнённым и предназначенным для касты посвящённых, а представляет собой ещё одно средство программирования, которым можно пользоваться удачно или злоупотреблять, как и всяким другим. Урок таков: следует избегать рекурсивного решения там, где есть очевидное итеративное решение, и использовать его тогда, когда без рекурсии просто не обойтись. “Итерация свойственна человеку, а рекурсия – богу” (Л. Питер Дойч). СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ: 1. Бен-Ари М. Языки программирования. Практический сравнительный анализ: Пер. с англ. – М.: Мир, 2000. – 366 с., ил. 2. Зуев Е.А. Turbo Pascal. Практическое программирование. – М.: Приор, 1997. – 336с. 3. Кнут Д. Искусство программирования, том 1. Основные алгоритмы, 3-е изд.: Пер. с англ. – М.: Издательский дом "Вильямс", 2000. – 720 с. 4. Немнюгин С.А. Turbo Pascal. – СПб.: Издательство “Питер”, 2000. – 496 с., ил. 5. Немнюгин С.А. Turbo Pascal: практикум – СПб.: Питер, 2001. – 256 с., ил. 6. Рубенкинг Н.Дж. Турбо Паскаль для Windows: в 2-х томах. Т.1. Пер. с англ. - М.: Мир, 1993. – 536 с., ил. 7. Рубенкинг Н.Дж. Турбо Паскаль для Windows: в 2-х томах. Т.2. Пер. с англ. - М.: Мир, 1993. – 536 с., ил. 8. Ставровский А.Б. Турбо Паскаль 7.0. Учебник. – К.: Издательская группа BHV, 2000. – 400 с. 9. Фаронов В.В. Турбо Паскаль 7.0. Начальный курс. Учебное пособие. Издание 7-е, переработанное. – М.: «Нолидж», 2000. – 576 с., ил. 10. Фаронов В.В. Турбо Паскаль 7.0. Практика программирования. Учебное пособие. Издание 7-е, переработанное. – М.: «Нолидж», 2000, - 416 с., ил. 11. Шелест В.Д. Программирование. – СПб.: БХВ – Петербург, 2001. – 592 с., ил.