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

При вызове рекурсивной подпрограммы с некоторым значением аргумента ее выполнение не завершается до конца, а порождает новый вызов с другим значением аргумента. Каждый рекурсивный вызов порождает новое «поколение» рекурсивной подпрограммы, сопровождаемое, в частности, выделением стековой памяти под параметры-значения и локальные переменные. Любой локальной переменной Х на разных уровнях  рекурсии будут соответствовать различные ячейки памяти, которые могут иметь различные значения. Поэтому выполнение вычислений с большой глубиной рекурсии (числом поколений) нередко приводит к нехватке этой памяти (сегмента стека).

Компилятор назначает адреса для каждого из глобальных данных. Такие данные называют данными со статическим размещением – их адреса зависят только от их описания в программе и не изменяются при исполнении программы.

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

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

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

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

Определены следующие формы рекурсивных подпрограмм:

§  форма с выполнением действий на рекурсивном спуске (до рекурсивного вызова);

§  форма с выполнением действий на рекурсивном возврате (после рекурсивного вызова);

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

Например, структура рекурсивной функции может иметь формы:

С выполнением действий на рекурсивном спуске:

void Rec(); { S; if (условие)  Rec(); }

С выполнением действий на рекурсивном возврате:

void  Rec(); { if  (условие) {Rec(); S;} }

С выполнением действий как на рекурсивном спуске, так и на рекурсивном возврате:

void Rec();

{ S1; if (условие) {Rec(); S2;}

}

void Rec();

{ if( условие) {S1; Rec(); S2;}

}

Приведенная ниже рекурсивная функция работает бесконечно и бесконечно печатает известные строки (это форма с выполнением действий на рекурсивном спуске):

#include <iostream.h>

#include <conio.h>

main ()

{ void PopeAndDoge1(); PopeAndDoge1();

getch();

return 0 ;

}

void PopeAndDoge1() {         

cout << “ Y popa byla sobaka, on ee lubil.”<< endl;

cout << “ Ona s’ela kysok mjasa, on ee ubil.”<< endl; cout << “ poxoronil i nadpic napical:”<< endl; PopeAndDoge1(); }         

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