Кратко о цели: преодолеть страх, показать рекурсию как метод «разбиения на похожие подзадачи» и сформировать образ стековых вызовов и базового случая.
Подходы (методы обучения)
- Метафоры и аналогии
- Русские матрёшки: каждая внутренняя матрёшка — новый вызов; базовая матрёшка — базовый случай.
- Список дел: «делегируй часть работы другому» — объясняет передачу параметров и возврат результата.
- Правило трёх частей (шаблон)
1. базовый случай (останавливаемся),
2. рекурсивный вызов(ы) на меньшей задаче,
3. комбинирование результатов.
- Визуализация стека
- Показывать каждый вызов как фрейм: параметры, локальные переменные, куда вернётся результат.
- Демонстрировать «push» при входе в вызов и «pop» при возвращении.
- Демонстрация через отладчик/логирование
- Динамически шагать по коду, смотреть стек вызовов, распечатывать при входе/выходе.
- Постепенное усложнение
- Начать с простых линейных рекурсий, затем — ветвящихся, потом — оптимизации (мемоизация, хвостовая рекурсия).
- Практика «человек‑как‑стек»
- Студенты образуют очередь; первый вызывает второго и ждёт — наглядно показывает поведение стека.
- Сравнение с итерацией
- Показать, как рекурсивный алгоритм превращается в цикл и обратно, чтобы снять мистику.
Ключевые объяснения (коротко)
- Базовый случай — гарантия завершения. Без него — бесконечная рекурсия (stack overflow).
- Каждый вызов имеет свою копию параметров и локальных переменных — независимые фреймы.
- Количество фреймов = глубина рекурсии; для рекурсии на $n$ обычно глубина $O(n)$.
- Экспоненциальные ветвящиеся рекурсии дают число вызовов, растущее быстро (напр., для наивной Фибоначчи число вызовов ≈ $2^n$; точнее $F_{n+2}-1$).
Упражнения (с целью и подсказками)
1. Факториал (вводная)
- Цель: шаблон базы/шага, отслеживание стека.
- Задача: написать рекурсивный $fact(n)$ с базой $fact(0)=1$.
Математически: $fact(n)=n\cdot fact(n-1)$.
- Упражнение: вручную проследить вызовы для $n=4$, записать стек и возвраты.
- Подсказка: показать, что глубина вызовов = $n+1$ (включая $n=0$).
2. Сумма массива
- Цель: рекурсия над индексами, комбинирование результатов.
- Вариант: рекурсивно суммировать элементы на отрезке $[\mathrm{0..}n-1]$.
- Задача: проследить стек при $n=5$.
3. Обратная строка
- Цель: понять порядок возврата (LIFO).
- Задача: рекурсивно строить обратную строку: если строка пустая — базовый случай, иначе вернуть lastChar + reverse(rest).
- Упражнение: показать последовательность возвращаемых символов.
4. Наивный Фибоначчи и мемоизация
- Цель: показать проблему повторных вызовов и пользу кеширования.
- Задача: реализовать $fib(n)$ рекурсивно; посчитать число вызовов для $n=6$; затем добавить мемоизацию и сравнить.
- Теоретическая подсказка: число вызовов ≈ $F_{n+2}-1$ и растёт экспоненциально.
5. Двоичный поиск (рекурсивный)
- Цель: рекурсия «делим и властвуй», сложность $O(\log n)$ по глубине.
- Упражнение: проследить вызовы и показать, что глубина ≈ ${\log }_{2}n$.
6. Перестановки / генерация комбинаций
- Цель: ветвящаяся рекурсия и backtracking; понять, как создаются и откатываются изменения.
- Упражнение: генерировать все перестановки для $n=3$ и объяснить структуру стека.
7. Ханойские башни
- Цель: понятие многократных рекурсивных вызовов и их порядок.
- Математика: минимальное число перемещений = $2^n-1$.
- Упражнение: показать дерево вызовов для $n=3$.
8. Преобразование рекурсии в итерацию (и обратно)
- Цель: укрепить связь между стеком вызовов и явным стеком/циклом.
- Задача: переписать простой рекурсивный алгоритм используя явный стек; сравнить.
9. Хвостовая рекурсия и аккумулятор
- Цель: понять, как трансформировать рекурсию для уменьшения использования стека.
- Упражнение: переписать $fact$ в хвостовую форму с аккумулятором: $fac{t}_{acc}(n,acc)$ где при старте $acc=1$; проверить для $n=5$.
Классная активность (наглядный опыт)
- Карточки‑фреймы: каждый студент получает карточку с параметрами; при вызове ставит карточку в стопку и вызывает коллегу; при возврате записывает результат и убирает карточку.
- Программист‑мозг: один студент — функция, другие — рекурсивные вызовы; ведущий даёт аргумент и следит за «push/pop».
Ошибки и как их показывать
- Отсутствие базового случая: привести пример и запустить на малом $n$ до переполнения стека.
- Неправильный уменьшитель: показывать истории вызовов, где параметр не уменьшается → бесконечный цикл.
- Общая мутация состояния: показать баги при использовании общей глобальной структуры без копирования/отката.
Диагностика и отладка (коротко)
- Трассировка: печатать «enter n=…» и «exit n=…, return=…».
- Просмотр call stack в отладчике.
- Ограничение глубины рекурсии / тесты на краевых случаях (пустая структура, $n=0$, $n=1$).
Оценка усвоения
- Попросить студентов вручную «пройти» стек для небольших входов.
- Попросить переписать рекурсию в итерацию и объяснить соотношение стека и явного цикла.
- Дать задачу на нахождение сложности по числу вызовов и глубине.
Короткие памятки для учеников
- Всегда формулируй базовый случай.
- Докажи, что каждый шаг уменьшает сложность (приближает к базе).
- Нарисуй дерево вызовов или стек — это снимает страх.
Если хотите, могу прислать набор конкретных заданий с тестами и ожидаемыми трассировками для классной работы.