📘 Тема 1.5. Необходимый материал#

Шпаргалка по функциям, декомпозиции и рекурсии.

1. Что такое функция#

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

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

• Повторное использование. Код пишется один раз, а вызывается сколько угодно раз.
• Модульность. Программа разбивается на логические блоки, её проще читать и отлаживать.
• Одно место для изменений. Если формула поменялась, правим её в одной функции, а не в десяти местах.

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

Термины:

Заметка

main — тоже функция. Она возвращает int, и return 0; в конце сообщает системе, что программа завершилась успешно.

2. Синтаксис функции#

тип имя_функции(параметры) {
    // инструкции
    return значение;
}

• тип — тип возвращаемого значения (int, long long, double, bool, string). Если функция ничего не возвращает — void.
• имя — пишется с маленькой буквы по правилам имён переменных.
• параметры — входные данные через запятую, у каждого свой тип.
• return — возвращает значение и сразу завершает функцию.

int square(int x) {
    return x * x;
}

int main() {
    cout << square(3) << endl;            // 9
    cout << square(square(2)) << endl;    // 16
    int y = square(4) + 1;                // 17
    return 0;
}

Совет

Функция — это «чёрный ящик»: даём ей вход, получаем выход. Результат можно вывести, сохранить в переменную или подставить в другое выражение, в том числе в вызов другой функции.

3. Виды подпрограмм#

// процедура
void printHello() {
    cout << "Hello!" << endl;
}

// функция
int square(int x) {
    return x * x;
}

// рекурсия
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

4. Прототип функции#

Функцию нужно объявить до того места, где она вызывается. Если хочется написать её после main, сверху ставят прототип — объявление без тела.

#include <iostream>
using namespace std;

int square(int x);          // прототип

int main() {
    cout << square(5) << endl;
    return 0;
}

int square(int x) {         // определение
    return x * x;
}

Предупреждение

Без прототипа такой код не скомпилируется: компилятор читает файл сверху вниз и в main ещё не знает, что такое square.

5. Передача параметров по значению#

Функция получает копию аргумента. Изменения внутри функции на оригинал не влияют.

void square(int m) {
    m = m * m;
    cout << "In square: m = " << m << endl;
}

int main() {
    int n = 4;
    cout << "Before: n = " << n << endl;
    square(n);
    cout << "After: n = " << n << endl;
    return 0;
}

Before: n = 4
In square: m = 16
After: n = 4

Здесь m — копия n. Изменение m не меняет n. Чтобы функция изменила оригинал, нужна передача по ссылке или указателю — к этому мы ещё вернёмся.

Значение параметра по умолчанию#

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

int reverseNumber(int n, int reversed = 0) { ... }

reverseNumber(123);         // reversed = 0
reverseNumber(123, 5);      // reversed = 5

6. Возврат указателя#

Если функция возвращает указатель, он должен указывать на память, которая жива после выхода из функции, либо быть равным nullptr.

// ❌ ошибка: a и b — локальные копии, после выхода из функции их нет
int* maxPtr(int a, int b) {
    if (a > b) return &a;
    return &b;
}

// ✅ указатели ссылаются на переменные из main
int* maxPtr(int* a, int* b) {
    if (*a > *b) return a;
    return b;
}

int main() {
    int n = 5, m = 4;
    int* p = maxPtr(&n, &m);
    cout << *p << endl;     // 5
    return 0;
}

Внимание

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

7. Декомпозиция: пример с рядом Тейлора#

Задача: вычислить sin(x) через ряд

sin(x) = x - x³/3! + x⁵/5! - x⁷/7! + ...

Суммируем члены, пока очередной член не станет меньше точности 10⁻⁶.

Каждый следующий член получается из предыдущего: term = -term * x * x / ((2n) * (2n + 1)). Поэтому факториал в явном виде считать не нужно.

#include <iostream>
#include <cmath>
using namespace std;

double taylorSine(double x, double epsilon = 1e-6) {
    double result = 0.0;
    double term = x;
    int n = 1;
    while (fabs(term) > epsilon) {
        result += term;
        term = -term * x * x / ((2 * n) * (2 * n + 1));
        n++;
    }
    return result;
}

