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

ГУМАНИТАРНЫЙ УНИВЕРСИТЕТ
УЗапорожский институт государственного и муниципального управленияФ
ФАКУЛЬТЕТ УПРАВЛЕНИЯ
КАФЕДРА ПРОГРАММИРОВАНИЯ И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовой работе по дисциплине:
УПрограммирование и алгоритмические языкиФ
на тему: УРекурсивные алгоритмыФ
Подготовил студент группы ДИ-102 ________________ Воронин А.А.
(подпись)
Научный руководитель доцент, к. ф.-м. н. ________________ Швец Ю.А.
(подпись)
Запорожье
2003
КАФЕДРА ПРОГРАММИРОВАНИЯ И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
ЗАДАНИЕ
на выполнение курсовой работы
по дисциплине УПрограммирование и алгоритмические языкиФ
студенту группы ДИ-102 Воронину А.А.
Тема работы: Рекурсивные алгоритмы.
Задание: 1) Подготовить литературное рассмотрение темы работы;
2) Разработать и привести фрагмент оперативной памяти условной ЭВМ, в
которой указаны Ваши личные данные:
Ц фамилия;
Ц имя;
Ц число рождения;
Ц месяц рождения (в цифровом виде);
Ц год рождения.
Определите, какое количество памяти (в байтах) займут эти данные. Произвести
в двоичной форме сложение и вычитание столбиком цифр, которые соответствуют
вашим дню и месяцу рождения;
3) Составить программу в среде Turbo Pascal. Привести общую схему
решения задачи, алгоритмы наиболее важных блоков, а также полный текст
программы. Текст программы должен сопровождаться комментариями. Программа
должна иметь дружелюбный для пользователя интерфейс.
Задание выдал к. ф.-м. н. Швец Ю.А.
___________________
(подпись, дата)
Задание получил студент группы ДИ-102 Воронин А.А. ___________________
(подпись, дата)

РЕФЕРАТ
Пояснительная записка имеет объём 39 страниц, содержит: 6 рисунков, 2
таблицы, 11 источников.
Объектом исследования является программирование в среде Турбо Паскаль,
представление данных в памяти ЭВМ, а также изучение рекурсивных алгоритмов и их
использование.
Цель работы: исследовать рекурсивные алгоритмы, рассмотреть примеры их
применения.
Методы исследования:
Ц описательный
Ц метод практического сравнительного анализа
Ц метод системного анализа
Научная новизна состоит в попытке дать чёткое определение рекурсии, а
также исследовать рекурсивные алгоритмы в среде Турбо Паскаль.
В курсовой работе: рассмотрена рекурсия, её определение, алгоритмы и примеры;
решена задача представления данных в памяти ЭВМ; разработана программа роста
банковского вклада по месяцам.
ПРОГРАММИРОВАНИЕ, РЕКУРСИЯ, РЕКУРСИВНЫЕ АЛГОРИТМЫ, ТУРБО ПАСКАЛЬ
СОДЕРЖАНИЕ
Условные обозначения, символы, нестандартные сокращения......................5

Введение......................................................................................................................6
1. Рекурсивные
алгоритмы......................................................................................7
1.1. Рекурсивные определения
...............................................................................7
1.2. Рекурсивные подпрограммы
.........................................................................10
1.3. Косвенная рекурсия и опережающее описание
...........................................13
1.4. Рекурсивные структуры
.................................................................................15
1.4.1. Список
....................................................................................................15
1.4.2. Набор
.....................................................................................................16
1.4.3. Дерево
....................................................................................................17
1.5. Примеры решения задач с помощью рекурсии
...........................................21
1.5.1. УХанойская башняФ
..............................................................................21
1.5.2. Двумерное множество Кантора
...........................................................23
1.5.3. УИндийский алгоритмФ возведения в степень
...................................25
1.5.4. Вычисление факториала
......................................................................28
1.5.5. Числа Фибоначчи
.................................................................................30
2. Представление данных в памяти
ЭВМ...........................................................33
3. Разработка программы.....................................................34
3.1. Программа роста банковского вклада по месяцам
......................................34
3.2. Блок-схема к программе
................................................................................37

