66. Функции, область видимости, рекурсия

Функция — это кусок программы с именем, входом и выходом. Всё, что делает программа на микроконтроллере, разложено по функциям: main, обработчики прерываний, драйверы, задачи операционной системы.

Раздел про то, как функция объявляется и вызывается, что на самом деле происходит с аргументами, где живут переменные и сколько они живут. И про рекурсию — приём красивый, но на камне с несколькими килобайтами ОЗУ требующий отдельного разговора о стеке.

Как это называется в документации

Оригинал	Перевод
function declaration, prototype	объявление функции, прототип
function definition	определение функции
parameter, argument	параметр, аргумент
pass by value	передача по значению
return value	возвращаемое значение
calling convention (AAPCS)	соглашение о вызовах
stack frame	кадр стека
scope	область видимости
storage duration, lifetime	время жизни
automatic, static storage	автоматическая, статическая память
shadowing	затенение имени
recursion, base case	рекурсия, условие остановки
tail call	хвостовой вызов
call graph	граф вызовов

66.1 Зачем функции

Функция решает три задачи:

• даёт имя действию: uart_send(byte) читается лучше, чем восемь строк работы с регистрами;
• убирает повторение: исправление в одном месте исправляет все вызовы;
• ограничивает видимость: переменные функции не мешают остальной программе.

Функция состоит из заголовка — тип результата, имя, параметры — и тела:

int max(int a, int b)       /* заголовок */
{                           /* тело */
    if (a > b)
        return a;
    return b;
}

return возвращает значение и сразу завершает функцию. Если функция ничего не возвращает, её тип — void, и return в ней пишут без значения или не пишут вовсе.

66.2 Объявление и определение

Компилятор читает файл сверху вниз. Чтобы вызвать функцию раньше, чем написано её тело, её объявляют — прототипом:

int max(int a, int b);      /* объявление: имя, типы, и больше ничего */

int main(void)
{
    return max(3, 7);
}

int max(int a, int b)       /* определение: тело */
{
    return a > b ? a : b;
}

Прототипы функций, которые нужны в нескольких файлах, выносят в заголовочный файл (раздел 71). А если прототип есть, а тела нет нигде, ошибку выдаст уже не компилятор, а компоновщик — «undefined symbol» (раздел 63.7).

int f() и int f(void) — не одно и то же. Пустые скобки в старом C означают «параметры не указаны», и компилятор не проверяет вызовы:

Правило простое: функция без параметров объявляется с void в скобках. Тогда ошибку с аргументами найдёт компилятор, а не вы на отладке.

66.3 Как передаются аргументы

В C аргументы передаются только по значению. Функция получает копии, и что бы она с ними ни делала, переменные вызывающего не меняются:

void swap(int a, int b) { int t = a; a = b; b = t; }

int n = 7, m = 5;
swap(n, m);                 /* n = 7, m = 5 — поменялись только копии */

Чтобы функция могла изменить переменную, ей передают адрес переменной — тогда копируется адрес, а по нему можно добраться до оригинала:

void swap(int *pa, int *pb) { int t = *pa; *pa = *pb; *pb = t; }

swap(&n, &m);               /* n = 5, m = 7 */

Как устроены указатели — раздел 67.

Где аргументы лежат на самом деле. Правила вызова на ARM (соглашение AAPCS) одинаковы для всех компиляторов, и их полезно знать:

• первые четыре аргумента передаются в регистрах r0, r1, r2, r3;
• пятый и следующие — через стек: вызывающий кладёт их туда, а вызываемая функция оттуда читает;
• результат возвращается в r0.

Это правила для 32-битных целых и указателей. 64-битное значение (int64_t, а без -mfloat-abi=hard и double) занимает пару регистров — r0:r1 или r2:r3: в f(int x, int64_t y) число y идёт в r2:r3, а r1 пропадает. 64-битный результат возвращается в r0:r1. При -mfloat-abi=hard на Cortex-M4 вещественные аргументы идут в регистры FPU s0–s15, а результат float — в s0 (раздел 77.3). Структура больше четырёх байт возвращается через память: её адрес вызывающий передаёт скрытым первым аргументом в r0.

Вот вызов five(1, 2, 3, 4, 5) в том виде, в каком его делает компилятор:

movs    r0, #1
movs    r1, #2
movs    r2, #3
movs    r3, #4
mov.w   r12, #5
str.w   r12, [sp]           ; пятый — в стек
bl      five

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

66.4 Область видимости и время жизни

У каждой переменной две независимые характеристики: где её имя видно и сколько она живёт.

Локальные живут на стеке: при входе в функцию для них отводится место, при выходе оно освобождается. Поэтому их значение не сохраняется между вызовами и не обнуляется при старте (раздел 64.1).

