TwiddleLab / Код / Рекурсия: функции, которые вызывают себя
Разделяй и властвуй
Что ты узнаешь
- Разделяй и властвуй: раздели задачу на меньшие части, реши каждую той же функцией, объедини ответы.
- Сортировка слиянием делит список пополам, сортирует каждую половину, доверяя себе, потом сливает. Базовый случай: 0 или 1 элемент.
- Быстрая сортировка вместо этого делит вокруг опорного; двоичный поиск оставляет только одну половину; турнир находит самое большое.
- Деревья решений в ИИ делят данные так же: задай вопрос, потом сделай то же для каждой части.
Как идёт урок
Раньше сортировка шла слиянием снизу вверх. Теперь сверху вниз: разрежь стопку пополам.
Режь, пока резать будет нечего.
Сортировка слиянием как рекурсия: деление вниз, слияние вверх.
Пройди по шагам рядом с кодом.
merge_sort не может сливать, пока обе половины не вернутся отсортированными, а каждая половина ждёт свои половины. Поэтому вызовы спускаются до отдельных карт, а слияния происходят по пути обратно вверх.
Разделяй и властвуй.
Разделяй: раздели задачу на меньшие части того же вида.
Властвуй: реши каждую часть той же функцией. Доверься ей, как в уроке «Доверься меньшей задаче». Достаточно маленькие части это базовые случаи.
Объединяй: сложи ответы вместе. В сортировке слиянием объединение это слияние двух отсортированных половин.
Напиши сортировку слиянием в пять строк.
merge(a, b) уже готова наверху. Раздели, отсортируй каждую половину, слей.
Слияние двух неотсортированных половин даёт кашу, поэтому каждую половину сначала нужно отсортировать, самой merge_sort. Вызов на том же списке (merge_sort(items)) никогда бы не уменьшался.
Быстрая сортировка вручную: дели вокруг опорного.
Первая карта стопки это опорная. Меньшие карты влево, большие вправо. Потом каждая сторона так же.
Сетка турнира: найди самое большое из 16 в стиле турнира.
Нажимай на большее число в каждом матче. Быстро и без промахов.
ИИ делает так же: дели кучу фруктов, пока в каждой кучке не останется один вид.
Выбери смешанную кучку, потом вопрос. С каждой частью поступай так же.
Рекурсивный двоичный поиск: найди 63.
Каждый вызов проверяет середину оставшегося, потом вызывает себя на одной половине. Нажимай на карту, которую проверяет каждый вызов.
Двоичный поиск делит список, потом решает только ту половину, где может быть цель. Объединять нечего, поэтому нужен один вызов на уровень: около log2 от n вызовов.
Твоя сортировка слиянием на 16 картах.
Нажми «Запуск».
Предыдущий урок: Рисуем фракталы · Следующий урок: Перебираем всё: подмножества и порядки · Часть курса: Рекурсия: функции, которые вызывают себя
Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.