Вывод.........................................................................................................................38
Список использованных
источников..................................................................39

УСЛОВНЫЕ ОБОЗНАЧЕНИЯ, СИМВОЛЫ, НЕСТАНДАРТНЫЕ СОКРАЩЕНИЯ
ПСЗ Ц полная скобочная запись
НОД Ц наибольший общий делитель
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;
з если а mod b=0, то НОД(a, b)=b;
з если а mod b>0, то НОД(a, b)= НОД(b, а mod b).
Этому определению соответствует следующая рекурсивная функция вычисления НОД:
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 при т<1 или n=0, или n
=m; в противном случае C(m, n)=
C(mн-1, n-1)+C(m-1, n).
В соответствии с этим равенством напишем рекурсивную функцию вычисления
биномиального коэффициента C(m, n) по m, n
, где 0<n<m:
function C(m, n:integer):integer;
begin
if (m<=1) or (n=0) or (n=m) then C:=1
else C:=C(m-1, n-1)+C(m-1, n)
end;
Как видим, каждый вызов, в котором значения аргументов m>1, 0<n
<m, порождает два вложенных вызова. В результате происходит повторное
вычисление одних и тех же величин. Например, выполнение вызова с аргументом
(5,2) ведёт к тому, что вызов с аргументами (3,1) выполняется дважды, вызовы с
аргументами (2,1), (1,0) и (1,1) Ц трижды, а общее количество вложенных вызовов
достигает 18.
Нетрудно понять, что чем больше т и чем ближе n к т/2,
тем большим будет общее количество вложенных вызовов. Мы не будем точно
определять его зависимость от аргументов. Скажем лишь, что при n=m
div 2 или n=m div 2+1 оно больше, чем 2^т^/2. Например, при т=60 это 2³⁰, или примерно 10⁹
. Если даже предположить, что за секунду можно выполнить 10⁶ вызовов,
то нужно больше 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).

а b с
H1

H3 H4

* *

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

*
Информационное поле

