Метод «разделяй и властвуй» делит задачу на независимые меньшие задачи того же вида, решает каждую рекурсивно и объединяет ответы.

Три шага

  1. Разделить: разбить задачу (обычно на две половины).
  2. Решить: рекурсивно решить каждую часть; самая маленькая часть (базовый случай) решается напрямую.
  3. Объединить: собрать общий ответ из ответов частей.

Части не пересекаются, и этим подход отличается от динамического программирования, где подзадачи повторяются.

Уровни рекурсии сортировки слиянием: каждый уровень стоит n, всего log n уровней
Уровни рекурсии сортировки слиянием: каждый уровень стоит n, всего log n уровней

Пример: максимум рекурсивно

python
def max_rec(a, lo, hi):
    if lo == hi:                          # base case: one item
        return a[lo]
    mid = (lo + hi) // 2
    left = max_rec(a, lo, mid)            # solve the left half
    right = max_rec(a, mid + 1, hi)       # solve the right half
    return max(left, right)               # combine

data = [3, 9, 2, 7, 5, 8]
print(max_rec(data, 0, len(data) - 1))

Рекуррентность T(n) = 2T(n/2) + O(1) даёт O(n), как и обычный цикл. Пример нужен только чтобы показать схему.

Быстрое возведение в степень