Рекурсія та backtracking

Рекурсія — це насправді дві ідеї, які випадково мають одну назву. З погляду алгоритмів це стратегія: звести задачу до меншої версії тієї самої задачі, розв'язати меншу — і зібрати відповідь. Так працюють divide-and-conquer алгоритми: mergesort, quicksort, обхід дерев. З погляду коду це просто функція, яка викликає сама себе. Обидва погляди описують те саме з різних боків: рекурсивна функція — це рекурсивний алгоритм, записаний у коді.

У цій статті розберемо, з чого складається будь-яка рекурсивна функція, напишемо кілька класичних алгоритмів і дійдемо до backtracking: універсального шаблону перебору, на якому тримається половина задач із співбесід.

1. Дві частини будь-якої рекурсії

Кожна коректна рекурсивна функція складається рівно з двох частин.

Базовий випадок (base case) — найпростіший варіант задачі, який розв'язується напряму, без рекурсії. Зазвичай це «порожнеча» або нуль: порожній список, рядок довжини 0, число 0.

Рекурсивний крок — розбиває поточну задачу на одну або кілька строго менших, розв'язує їх рекурсивними викликами і збирає результат.

Слово «строго» тут ключове. Якщо рекурсивний крок не зменшує задачу, рекурсія ніколи не дійде до базового випадку — і Python впаде з RecursionError (дефолтний ліміт — 1000 фреймів).

Коли варто брати рекурсію:

• задача природно рекурсивна: divide-and-conquer, обхід дерева, парсинг виразів;

• дані природно рекурсивні: файлова система (директорії містять директорії), зв'язний список (вузол плюс решта), parse tree;

• ви хочете писати в функціональному стилі: незмінні структури, чисті функції. Такий код набагато легше аналізувати і доводити коректним, ніж еквівалентні цикли зі спільним станом.

Ціна — один stack frame на кожен виклик. Глибина в кілька тисяч фреймів — і стек закінчився. У такому режимі правильний інструмент — явний цикл або явний стек як структура даних.

2. Розминка: степінь за O(log n)

Порахуємо xⁿ. Наївна рекурсія перекладає означення xⁿ = x · xⁿ⁻¹ напряму:

def power_slow(x, n):
    if n == 0:
        return 1
    return x * power_slow(x, n - 1)

Коректно, але кожен виклик зменшує n лише на одиницю. Можна краще. Кожен парний крок ділить степінь навпіл, кожен непарний робить його парним:

def power(x, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        half = power(x, n // 2)   # рахуємо x^(n/2) ОДИН раз
        return half * half
    return x * power(x, n - 1)

Два послідовні кроки зменшують n щонайменше вдвічі, тому викликів O(log n).

3. Ханойські вежі

Класика: три стрижні — Source, Auxiliary, Destination — і n дисків різного розміру на Source, більші знизу. Треба перенести всі диски на Destination. Правила: за раз рухаємо один диск, більший диск не можна класти на менший.

Планувати всю послідовність ходів у лоб — безнадійно. Рекурсивний погляд згортає задачу до трьох кроків. Щоб перенести n дисків із src на dst:

1. перенести верхні n−1 дисків із src на aux (рекурсивний виклик);

2. перенести найбільший диск із src на dst (один хід);

3. перенести n−1 дисків із aux на dst (рекурсивний виклик).

Весь розв'язок — чотири рядки:

def hanoi(n, src, dst, aux):
    if n == 0:
        return
    hanoi(n - 1, src, aux, dst)
    print(f"Move disk {n}: {src} -> {dst}")
    hanoi(n - 1, aux, dst, src)

Чому це коректно? Під час кроку 1 найбільший диск лежить на дні src і більший за всі диски, які ми переставляємо, тому нікому не заважає. На кроці 2 dst порожній — хід легальний. На кроці 3 найбільший диск уже на dst і знову не накладає жодних обмежень.

Кількість ходів: T(n) = 2·T(n−1) + 1 = 2ⁿ − 1. І це не недолік алгоритму — менше не можна в принципі: щоб легально зрушити найбільший диск, спочатку треба звільнити все над ним. Ханойські вежі — задача, яка експоненційна за своєю природою.

4. Генерація комбінаторних об'єктів

Багато задач зводяться до перебору: підмножини, перестановки, комбінації. Усі вони генеруються одним рекурсивним скелетом — змінюється лише те, що означає «зробити ще один вибір».

Підмножини. Кожну підмножину множини {0, …, n−1} кодуємо бітовим вектором: біт i = 1 означає «елемент i включений». На кожній позиції рекурсивно обираємо 0 або 1 — і 2ⁿ листків дерева рекурсії дають рівно 2ⁿ підмножин:

def gen_subsets(prefix, n):
    if len(prefix) == n:
        print([i for i, bit in enumerate(prefix) if bit == 1])
        return
    gen_subsets(prefix + [0], n)   # не беремо елемент
    gen_subsets(prefix + [1], n)   # беремо елемент

5. Шаблон backtracking

Усі такі алгоритми — варіації одного шаблону: на кожному кроці перебираємо кандидатів, робимо вибір, рекурсуємо і скасовуємо вибір перед наступною спробою. «Скасувати» — це і є «back» у backtracking.

def backtrack(state):
    if is_complete(state):
        process(state)                # знайшли розв'язок
        return
    for choice in candidates(state):
        if is_valid(state, choice):
            apply(state, choice)      # робимо вибір
            backtrack(state)          # рекурсія
            undo(state, choice)       # скасовуємо вибір

У цей шаблон вкладаються N ферзів, судоку, розфарбування графа, генерація дужкових послідовностей — і половина hard-задач на LeetCode.

Головне правило backtracking: відсікайте рано, відсікайте часто. Гілка, відкинута перевіркою is_valid на глибині d, забирає з собою все піддерево під нею — потенційно мільйони вузлів. Уся гра — у тому, щоб відсікати погані гілки якомога вище в дереві.