Занятие 2. Функции

1 Функции

Функция это именованный фрагмент программы. Она получает параметры, выполняет действия и обычно возвращает результат.

1.1 Зачем нужны функции

Если вся программа написана в main, одинаковая логика начинает повторяться. Ошибку приходится исправлять во всех копиях, большие блоки трудно читать, отдельный шаг алгоритма нельзя проверить независимо.

Принцип DRY требует записывать каждое знание в программе один раз.

Без функции поиск максимумов двух троек повторяется:

int m1 = a;
if (b > m1) m1 = b;
if (c > m1) m1 = c;

int m2 = x;
if (y > m2) m2 = y;
if (z > m2) m2 = z;

Эту логику можно вынести в функцию:

int Max3(int a, int b, int c) {
    int m = a;
    if (b > m) m = b;
    if (c > m) m = c;
    return m;
}

int main() {
    int a, b, c, x, y, z;
    std::cin >> a >> b >> c >> x >> y >> z;
    std::cout << Max3(a, b, c) - Max3(x, y, z) << '\n';
    return 0;
}

Функции уже встречались в стандартной библиотеке:

double r = std::sqrt(2.0);
int a = std::abs(-7);
double p = std::pow(2.0, 10);
int m = std::max(3, 8);

main тоже является функцией.

1.2 Как устроена функция

В определении функции указываются тип результата, имя, параметры и тело:

int Max(int x, int y) {
    if (x > y) return x;
    return y;
}

Здесь int задает тип результата, Max является именем, а x и y являются параметрами. Оператор return вычисляет результат, передает его вызывающему коду и сразу завершает функцию.

Функции могут возвращать значения разных типов:

double Average(int a, int b) {
    return (a + b) / 2.0;
}

bool IsEven(int n) {
    return n % 2 == 0;
}

int Sign(int x) {
    if (x > 0) return 1;
    if (x < 0) return -1;
    return 0;
}

long long Cube(int x) {
    return 1LL * x * x * x;
}

В Average используется 2.0, поэтому деление является вещественным.

1.3 Вызов функции

При вызове значения аргументов копируются в параметры. Затем управление переходит в функцию. После return результат подставляется на место вызова.

Вызов является обычным выражением:

Max(a, b) * 2
Max(Max(a, b), c)

Вложенные вызовы вычисляются изнутри наружу:

int Twice(int x) {
    return 2 * x;
}

int Inc(int x) {
    return x + 1;
}

std::cout << Twice(Inc(3)) << ' '
          << Inc(Twice(3)) << '\n';

Первое выражение дает 8, второе дает 7.

1.4 return и void

Тип результата указывается перед именем. Значение после return при необходимости преобразуется к этому типу.

int F() { return 7; }
int G() { return 2.9; }

В G дробная часть отбрасывается. Строку преобразовать в int нельзя:

int H() { return "seven"; }

В функции может быть несколько операторов return. Срабатывает первый достигнутый оператор. return завершает всю функцию, а не только ближайший блок.

В функции с результатом должен быть определен результат для каждого возможного пути выполнения:

int Sign(int x) {
    if (x > 0) return 1;
    if (x < 0) return -1;
}

Для x == 0 выполнение доходит до конца без результата. Поведение программы не определено. Компилятор может предупредить: control reaches end of non-void function.

Тип void используется для функции без результата:

void PrintPositive(int x) {
    if (x <= 0) return;
    std::cout << x << '\n';
}

В такой функции return; выполняет досрочный выход без значения. Результат void-функции нельзя присвоить переменной.

1.5 Небольшая булева функция

Условие само имеет тип bool, поэтому его можно сразу вернуть:

bool IsLeap(int year) {
    return (year % 4 == 0 && year % 100 != 0)
        || year % 400 == 0;
}

Год високосный, если делится на 4, но не делится на 100, либо делится на 400.

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

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

Определение можно поместить выше main. Другой вариант: сначала написать объявление, затем определение.

int Max(int x, int y);

int main() {
    std::cout << Max(1, 2);
}

int Max(int x, int y) {
    if (x > y) return x;
    return y;
}

В объявлении имена параметров можно опустить:

int Max(int, int);

Объявлений одной функции может быть несколько, но определение должно быть ровно одно. Это правило ODR, One Definition Rule.

Если определения нет, исходный файл может скомпилироваться, но на этапе линковки появится ошибка undefined reference.

1.7 Параметры и область видимости

Параметры в определении называются формальными. Значения при вызове являются фактическими параметрами, или аргументами.

int Max(int x, int y) {
    if (x > y) return x;
    return y;
}