Связь с левым потомком

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

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 <Space>Т);
ch:=ReadKey;
SetColor(Black);
SetWriteMode(xorput);
draw(getmaxx div 2, getmaxy div 2, getmaxy div 4);
SetColor(White);
OutTextXY(265, 235, СPress <Space>Т);
ch:=ReadKey;
close_graph;
end.
1.5.3. УИндийский алгоритмФ возведения в степень
Этот алгоритм вычисления натуральной n-й (n>1) степени целого
числа х выглядит совсем просто:
з при n=1 xⁿ=x;
з при n>1 xⁿ= xⁿ ^mod ²(xⁿ ^div ²)².
Основная цель этого алгоритма Ц сократить количество умножений при возведении в
степень. Например, по этому алгоритму х⁵=х*(х²)², т.е. достаточно трёх умножений вместо четырёх: х*
х*х*х*х. Одно умножение экономится за счёт того, что
х² хранится как промежуточное значение и умножается само на себя.
Точно так же х¹⁰=1*(х⁵)²=(х⁵)², что требует лишь четырёх умножений (три из них для
вычисления х⁵) вместо девяти УлобовыхФ. Но здесь придётся
хранить сначала х², а потом х⁵.
Очевидно, что вычисление хⁿ сводится к вычислению хⁿ ^div ², запоминанию результата, возведению в квадрат и
умножению его на х при нечётном n. Итак, вычисление xⁿ
описывается рекурсивной функцией:
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
не может быть больше чем log₂n. Следовательно, глубина
рекурсии вызова с аргументом n не превышает log₂n
.
Такую глубину можно считать хорошим свойством алгоритма. При каждом выполнении
вызова происходит не более одного деления, возведения в квадрат и умножения,
поэтому общее количество арифметических операций не больше 3log₂
n. При больших значениях n это существенно меньше УлобовыхФ n
-1 умножений. Например, при n=1000 это примерно 30.
Отметим, что при некоторых значениях n приведённый алгоритм не даёт
наименьшего количества умножений, необходимых для вычисления n-й
степени. Например, при n=15 по этому алгоритму необходимо выполнить 6
умножений, хотя можно с помощью 3-х умножений вычислить х⁵,
после чего помножить его на себя дважды (всего 5 умножений). Однако написать
алгоритм, который задаёт вычисление произвольной степени с минимальным
количеством умножений, Ц не совсем простая задача.
Построим нерекурсивный аналог приведённого алгоритма. Представим вычисление
по рекурсивному алгоритму в таком виде:
х¹³=(х⁶)²*х¹=((х³)²*х⁰)²*х¹=(((х¹)²*х¹)²*х⁰)²*х¹
Этому соответствует следующая обработка вычисляемых показателей степеней:
13=6*2+1=(3*2+0)*2+1=((1*2+1)*2+0)*2+1
Как видим, вычислению степеней соответствует вычисление значения 13,
представленного полиномом относительно 2. Коэффициентами его являются цифры
двоичного разложения числа 13. Нетрудно убедится, что вычислению степени с
произвольным показателем n точно так же соответствует вычисление числа
n, представленного двоичным разложением. Причём это разложение-полином
записано по схеме Горнера. Раскроем в нём скобки:
1*2³+1*2²+0*2¹+1*2⁰
Коэффициент при 2⁰, 2¹, 2² и т.д. Ц это
последовательные остатки от деления на 2 чисел:
n, n div 2, (n div 2) div 2 и т.д.
причём остатку 1 соответствует в рекурсивном алгоритме присваивание t:=x, а 0 Ц
присваивание t:=1. Таким образом, двоичное разложение, например, числа 13 по
степеням двойки соответствует такому представлению х¹³:
х^{2^3}*x^{2^2}*1*x^{2^0}
Итак, достаточно вычислять степени:
x^{2^0}= x, x^{2^1}= x², x^{2^2}= (x²)², x^{2^3}= (x^{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. Программа вычисления факториала.
Program Factorial;
{$S+} {Включаем контроль переполнения стека}
var n: Integer;
function Fac (n: Integer): Real;
{Рекурсивная функция, вычисляющая n!}
begin
if n<0 then
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))
until EOF
end {main}.
Рекурсивная форма организации алгоритма обычно выглядит изящнее итерационной
и даёт более компактный текст программы, но при выполнении, как правило,
медленнее и может вызвать переполнение стека (при каждом входе в программу её
локальные переменные размещаются в особым образом организованной области
памяти, называемой программным стеком). Переполнение стека особенно ощутимо
сказывается при работе с сопроцессором: если программа использует
арифметический сопроцессор, результат любой вещественной функции возвращается
через аппаратный стек сопроцессора, рассчитанный всего на 8 уровней. Если,
например, попытаться заменить тип REAL функции FAC (см. листинг 3) на
EXTENDED, программа перестанет работать уже при N=8. Чтобы избежать
переполнения стека сопроцессора, следует размещать промежуточные результаты
во вспомогательной переменной. Вот правильный вариант для работы с типом
EXTENDED:
Program Factorial;
{$S+,N+,E+} {Включаем контроль стека и работу сопроцессора}
var n: Integer;
function Fac (n: Integer): extended;
var F: extended; {Буферная переменная
для разгрузки стека сопроцессора}
{Рекурсивная функция, вычисляющая n!}
begin {Fac}
if n<0 then
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))
until EOF
end {main}.
Архитектура стека непосредственно поддерживает рекурсию, поскольку каждый вызов
процедуры автоматически размещает новую копию локальных переменных. Например,
при каждом рекурсивном вызове функции факториала требуется одно слово памяти
для параметра и одно слово памяти для адреса возврата. То, что издержки на
рекурсию больше, чем на итерацию, связано с дополнительными командами,
затраченными на вход в процедуру и выход из неё. Некоторые компиляторы пытаются
выполнить оптимизацию, называемую оптимизацией хвостовой рекурсии
(tail-recursion) или оптимизацией последнего вызова (last-call). Если
единственный рекурсивный вызов в процедуре Ц последний оператор процедуры, то
можно автоматически перевести рекурсию в итерацию.
1.5.5. Числа Фибоначчи
С идейной точки зрения рекурсия аналогична методу математической индукции.
Базе индукции соответствует база рекурсии. Предположению индукции
соответствует предположение о том, что нужная процедура уже написана.
Наконец, шагу индукции соответствует вызов создаваемой рекурсивной процедуры.
В любой рекурсии необходимо предусмотреть условие завершения процесса, т.е.
когда вызова больше не происходит.
Рассмотрим ещё один пример использования рекурсии Ц вычисление N-ого по счёту
числа Фибоначчи. Числа Фибоначчи составляют последовательность, очередной
элемент которой вычисляется по двум предыдущим значениям:
Fн_n=F_n_-1 + F_n_-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(СНажмите <Enter>Т);
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)₂=(19)₁₀
Вычитание месяца из числа рождения в двоичном формате: _1111
0100
1011
(1011)₂=(11)₁₀

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_vn<1000 then
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_st<0.5 then
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 plat<1 then
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 i<10 then
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. Блок-схема к программе

