TwiddleLab / Курсы / Код

Рекурсия: функции, которые вызывают себя

Функции, которые вызывают сами себя: смотри, как растут деревья вызовов, рисуй фракталы и проходи лабиринты.

Средний уровень · уроков: 11 · Бесплатно, без аккаунта

Лучше после: Строим на Python, Алгоритмы в движении

Начать курс

Уроки

1. Функция, которая вызывает себя (5 мин): Рекурсия это функция, которая вызывает себя на уменьшенной версии задачи.
2. Базовый случай (7 мин): Базовый случай это строка, которая отвечает, не вызывая снова. Это пол.
3. Доверься меньшей задаче (7 мин): Рекурсивное мышление: сделай один маленький кусочек и доверь остаток меньшему вызову.
4. Деревья вызовов (7 мин): Функция, которая вызывает себя дважды, строит дерево вызовов: каждый кружок это один вызов.
5. Запоминай ответы: мемоизация (7 мин): Мемоизация: веди блокнот ответов. Прежде чем что-то считать, загляни в него; после запиши ответ.
6. Ханойские башни (7 мин): Рекурсивный план: чтобы перенести n дисков, убери n - 1 с дороги, перенеси самый большой, потом верни n - 1 сверху.
7. Рисуем фракталы (7 мин): Фрактал это фигура из уменьшенных копий самой себя: дерево это ствол с двумя деревьями поменьше наверху.
8. Разделяй и властвуй (7 мин): Разделяй и властвуй: раздели задачу на меньшие части, реши каждую той же функцией, объедини ответы.
9. Перебери всё: подмножества и порядки (7 мин): Полный перебор: перечисли все варианты и проверь каждый.
10. Поиск с возвратом: проходим лабиринт (7 мин): Поиск с возвратом: попробуй выбор и иди глубже; в тупике отмени последний выбор и попробуй следующий.
11. Решатель судоку (7 мин): Ограничение это правило, которое должен соблюдать любой ответ: ни одна цифра дважды в строке, столбце или блоке.

Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.