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

       

СТЕК И ФУНКЦИИ


Будем рассматривать каждый ВЫЗОВ функции как помещение в специальный стек большого "блока информации", включающего в частности АРГУМЕНТЫ И ЛОКАЛЬНЫЕ ПЕРЕМЕННЫЕ вызываемой функции.

Оператор 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 раза!


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