static у локальной переменной меняет время жизни, но не видимость. Сравните:

void count(void)        { int a = 5;        a++; printf("%d ", a); }  /* 6 6 6 */
void count_static(void) { static int a = 5; a++; printf("%d ", a); }  /* 6 7 8 */

Три вызова первой печатают 6, 6, 6: переменная каждый раз создаётся заново. Вторая печатает 6, 7, 8: static-переменная создана один раз до начала программы, и начальное значение 5 присвоено ей тогда же, а не при каждом вызове.

Задача на всё сразу:

int y = 1;

int f(int *pa)
{
    static int x = 3;
    x += y;
    return x + *pa + y;
}

int main(void)
{
    int n = 10;
    y++;
    printf("%d ", f(&n));   /* 17 */
    printf("%d\n", f(&n));  /* 19 */
}

Первый вызов: y уже 2, x было 3, стало 5; 5 + 10 + 2 = 17. Второй: x помнит 5 и становится 7; 7 + 10 + 2 = 19.

static у глобальной переменной или функции делает имя невидимым для других файлов. Это главный инструмент порядка в многофайловом проекте: всё, что не нужно снаружи, объявляется static (раздел 3.6).

Затенение. Локальная переменная может носить то же имя, что и глобальная, — и тогда внутри блока глобальная становится недоступна:

int level = 1;
int shadow(void) { int level = 2; return level; }    /* 2; глобальная осталась 1 */

В C нет способа обратиться к затенённой глобальной из этого блока. Компилятор о затенении молчит даже с -Wall -Wextra; предупреждает только ключ -Wshadow. Ошибка коварна тем, что код выглядит правильно: пишем в level, а меняется не та переменная.

66.5 static как память функции

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

unsigned prbs7(void)
{
    static unsigned a = 0x01;                       /* состояние между вызовами */
    unsigned bit = ((a >> 6) ^ (a >> 5)) & 1u;
    a = ((a << 1) | bit) & 0x7Fu;
    return a;
}

Семь бит дают 128 комбинаций, но одна из них, ноль, запрещена: из нуля генератор не выходит никогда. Остальные 127 проходятся по кругу, и последовательность повторяется ровно через 127 вызовов — это максимум для семи бит, 2⁷ − 1. Поэтому начальное значение — любое, кроме нуля. Состояние никто снаружи испортить не может: имя a видно только внутри функции.

Частый вопрос: сколько static-переменных будет при рекурсии? Одна. Сколько бы раз функция ни вызывала сама себя, её static-переменная существует в единственном экземпляре. Функция, считающая свои заходы в static-счётчике, после пяти вложенных вызовов увидит в нём 5 — у всех уровней один и тот же счётчик.

⚠️ static и прерывания. Функция со static-состоянием не должна вызываться одновременно из основной программы и из прерывания: прерывание может застать состояние наполовину обновлённым. То же с задачами ОСРВ (раздел 30).

66.6 Рекурсия

Рекурсивная функция вызывает сама себя. У неё обязательно есть две части: условие остановки и шаг, который приближает к нему.

unsigned fact(unsigned n)
{
    if (n <= 1)                 /* условие остановки */
        return 1;
    return n * fact(n - 1);     /* шаг */
}

Каждый вызов ждёт результата следующего. fact(3) вызывает fact(2), та — fact(1), которая возвращает 1; дальше результаты поднимаются обратно: 2 · 1, потом 3 · 2.

Порядок действий относительно вызова решает всё:

void rec(int n)     { if (n > 0) rec(n - 1); printf("%d ", n); }   /* 0 1 2 3 */
void rec_pre(int n) { printf("%d ", n); if (n > 0) rec_pre(n - 1); } /* 3 2 1 0 */

Печать после вызова выполняется «на обратном пути» — снизу вверх.

Рекурсивно удобно записывать то, что само определено рекурсивно:

int sum_digits(int n) { return n > 0 ? n % 10 + sum_digits(n / 10) : 0; }  /* 12345 → 15 */
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }               /* (14, 35) → 7 */

И заодно о пределах: fact(12) = 479 001 600 ещё помещается в 32 бита, а fact(13) — уже нет. Вместо 6 227 020 800 получится 1 932 053 504, без всякого предупреждения.

66.7 Цена рекурсии: стек

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

Сколько это в байтах, видно из кода. Функция с локальным массивом на 256 байт начинается командой sub sp, #256 — ровно столько она отъедает от стека при каждом вызове. Рекурсивная fib берёт 16 байт на вызов, и при глубине 30 это уже 480 байт.

