СТЕК И ФУНКЦИИ
Будем рассматривать каждый ВЫЗОВ функции как помещение в специальный стек большого "блока информации", включающего в частности АРГУМЕНТЫ И ЛОКАЛЬНЫЕ ПЕРЕМЕННЫЕ вызываемой функции.
Оператор return из вызванной функции выталкивает со стека ВЕСЬ такой блок.
В качестве примера рассмотрим такую программу:
int x = 7; /* глобальная */ int v = 333; /* глобальная */
int factorial(int n){ int w; /* лишняя переменная, только для демонстрационных целей */
w = n;
if(n == 1) return 1; /* #a */ else return n * factorial(n-1); /* #b */ } void func(){ int x; /* func::x */
x = 777; /* #c */ printf("Вызвана функция func()\n"); } void main(){ int y = 12; /* main::y */ int z;
/* A */ z = factorial(3); /* B */ printf("z=%d\n", z);
func(); /* C */ }
Выполнение программы начнется с вызова функции main(). В точке /* A */
| в з г л я д | V V
--------+ +-------- |=======================| | z = мусор | | y = 12 | +------+---------+ |main() | |x = 7 | v = 333 | +-----------------------+-----------+------+---------+----- СТЕК ВЫЗОВОВ ФУНКЦИЙ ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ
В каждый данный момент видимы переменные, которые находятся a) на вершине (и только) стека вызовов функций. b) и незаслоненные ими глобальные переменные. В данном случае мы смотрим "сверху" и видим:
main::z, main::y, ::x, ::v
В точке /* B */ мы вызываем factorial(3).
--------+ +-------- |=======================| | w = мусор | | n = 3 | |factorial(3) | |=======================| | +-|---> текущий оператор z = factorial(3); | z = мусор | | y = 12 | +------+---------+ |main() | |x = 7 | v = 333 | +-----------------------+-----------+------+---------+----- СТЕК ВЫЗОВОВ ФУНКЦИЙ ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ
При новом взгляде видимы: factorial(3)::w, factorial(3)::n, ::x, ::v
Стали невидимы: main::z, main::y
Строка "текущий оператор ..." указывает место, с которого надо возобновить выполнение функции, когда мы вернемся в нее.
Когда выполнение программы в функции factorial(3) дойдет до точки /* #b */ будет выполняться return 3 * factorial(2). В итоге будет вызвана функция factorial(2).
--------+ +-------- |=======================| | w = мусор | | n = 2 | |factorial(2) | |=======================| | +-|---> текущий оператор return 3 * factorial(2); | w = 3 | | n = 3 | |factorial(3) | |=======================| | +-|---> текущий оператор z = factorial(3); | z = мусор | | y = 12 | +------+---------+ |main() | |x = 7 | v = 333 | +-----------------------+-----------+------+---------+----- СТЕК ВЫЗОВОВ ФУНКЦИЙ ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ
Когда выполнение программы в функции factorial(2) дойдет до точки /* #b */ будет выполняться return 2 * factorial(1). В итоге будет вызвана функция factorial(1).
--------+ +-------- |=======================| | w = мусор | | n = 1 | |factorial(1) | |=======================| | +-|---> текущий оператор return 2 * factorial(1); | w = 2 | | n = 2 | |factorial(2) | |=======================| | +-|---> текущий оператор return 3 * factorial(2); | w = 3 | | n = 3 | |factorial(3) | |=======================| | +-|---> текущий оператор z = factorial(3); | z = мусор | | y = 12 | +------+---------+ |main() | |x = 7 | v = 333 | +-----------------------+-----------+------+---------+----- СТЕК ВЫЗОВОВ ФУНКЦИЙ ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ
Затем в factorial(1) выполнение программы дойдет до точки /* #a */ и будет производиться return 1.
При return вычеркивается ОДИН блок информации со стека вызовов функций, и возобновляется выполнение "текущего оператора" в функции, ставшей НОВОЙ вершиной стека вызовов. Заметьте, что в данной ситуации вызванные функции factorial(m) еще не завершились. В них еще ЕСТЬ что сделать: вычислить выражение в return, и собственно выполнить сам return. Вычисления будут продолжены.
--------+ +-------- |=======================| | +-|---> текущий оператор return 1; | w = 1 | | n = 1 | |factorial(1) | |=======================| | +-|---> текущий оператор return 2 * factorial(1); | w = 2 | | n = 2 | |factorial(2) | |=======================| | +-|---> текущий оператор return 3 * factorial(2); | w = 3 | | n = 3 | |factorial(3) | |=======================| | +-|---> текущий оператор z = factorial(3); | z = мусор | | y = 12 | +------+---------+ |main() | |x = 7 | v = 333 | +-----------------------+-----------+------+---------+----- СТЕК ВЫЗОВОВ ФУНКЦИЙ ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ
Начинается выталкивание функций со стека и выполнение операторов return;
--------+ +-------- |=======================| | +-|---> текущий оператор return 2 * 1; | w = 2 | | n = 2 | |factorial(2) | |=======================| | +-|---> текущий оператор return 3 * factorial(2); | w = 3 | | n = 3 | |factorial(3) | |=======================| | +-|---> текущий оператор z = factorial(3); | z = мусор | | y = 12 | +------+---------+ |main() | |x = 7 | v = 333 | +-----------------------+-----------+------+---------+----- СТЕК ВЫЗОВОВ ФУНКЦИЙ ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ
--------+ +-------- |=======================| | +-|---> текущий оператор return 3 * 2; | w = 3 | | n = 3 | |factorial(3) | |=======================| | +-|---> текущий оператор z = factorial(3); | z = мусор | | y = 12 | +------+---------+ |main() | |x = 7 | v = 333 | +-----------------------+-----------+------+---------+----- СТЕК ВЫЗОВОВ ФУНКЦИЙ ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ
--------+ +-------- |=======================| | +-|---> текущий оператор z = 6; | z = мусор | | y = 12 | +------+---------+ |main() | |x = 7 | v = 333 | +-----------------------+-----------+------+---------+----- СТЕК ВЫЗОВОВ ФУНКЦИЙ ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ
--------+ +-------- |=======================| | z = 6 | | y = 12 | +------+---------+ |main() | |x = 7 | v = 333 | +-----------------------+-----------+------+---------+----- СТЕК ВЫЗОВОВ ФУНКЦИЙ ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ
Наконец, в точке /* C */ будет вызвана функция func(). Рассмотрим точку /* #c */ в ней.
--------+ +-------- |=======================| | x = 777; | |func(); | |=======================| | +-|---> текущий оператор func(); | z = 6 | | y = 12 | +------+---------+ |main() | |x = 7 | v = 333 | +-----------------------+-----------+------+---------+----- СТЕК ВЫЗОВОВ ФУНКЦИЙ ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ
В данном месте нас интересует - какие переменные видимы? Видимы: func::x = 777 ::v = 333
И все. ::x заслонен локальной переменной. main::y, main::z невидимы, так как находятся не на вершине стека вызовов функций
Многие функции более естественно выражаются через рекурсию. Хотя, часто это приводит к излишним вычислениям по сравнению с итерациями (то есть циклами). Вот пример - числа Фибоначчи.
int fibonacci(int n){ if(n==1 || n==2) return 1;
/* else */
return fibonacci(n-1) + fibonacci(n-2); } void main(){ printf("20ое число Фибоначчи равно %d\n", fibonacci(20)); }
Поскольку тут отсутствует массив для запоминания промежуточных результатов, то этот массив на самом деле неявно моделируется в виде локальных переменных внутри стека вызовов функций. Однако этот способ плох - в нем слишком много повторяющихся действий. Добавим оператор печати - и посчитаем, сколько раз была вызвана fibonacci(1) ?
int called = 0;
int fibonacci(int n){ if(n==1){ called++; return 1;
} else if(n==2) return 1;
return fibonacci(n-1) + fibonacci(n-2); } void main(){ printf("20ое число Фибоначчи равно %d\n", fibonacci(20)); printf("fibonacci(1) была вызвана %d раз\n", called); }
Она была вызвана... 2584 раза!