int a = 1;
std::cout << Max(a, -1);

При передаче по значению аргументы копируются:

void Reset(int x) {
    x = 0;
    std::cout << x << ' ';
}

int main() {
    int x = 5;
    Reset(x);
    std::cout << x << '\n';
}

Функция выводит 0, затем main выводит 5. Переменные x в двух функциях являются разными.

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

1.8 Передача по ссылке

Ссылка является вторым именем существующей переменной:

int x = 1;
int& r = x;
r = 10;
std::cout << x;

Ссылку нужно связать с переменной при создании. Ее нельзя оставить без инициализации или связать с числовым литералом.

При передаче по значению функция работает с копией. При передаче по ссылке параметр обозначает ту же переменную, что и аргумент.

void Swap(int& x, int& y) {
    int tmp = x;
    x = y;
    y = tmp;
}

int main() {
    int a = 0, b = 1;
    Swap(a, b);
    std::cout << a << ' ' << b << '\n';
}

После вызова значения равны 1 и 0. Синтаксис вызова не меняется, отличие находится в & у параметров.

1.9 Параметры по умолчанию

Параметру можно задать значение по умолчанию. Такой аргумент разрешено не передавать при вызове:

void PrintLine(int len = 10, char c = '-');

PrintLine();
PrintLine(5);
PrintLine(5, '*');

Параметры со значениями по умолчанию должны находиться в конце списка.

1.10 Перегрузка функций

В C++ функции могут иметь одинаковое имя, если различаются списки параметров:

int Max(int a, int b) {
    if (a > b) return a;
    return b;
}

double Max(double a, double b) {
    if (a > b) return a;
    return b;
}

int Max(int a, int b, int c) {
    return Max(Max(a, b), c);
}

Компилятор выбирает функцию по числу и типам аргументов. Тип результата и имена параметров не входят в сигнатуру и не позволяют создать отдельную перегрузку.

Точное совпадение типа лучше расширения. Расширение лучше остальных преобразований:

void F(int);
void F(double);
void F(char);

F(5);
F(5.0);
F('5');
F(5.0f);
F(true);

Выбираются версии int, double, char, double, int.

Если два преобразования одинаково хороши, вызов неоднозначен:

void G(long);
void G(long long);

G(0);

Литерал 0 имеет тип int. Преобразования в long и long long равноценны, поэтому компилятор сообщает об ошибке.

1.11 Рекурсия

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

int Factorial(int n) {
    if (n <= 1) return 1;
    return n * Factorial(n - 1);
}

У рекурсии есть две обязательные части:

база, которая решается сразу;
шаг, который приближает аргумент к базе.

Каждый вызов получает свою копию параметров и ожидает результат следующего вызова. Незавершенные вызовы находятся в стеке.

Если базы нет, вызовы продолжаются до переполнения стека. Даже правильная рекурсия слишком большой глубины может не поместиться в память.

Код до рекурсивного вызова выполняется при движении к базе. Код после вызова выполняется при возврате:

void Show(int n) {
    if (n == 0) return;
    std::cout << n;
    Show(n - 1);
    std::cout << n;
}

Show(3) выводит 321123.

Алгоритм Евклида записывается рекурсивно:

int Gcd(int a, int b) {
    if (b == 0) return a;
    return Gcd(b, a % b);
}

Сумма цифр неотрицательного числа:

int SumDigits(int n) {
    if (n < 10) return n;
    return n % 10 + SumDigits(n / 10);
}

Рекурсивное решение иногда многократно вычисляет одно и то же значение:

int Fib(int n) {
    if (n <= 1) return n;
    return Fib(n - 1) + Fib(n - 2);
}

Для Fib(40) получается около 331 миллиона вызовов. Итеративная версия делает 40 шагов. Рекурсивная запись может быть короче, но число вызовов нужно оценивать.

Функции могут вызывать друг друга рекурсивно. Тогда объявление одной из функций нужно поместить выше первого вызова.

1.12 Бонус: static и шаблоны

Локальная переменная со словом static создается один раз и сохраняет значение между вызовами:

int NextId() {
    static int id = 0;
    return ++id;
}

Переменная видна только внутри своего блока, но живет до конца программы.

Шаблон позволяет описать одну функцию для разных типов:

template <class T>
T Max(T a, T b) {
    if (a > b) return a;
    return b;
}

Max(3, 7);
Max(2.5, 1.5);
Max('a', 'z');

Для каждого набора типов компилятор создает подходящую версию.

Ссылка на Яндекс Контест: будет добавлена позже.