Руководство полного чайника по программированию на языке Си

       

РЕКУРСИВНЫЕ ФУНКЦИИ. СТЕК


Рекурсивной называется функция, вызывающая сама себя.

int factorial(int arg){ if(arg == 1) return 1; /* a */ else return arg * factorial(arg - 1); /* b */ }

Эта функция при вызове factorial(n) вычислит произведение

n * (n-1) * ... * 3 * 2 * 1

называемое "факториал числа n". В данной функции переменная arg будет отведена (а после и уничтожена) МНОГО РАЗ.

Так что переменная factorial::arg должна получить еще и НОМЕР вызова функции:

factorial::arg[уровень_вызова]

И на каждом новом уровне новая переменная скрывает все предыдущие. Так для factorial(4) будет

+----------------------------------------+ | | factorial::arg[ 0_ой_раз ] есть 4 | | | factorial::arg[ 1_ый_раз ] есть 3 | | | factorial::arg[ 2_ой_раз ] есть 2 | | | factorial::arg[ 3_ий_раз ] есть 1 | V --------+ +---------

Затем пойдут возвраты из функций:

+----------------------------------------+ A | /* b */ return 4 * 6 = 24 | | | /* b */ return 3 * 2 = 6 | | | /* b */ return 2 * 1 = 2 | | | /* a */ return 1; | | --------+ +---------

Такая конструкция называется СТЕК (stack).

--------+ +------------ | | пустой стек +---------------+



Положим в стек значение a | --------+ | +------------ | V | +---------------+ | a | <--- вершина стека +---------------+

Положим в стек значение b

--------+ +------------ | | +---------------+ | b | <--- вершина стека +---------------+ | a | +---------------+

Положим в стек значение c

--------+ +------------ | | +---------------+ | c | <--- вершина стека +---------------+ | b | +---------------+ | a | +---------------+

Аналогично, значения "снимаются со стека" в обратном порядке: c, b, a.

В каждый момент времени у стека доступно для чтения (копирования) или выбрасывания только данное, находящееся на ВЕРШИНЕ стека.

Так и в нашей рекурсивной функции переменная factorial::arg ведет себя именно как стек (этот ящик-стек имеет имя arg) - она имеет ОДНО имя, но разные значения в разных случаях. Переменные, которые АВТОМАТИЧЕСКИ ведут себя как стек, встречаются только в (рекурсивных) функциях.

Стек - это часто встречающаяся в программировании конструкция. Если подобное поведение нужно программисту, он должен промоделировать стек при помощи массива:

int stack[10]; int in_stack = 0; /* сколько элементов в стеке */

/* Занесение значения в стек */ void push(int x){ stack[in_stack] = x; in_stack++; }

/* Снять значение со стека */ int pop(){ if(in_stack == 0){ printf("Стек пуст, ошибка.\n"); return (-1); } in_stack--; return stack[in_stack]; }

Обратите в нимание, что нет нужды СТИРАТЬ (например обнулять) значения элементов массива, выкинутых с вершины стека. Они просто больше не используются, либо затираются новым значением при помещении на стек нового значения.

void main(){ push(1); push(2); push(3);

while(in_stack > 0){ printf("top=%d\n", pop()); } }



Содержание раздела