Алгоритмы C/C++

Рекурсия и стек вызовов в C и C++

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

Введение

Рекурсия - это решение задачи через сведение её к меньшей задаче того же вида. Каждой рекурсивной функции нужен базовый случай (base case), и каждый вызов должен приближаться к нему, иначе программа будет вызывать функцию бесконечно.

Главное

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

Как это работает

Нажимайте Шаг, чтобы следить за каждым вызовом. Новые вызовы попадают в стек вызовов, и каждый возвращает значение тому, кто его вызвал.

Примеры кода на C и C++

Запустить →

main.c

#include <stdio.h>

unsigned long long factorial(unsigned number) {
    return number < 2 ? 1 : number * factorial(number - 1);
}

int main(void) {
    printf("%llu\n", factorial(6));
}

Результат выполнения

C++

Запустить →

main.cpp

#include <iostream>

constexpr unsigned long long factorial(unsigned number) {
    return number < 2 ? 1 : number * factorial(number - 1);
}

int main() {
    constexpr auto value = factorial(6);
    std::cout << value << '\n';
}

Результат выполнения

Сравнение C и C++

Функция factorial возвращает 1, когда number меньше 2 (это базовый случай), а иначе возвращает number * factorial(number - 1). Каждый вызов занимает немного места в стеке вызовов (call stack), поэтому алгоритму нужно O(n) времени и O(n) стека. Версия на C++ помечает функцию constexpr, поэтому значение может быть вычислено ещё при компиляции. При больших входных данных нужно проверять ввод, и обычно лучше использовать цикл, а не рекурсию.

Циклы, указатели, длины и временные буферы пишутся явно.

C++

Итераторы и стандартные алгоритмы отделяют обработку от способа хранения данных.

Упражнения для практики

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

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

Попрактикуйтесь на задаче

Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.

Все задачи