Неделя 4
Лекция. Синхронные вызовы на примере репки; рекуррентное задание функции и стек вызовов; рекурсивная матрёшка; кривые Коха и дракона в ColabTurtle; рекурсивная генерация двоичных последовательностей и перестановок с печатью в базовом случае. Затем корень делением пополам, бинарный поиск, lower_bound / upper_bound и поиск по ответу.
Семинар. Сначала разминка на простую рекурсию: база и шаг, обратный отсчёт, факториал, глубина против числа вызовов, быстрое возведение в степень как мост к «делим пополам». Затем бинпоиск по полуинтервалу $[l, r)$ на примерах: lower_bound / upper_bound и диапазон равных, универсальный first_true с монотонным предикатом, поиск по ответу, где одна проверка стоит линейное время. Контест «Бинарный поиск» на algo.ai.msu.ru — семь задач LeetCode; ноутбук семинаристу не сдаёте, достаточно задач на платформе. Merge и quick — позже.