На компьютере стек — мегабайты. На микроконтроллере — обычно килобайт или два, а у задачи ОСРВ бывает и несколько сотен байт (раздел 26.7). Переполнение стека по умолчанию не даёт ошибки: он молча заезжает на соседние данные (раздел 11.4). Поймать его можно тремя способами. У Cortex-M33 (L5, U5, H5) есть регистры предела стека MSPLIM и PSPLIM: как только указатель стека уходит ниже предела, случается отказ UsageFault, а память под пределом остаётся целой. На других ядрах под стеком ставят область MPU без доступа (раздел 11а.4). Или раскладывают память так, чтобы стек начинался у нижней границы ОЗУ: переполнившись, он выходит за неё, и отказ случается на первой же записи.

И вот главное. Компоновщик Keil умеет посчитать максимальную глубину стека всей программы по графу вызовов — это лучший способ узнать, сколько стека нужно на самом деле (раздел 35.4). Но на рекурсии он останавливается:

Maximum Stack Usage = 272 bytes + Unknown(Cycles, Untraceable Function Pointers)
Call chain for Maximum Stack Depth:
main => fib_rec => fib_rec (Cycle)

Цикл в графе вызовов означает: глубину не знает никто. Она зависит от данных. Поэтому во встраиваемых стандартах программирования рекурсия обычно запрещена, а там, где она допустима, её глубину ограничивают явно.

66.8 Цена рекурсии: время

Числа Фибоначчи определены рекурсивно — F(n) = F(n−1) + F(n−2), — и прямая запись выглядит элегантно:

long fib(int n) { return n <= 0 ? 0 : n == 1 ? 1 : fib(n - 1) + fib(n - 2); }

Но каждый вызов порождает два, и одни и те же значения считаются заново много раз:

Почти три миллиона вызовов вместо тридцати шагов. Число вызовов растёт так же быстро, как сами числа Фибоначчи. Как такие вещи оценивают заранее — раздел 76, как измеряют — раздел 73.

66.9 Когда компилятор убирает рекурсию сам

Если рекурсивный вызов — последнее действие функции, как в gcd, компилятор с оптимизацией превращает его в обычный переход: рекурсия становится циклом, стек не растёт.

Современный компилятор идёт дальше. Рекурсивный fact с оптимизацией превращается в тот же цикл, что и написанная вручную итеративная версия, — различается одна команда, порядком операндов. А вот у fib из двух рекурсивных вызовов убрать удаётся только один.

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

66.10 Грабли

Функция «не меняет» переменную. Аргумент передан по значению: нужна передача адреса.

Лишний аргумент при вызове прошёл незамеченным. Объявление int f() без void.

Прототип есть, а компоновщик пишет «undefined symbol». Тела функции нет ни в одном файле проекта.

Счётчик в функции каждый раз начинается заново. Переменная не static.

static-переменная «не сбрасывается». Так и задумано: начальное значение присваивается один раз.

Изменили глобальную, а значение прежнее. Внутри блока её затеняет локальная с тем же именем. Ключ -Wshadow находит такие места.

Функция со static-состоянием иногда даёт мусор. Её вызывают одновременно из прерывания и из основной программы.

Рекурсия работает на компьютере и падает на камне. Стек в тысячи раз меньше.

Стек переполнился, а отказа нет. На M3 и M4 предела стека нет: сторож MPU под стеком или стек у нижней границы ОЗУ; на M33 — MSPLIM.

Выпускная сборка работает, отладочная падает. В выпускной оптимизатор убрал рекурсию, в отладочной она осталась.

Компоновщик не может посчитать стек. В графе вызовов цикл — это рекурсия.

Факториал 13 дал странное число. Переполнение 32 бит.

fib(40) считается минуту. Двойная рекурсия пересчитывает одно и то же.

66.11 Итоги

• Функция объявляется прототипом и определяется телом; без параметров — с void в скобках, иначе компилятор не проверит вызовы.
• Аргументы передаются только по значению; чтобы изменить переменную, передают её адрес.
• На Cortex-M первые четыре аргумента идут в r0–r3, остальные — через стек, результат — в r0; 64-битные значения — парами регистров, float при -mfloat-abi=hard — в s0–s15.
• Локальная переменная живёт, пока выполняется блок; static делает её вечной, но оставляет видимой только в блоке. Начальное значение static присваивается один раз.
• static на уровне файла прячет имя от других файлов.
• Локальная переменная может затенить глобальную; предупреждает только -Wshadow.
• У рекурсии обязательны условие остановки и шаг; static-переменная при рекурсии одна на все уровни.
• Каждый вызов берёт кадр стека; компоновщик считает глубину стека всей программы, но на рекурсии пишет «неизвестно».
• Двойная рекурсия fib(30) — 2 692 537 вызовов против 30 шагов цикла.
• Оптимизатор превращает хвостовую и простую рекурсию в цикл, но в отладочной сборке она остаётся.

Дальше: раздел 67 «Указатели и адресная арифметика».