_ +

+
Ц

_ +
_

+
Ц

Ц +

+
Ц

ВЫВОД
Итак, подведём итоги. Мы научились разрабатывать программы в среде Турбо
Паскаль, строить к ним блок-схемы и представлять данные в памяти ЭВМ. Также
мы познакомились с Умаленьким чудомФ в программировании Ц рекурсией и
рекурсивными алгоритмами.
Так почему же используют рекурсию? Дело в том, что многие алгоритмы можно
изящно и надёжно написать с помощью рекурсии, в то время как итерационное
решение трудно запрограммировать и легко сделать ошибки. Примером тому служат
алгоритм быстрой сортировки и алгоритмы обработки древовидных структур
данных. Языковые понятия опираются исключительно на рекурсию, а не на
итерацию. Даже для обычных языков типа С и Паскаль рекурсию, вероятно,
следует использовать более часто, чем это делается, из-за краткости и ясности
программ, которые получаются в результате.
Рекурсия отражает черту абстрактного мышления, проявляющуюся в самых
различных приложениях (в математике, синтаксическом анализе и трансляции,
древовидной сортировке и обработке данных с динамической структурой,
шахматных задачах и т.д.). Пользование ею избавляет от необходимости
последовательного (и часто, утомительного) описания процессов.
Таким образом, рекурсия не является чем-то нарочито усложнённым и
предназначенным для касты посвящённых, а представляет собой ещё одно средство
программирования, которым можно пользоваться удачно или злоупотреблять, как и
всяким другим.
Урок таков: следует избегать рекурсивного решения там, где есть очевидное
итеративное решение, и использовать его тогда, когда без рекурсии просто не
обойтись. УИтерация свойственна человеку, а рекурсия Ц богуФ (Л. Питер
Дойч).
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ:
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
с., ил.

Что выполняется	Состояние памяти
Вызов 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

СИМВОЛ	КОД		РАЗМЕР
СИМВОЛ	ДЕСЯТИЧНЫЙ	ДВОИЧНЫЙ	РАЗМЕР
В	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 байт

Blog

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

Что выполняется

Состояние памяти

1.5.1. УХанойская башняФ

Листинг 2. Программа УДвумерное множество КантораФ