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

void swap (Any &a, Any &b)

{Any temp;

temp = a; a = b; b = temp;

}

template <class Any>  //новый шаблон

void swap (Any *a, Any *b, int n)

{Any temp;

for (int i=0; i<n; i++)

{temp = a[i]; a[i] = b[i]; b[i] = temp;}

}

void show(int a[], int n)

{for (int i=0; i<n; i++)

cout << a[i] << “  “;

cout << endl;

}

Результаты работы программы:

  i=10   j=20

 new i=20   new j=10

 original arrays:

0  7  0  4  1  7  7  6

0  6  2  0  1  9  6  9

 swapped arrays:

0  6  2  0  1  9  6  9

0  7  0  4  1  7  7  6

Рекурсивные подпрограммы

Понятие рекурсии затруднено даже для программистов с опытом. Для вычислительных задач более эффективной, чем рекурсия, оказывается итерация. Как мы знаем, итерация – это повторяемое выполнение процесса до тех пор, пока не будет удовлетворено некоторое условие (while  или do while).

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

Рекурсивная подпрограмма – подпрограмма, содержащая вызовы самой себя. Выполнение рекурсивной подпрограммы происходит в два этапа: первый этап завершается выполнением так называемого условия завершения рекурсии; второй этап – вычислений действий на основе рекурсивных соотношений.

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

Как мы знаем, компилятор назначает адреса для каждого из глобальных данных. Такие данные называют данными со статическим размещением – их адреса зависят только от их описания в программе и не изменяются при исполнении программы. Другую категорию данных, называемых данными с автоматическим размещением, составляют данные подпрограмм: переменные их локальных блоков и параметры-значения. Для них память выделяется и освобождается в соответствии с порядком вызова подпрограмм при исполнении программы. Этот механизм распределения оперативной памяти определен самим языком программирования (его семантикой).

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

Пусть при исполнении программы Р1 вызывается функция Р2, а из нее – функция  Р3 и т.д. Данные, локализуемые каждой из этих функций, остаются в памяти. Поскольку завершение работы этих функций происходит в порядке, обратном их вызову, то выделение и возврат в свободную память фрагментов памяти для их локальных данных подчиняется принципу работы со стеком (первым пришел – последним ушел). Поэтому и механизм распределения памяти для данных вызываемых функций называется стековым механизмом, а распределяемая при этом память называется областью памяти для данных со стековым размещением. Выделение таких фрагментов памяти происходит и при каждом вызове очередного «поколения» рекурсивной функции.