Лекции

Разбираем модель выполнения программы и стек вызовов в C++: почему при вызове doSomething () ; выполнение «возвращается» назад, что такое LIFO и кадр стека (параметры, локальные переменные, точка возврата), как return завершает текущий вызов и уничтожает локальные объекты с automatic storage duration. Закрепим понимание через трассировку входов/выходов с отступами и мини-проект с тонким main (), а затем разберём типичные ошибки в представлении работы стека.

Разбираем, из чего состоит корректная рекурсия: базовый случай (base case) и рекурсивный шаг (recursive step). Поймём, почему без достижимой базы рекурсивная функция уходит в бесконечные вызовы и заканчивается переполнением стека, как проверять сходимость (двигаемся ли к базе), и как это выглядит на примерах sum_to(), factorial() и gcd(). В конце — трассировка вызовов, мини-пример консольного меню и раздел «Типичные ошибки».

Разбираем, как осознанно выбирать между рекурсией и циклом в C++: где проще увидеть остановку (базовый случай vs условие цикла), как не потерять порядок выполнения («до вызова» и «на возврате»), и почему ошибки границ ( </ <=) и беззнаковые типы вроде std::size_t часто ломают обратные проходы. На примерах факториала, суммы 1.. n и печати строки наоборот сравним читаемость и риск ошибок, а в конце соберём практическую памятку и типичные фейлы при переводе рекурсии в цикл.

Разбираем практические ограничения рекурсии в C++: как глубина рекурсии расходует стек и приводит к stack overflow, почему число вызовов и глубина — разные величины, как «профилировать» рекурсивные функции простыми счётчиками через int &, и где рекурсивные решения проигрывают по времени из-за накладных расходов вызова. В конце — типичные ошибки: забытая база, отсутствие прогресса, тяжёлые локальные объекты и неверные ожидания вида «работает на 10 — значит, заработает и на 1'000'000».

Разбираем хвостовую рекурсию в C++: как отличать хвостовой вызов от обычного (последнее действие — return результата рекурсивного вызова), зачем нужен аккумулятор acc и нейтральный элемент ( 0 для суммы, 1 для произведения), почему хвостовая форма сама по себе не гарантирует отсутствие переполнения стека, что такое TCO (Tail Call Optimization) и почему компилятор может её не применить. Покажем, как вручную переписать хвостовую рекурсию в while/ for, и закрепим всё на мини-практике: утилита TextTools для суммы цифр в std::string с реализацией и через цикл, и через хвостовую рекурсию.