int main() {
    double x;
    cin >> x;
    cout << "Taylor:  " << taylorSine(x) << endl;
    cout << "Library: " << sin(x) << endl;
    return 0;
}

Совет

Признаки хорошей декомпозиции: main короткий и читается как план решения, каждая функция делает одну вещь, каждую функцию можно проверить отдельно.

8. Рекурсия#

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

У рекурсивной функции всегда две части:

1. База рекурсии — условие, при котором функция возвращает ответ сразу, без вызова себя.
2. Рекурсивный шаг — вызов функции с аргументом, который приближает к базе.

int factorial(int n) {
    if (n <= 1) {
        return 1;                       // база
    }
    return n * factorial(n - 1);        // рекурсивный шаг
}

Как это работает для n = 5:

factorial(5)
= 5 * factorial(4)
= 5 * 4 * factorial(3)
= 5 * 4 * 3 * factorial(2)
= 5 * 4 * 3 * 2 * factorial(1)
= 5 * 4 * 3 * 2 * 1
= 120

Каждый вызов ждёт результата следующего и хранится в стеке вызовов. Когда достигнута база, результаты начинают «возвращаться» вверх.

Внимание

Без базы (или если база никогда не достигается) функция вызывает себя бесконечно. Стек вызовов заканчивается, и программа падает — это переполнение стека.

9. Последовательности и рекуррентные формулы#

Последовательность — упорядоченный набор чисел a₁, a₂, a₃, ..., где n — номер члена.

Рекуррентная формула выражает член последовательности через предыдущие: aₙ = f(aₙ₋₁, aₙ₋₂, ...).

Как перевести последовательность в рекуррентную формулу#

1. Найдите закономерность: как следующий член связан с предыдущими.
2. Выразите aₙ через aₙ₋₁, aₙ₋₂, ...
3. Запишите начальные условия — они станут базой рекурсии.
4. Проверьте формулу на нескольких первых членах.

Пример: 1, 1, 2, 6, 24, 120, ... — каждый член в n раз больше предыдущего, значит, aₙ = n · aₙ₋₁, a₀ = 1. Проверка: a₃ = 3 · 2 = 6 ✅.

Совет

Рекуррентная формула переводится в код почти дословно: начальные условия → if (...) return ...;, формула → return ...; с вызовом той же функции.

10. Шаблоны рекурсивных функций#

Числа Фибоначчи#

int fibonacci(int n) {
    if (n == 0) return 0;               // база
    if (n == 1) return 1;               // база
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Предупреждение

Такая функция работает медленно: fibonacci(5) вызывает fibonacci(3) дважды, fibonacci(2) — трижды, и с ростом n число вызовов растёт экспоненциально. Для n ≤ 30 это нормально, для n = 50 — уже слишком долго. На олимпиадах в таких случаях считают циклом.

Сумма цифр числа#

int sumDigits(int n) {
    if (n < 10) return n;               // одна цифра
    return n % 10 + sumDigits(n / 10);  // последняя цифра + сумма остальных
}

НОД (алгоритм Евклида)#

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

// НОД трёх чисел
cout << gcd(gcd(a, b), c) << endl;

Переворот числа#

int reverseNumber(int n, int reversed = 0) {
    if (n == 0) return reversed;
    return reverseNumber(n / 10, reversed * 10 + n % 10);
}

Проверка на простоту (функция с bool)#

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

Заметка

Условие i * i <= n равносильно i <= sqrt(n), но работает только с целыми числами и не требует <cmath>.

11. Чтение данных с разделителями#

Если данные записаны как 15:01:40, удобно считывать разделитель в переменную типа char:

int h, m, s;
char sep;
cin >> h >> sep >> m >> sep >> s;   // sep получает ':'

cin прочитает число, затем один символ, затем снова число.

12. Типичные ошибки#

13. Шаблон программы#

#include <iostream>
using namespace std;

// вспомогательные функции

int main() {
    // ввод данных

    // вызов функций

    // вывод ответа

    return 0;
}