- •1. Абстрагирование типов
- •1.1. Понятие типа данных
- •1.1.1. Простые типы
- •1.1.2. Абстрактные типы
- •2. Идентификация объектов
- •2.1. Именование
- •2.2. Указание
- •2.2.1. Организация адресного пространства оперативной
- •2.2.2. Понятие указателя
- •2.2.3. Действия над указателями
- •2.2.4. Связывание идентификатора объекта с его
- •3. Время жизни объекта. Классы памяти
- •3.1. Понятие “времени жизни” объекта
- •3.2. Классы памяти
- •3.2.1. Статическая память
- •3.2.2. Автоматическая память
- •3.2.3. Динамическая память
- •4. Динамические структуры данных
- •4.1. Метод вычисляемого и хранимого адреса.
- •4.2. Понятие динамической структуры данных
- •4.3. Линейные динамические структуры данных (списки)
- •4.3.1. Основные виды списков
- •4.4. Односвязные списки
- •4.4.1. Включение узла в начало списка
- •4.4.2. Создание списка из n узлов за счет добавления
- •4.4.3. Создание списка из n узлов за счет добавления
- •4.4.4. Исключение узла из начала списка
- •4.4.5. Перестановка указателя
- •4.4.6. Поиск в списке узла по заданному условию
- •4.4.7. Включение нового узла в список за тем узлом, на
- •4.4.8. Исключение из списка узла за тем узлом, на
- •4.4.9. Исключение из списка узла, на который предварительно
- •4.4.10. Разрушение списка
- •4.4.11. Программный модуль, реализующий операции
- •4.5. Односвязные циклические списки
- •4.6. Двусвязные списки
- •4.6.1. Включение нового узла в список за тем узлом, на
- •4.6.2. Исключение из списка узла, на который
- •4.7. Ортогональные списки (мультисписки)
- •4.8. Разнородные списки
- •4.9. Управление динамической памятью
- •4.9.1. Администратор кучи
- •4.9.2. Алгоритмы выделения участков памяти по запросу
- •4.9.3. Фрагментация
- •4.9.4. Накопление мусора
- •4.9.5. Висящие ссылки
- •5. Множественная интерпретация объектов
- •5.1. Совместимость типов. Приведение и преобразование типов
- •5.2. Методы совмещения типов
- •5.2.1. Запись с вариантной частью
- •5.2.2. Использование директивы absolute
- •5.2.3. Параметры без типа
- •5.2.4. Открытые массивы
- •5.2.5. Наложение масок с помощью указателей
- •6. Рекурсивные структуры данных
- •6.1. Итерация и рекурсия в программировании
- •6.1.1. Понятие рекурсии
- •6.1.2. Итеративная и рекурсивная схема организации
- •6.2. Задача о “ханойских башнях”
- •6.3. Виды рекурсивных структур данных
- •6.3.1. Арифметические выражения
- •6.3.2. Динамические линейные структуры данных: списки
- •6.3.3. Иерархические линейные структуры данных: наборы
- •6.4. Эффективность рекурсивных вычислений
- •7. ИерархическиеНелинейные структуры данных.Деревья
- •7.1. Деревья общего вида
- •7.2. Бинарные деревья
- •7.3. Представление бинарных деревьев
- •7.3.1. Представление бинарных деревьев на статической
- •7.3.2. Представление бинарных деревьев на
- •7.4. Алгоритмы обхода бинарных деревьев
- •7.5. Виды бинарных деревьев
- •7.5.1. Сбалансированные деревья
- •7.5.2. Дихотомические деревья (деревья поиска)
- •7.5.3. Деревья выражений
- •7.6. Программный модуль, реализующий операции
- •Список рекомендуемой литературы
6.1.2. Итеративная и рекурсивная схема организации
вычислительного процесса
Для того чтобы лучше понять особенности рекурсивных алгоритмов, полезно сопоставить итеративнную и рекурсивную огранизацию процесса вычислений в программе. Особенности итеративного и рекурсивного вычислительного процесса рассмотрим на примере вычисления значения факториала некоторого натурального числа N.
Итеративная схема организации вычислительного процесса
Итеративный процесс можно проиллюстрировать с помощью схемы, приведенной на рис. 55. Этот процесс состоит из четырех блоков: инициализации, принятия решения (о продолжении вычислений), вычисления и модификации.
Рис. 55. Схема итеративного процесса
В основе итеративного вычислительного процесса лежит итеративный циклWhile, Repeat-Until, For. Наиболее общим является цикл While:
While < условие цикла > do < тело цикла >;
Итеративная схемавычисления факториала:
N! = 1 * 2 * 3 * … * N.
Процедура, реализующая итеративную схему вычисления факториала:
Procedure Iter_Fact ( n: word; var f: word ); |
| |
Var i: word; |
| |
begin |
| |
i:=1; f:=1; |
{ инициализация } | |
while i < = n do begin |
{ решение о завершении } | |
f:= f * i; |
{ вычисления } | |
inc( i ); |
{ модификация } | |
end; |
| |
end; |
|
Существует два важных положения, известных в математике и в программировании, определяющих соотношение между итерацией и рекурсией.
1. Любой итеративный цикл может быть заменен рекурсией.
2. Рекурсия не всегда может быть заменена итерацией.
Рекурсивная схема организации вычислительного процесса
Общая схема рекурсивного вычислительного процесса представлена на рис. 56.
Рис. 56. Схема рекурсивного вычислительного процесса
Так как обращаться к рекурсивной процедуре можно как из нее самой, так и извне, каждое обращение к рекурсивной процедуре вызывает ее независимую активацию. При каждой активации образуются копии всех локальных переменных и формальных параметров рекурсивной процедуры, в которых “оставляют следы” операторы текущей активации. Таким образом, для рекурсивной процедуры может одновременно существовать несколько активаций. Для обеспечения правильного функционирования рекурсивной процедуры необходимо сохранять адреса возврата в таком порядке, чтобы возврат после завершения каждой текущей активации выполнялся в точку, соответствующую оператору, непосредственно следующему за оператором рекурсивного вызова. Совокупность локальных переменных, формальных параметров рекурсивной процедуры и адреса возврата однозначно характеризует текущую активацию и образуетфрейм активации. Фрейм активации необходимо сохранять при очередной активации и восстанавливать после завершения текущей активации.
В блоке принятия решения (о продолжении вычислений) производится проверка, являются ли значения входных параметров такими, для которых возможно вычисление значений выходных параметров в соответствии с базисной частью рекурсивного определения. На основании этой проверки принимается решение о выполнении промежуточных или окончательных вычислений. Блок промежуточных вычислений можно объединить с блоком обращения к процедуре, если промежуточные вычисления очень просты. В блоке окончательных вычислений производится явное определение параметров-переменных процедуры для конкретных значений входных параметров, соответствующих текущей активации процедуры.
В основе рекурсивного вычислительного процесса лежит рекурсивный цикл, который реализуется через вызов рекурсивной процедуры, причем каждая активация рекурсивной процедуры эквивалентна одному проходу итеративного циклаWhile.
Общая схема рекурсивного цикла:
Procedure Рекурсивный_Цикл (…);
begin
if< условие цикла>then
begin
< тело рекурсивного цикла; >
Рекурсивный_Цикл (…);
end;
end;
В теле рекурсивного цикла (в блоке промежуточных вычислений) обязательно должны содержаться операторы, изменяющие значения переменных, от которых зависит условие завершения рекурсивного цикла. Напомним, что выполнение условия завершения рекурсивного цикла соответствует достижению базиса рекурсивного определения. Если значения этих переменных не успевают измениться до очередной активации рекурсивной процедуры, возникает бесконечный рекурсивный цикл.
Общая схема бесконечного рекурсивного цикла:
Procedure Бесконечный_Рекурсивный_Цикл (…);
begin
if< условие цикла >then
begin
Бесконечный_Рекурсивный_Цикл (…);
< тело рекурсивного цикла; >
end;
end;
Рекурсивная схемавычисления факториала:
Базисная часть:
0! = 1; 1! = 1;
Рекурсивная часть:
N! = N * ( N-1 )! = N * ( N-1 ) * ( N-2 )! = N * ( N-1 ) * … * ( N – ( N-1 ) )! =
Процедура, реализующая рекурсивную схему вычисления факториала:
Procedure Recurs_Fact (n : word; var f: word ); |
| ||
begin |
| ||
if n <= 1 then |
{ принятие решения о завершении вычислений:} | ||
f:=1; |
{ да - окончательные вычисления для базисной части } | ||
elsebegin |
| ||
Recurs_Fact ( n-1, f ); |
{ нет - промежуточные вычисления и обращение процедуры к самой себе } | ||
{ 1 } f:=f * n; |
{ окончательные вычисления для рекурсивной части } | ||
end; |
| ||
{ 2 } end; |
|
{ 1 }– адрес возврата после завершения активации,
{ 2 }– завершение активации.
С каждым обращением к рекурсивной процедуре ассоциируется номер уровня рекурсии(номер фрейма активации). Считается, что при первоначальном вызове рекурсивной процедуры из основной программы номер уровня рекурсии равен единице. Каждый следующий вход в процедуру имеет номер уровня на единицу больше, чем номер уровня процедуры, из которой производится это обращение. Другой характеристикой рекурсивной процедуры являетсяглубина рекурсии, определяемая максимальным уровнем рекурсии в процессе вычисления при заданных аргументах. В общем случае эта величина неочевидна, исключение составляют простые рекурсивные функции: например, при вычислении значения N!глубина рекурсии равнаN.
Так как при выходе из текущей активации самым первым должен быть восстановлен фрейм, который был позже всех сохранен, для хранения фреймов используется автоматическая память, т.е. область системного стека (см. 3.2.2). Таблица 3 и рис. 57 поясняют механизм рекурсивных вычислений.
Таблица 3. Трасса вычисления 3!
Рис. 57. Фреймы активации при вычислении 3!