РЕКУРСИВНЫЕ ФУНКЦИИ. СТЕК
Рекурсивной называется функция, вызывающая сама себя.
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()); } }
