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

Рекурсия и call stack

Рекурсивной функции нужны base case и движение к нему.

Что такое Рекурсия и call stack?

Рекурсивной функции нужны base case и движение к нему.

Решайте задачу через меньший экземпляр.

Важные моменты

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

Примеры кода на 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 требует O(n) времени и O(n) stack. Большой ввод нужно проверять и часто заменять итерацией.

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

C++

Итераторы и алгоритмы отделяют операцию от хранения.

Практические задания

Запустите обе версии и изменяйте их, сравнивая гарантии языков.

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