Рекурсивный вызов функций.

Любая функция в программе на языке СИ может быть вызвана рекурсивно, т.е. она может вызывать саму себя. Рекурсия применяется в огромном количестве алгоритмов, её использование позволяет в ряде случаев значительно облегчить написание программы.

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

При каждом вызове для формальных параметров и переменных с классом памяти auto и register выделяется новая область памяти, так что их значения из предыдущих вызовов не теряются, но в каждый момент времени доступны только значения текущего вызова.

Переменные, объявленные с классом памяти static, не требуют выделения новой области памяти при каждом рекурсивном вызове функции и их значения доступны в течение всего времени выполнения программы.

Например, при выполнении следующей программы:

void main()

{

func(0);

}

void func(int i)

{

int j=0;

static int sj=0;

if(i==5)

return;

printf("i=%d j=%d sj=%d\n",i,j,sj);

i++;

j++;

sj++;

func(i);

// Даже здесь можно продолжить использование локальных

// переменных, их значения не будут испорчены в очередном

// рекурсивном вызове.

}

функция func() будет вызвана рекурсивно 5 раз, а в результате на экране будет напечатано:

i=0 j=0 sj=0;

i=0 j=1 sj=1

i=0 j=2 sj=2

i=0 j=3 sj=3

i=0 j=4 sj=4

Как видим, здесь с каждым вызовом под локальную переменную j выделяется новый участок памяти, и каждый раз она инициализируется нулём. Тем не менее, её значение сохраняется на протяжении всего текущего вызова, и даже после выхода из очередного рекурсивного вызова их можно продолжать использовать (см. комментарии в программе). Память же под статическую же переменную выделяется один раз, и поэтому изменение её значения в одном из вызовов отразится на значении этой переменной в других вызовах. Заметим, что значение локальной переменной i также меняется в каждом из вызовов, но происходит это в виде передачи её значения как параметра вызываемой функции.

Классический пример рекурсии - это математическое определение факториала n! :

n! = 1 при n=0;

n*((n-1)!) при n>1.

Функция, вычисляющая факториал, будет иметь следующий вид:

long faktor(int n)

{

if(!n)

return 1;

else

return n*faktor(n-1);

}

Хотя компилятор языка СИ не ограничивает число рекурсивных вызовов функций, это число ограничивается размером области памяти, в которой сохраняется информация о каждом вызове, и при слишком большом числе рекурсивных вызовов может произойти её переполнение.

17. Структуры и объединения. Операции над структурами и объединениями. Примеры использования.

Структуры. Объединения. Перечисления.

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

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