Если вы поняли, как работает рекурсия, то легко поймёте «Разделяй и властвуй»!

«Разделяй и властвуй» (англ. Divide and conquer) — это способ решения задач при помощи рекурсивного разбиения их на две либо большее количество подобных задач и их решения. Как только разбиение приведёт нас к элементарно решающейся задаче — перестаём разбивать, компонуем решения каждой из элементарных задач и получаем решение нашей изначальной задачи.

Приведём простой пример из жизни. Когда нас просят порезать батон, к примеру, на 16 равных ломтиков, обычно мы разрезаем его пополам, а потом режем половинки ещё раз пополам. Получившиеся части ещё раз режем пополам и ещё раз делаем то же самое. Таким образом, мы свели задачу нарезки батона к подзадачам нарезки более мелких его частей, пока не уткнулись в базовый случай: когда нам больше не нужно продолжать резать. Как только мы решили задачу нарезки более мелких частей, мы объединили решения воедино — в 16 ломтиков.

Доставка почты тоже может относиться к алгоритмам из серии «Разделяй и властвуй». Допустим, житель посёлка Варламово заказал что-то из Китая. Когда посылка прибывает в Шереметьево, курьер распределительного центра не идёт несколько сотен километров для того, чтобы лично вручить её. Он делегирует доставку этой и ещё части посылок подзадаче: отправляет их в сортировочный центр в Самаре. Сортировочный центр Самары тоже разбивает доставку прибывших к ней посылок на подзадачи и отправляет нужную нам посылку в Сызрань. Там происходит то же самое, и вот уже наш довольный житель Варламово забирает из отделения свой заказ. Примерно таким же образом работает интернет. Ведь пакеты, которые доставили вам эту статью, тоже прошли через несколько «сортировочных центров» интернета, каждый из которых шёл к вам с этой статьей не напрямую, а делегируя её доставку своим «подзадачам».

Алгоритмы, которые при разделении задачи получают лишь одну подзадачу, тоже относят к «разделяющим и властвующим» алгоритмам. Например, бинарный поиск, на который мы посмотрели в прошлом разделе, тоже является таким алгоритмом! В нём мы «подразделяем» задачу поиска по массиву на задачу поиска по массиву в два раза меньше, а решение этой подзадачи также будет являться и решением исходной задачи. В некоторых изданиях, в том числе «Introduction to the Design and Analysis of Algorithms», такие задачи выделяют в отдельную категорию — «Уменьшай и властвуй», которая по смыслу действительно чуть лучше им подходит.

А ещё этот концепт решения задач широко используется в задачах сортировки, которые мы будем рассматривать в следующем разделе.