Как проектировать рекурсивный алгоритм и анализировать дерево вызовов?

Рекурсия решает задачу через экземпляры меньшего размера. Корректная функция имеет базовый случай, переход к нему и правило объединения результатов. Если аргумент не приближается к базе на каждой ветви, программа может исчерпать стек или бесконечно повторять состояние.

Базовый случай

Это не техническая заглушка, а минимальный экземпляр, ответ для которого известен непосредственно. Для обхода дерева базой может быть пустой узел, для факториала — ноль, для диапазона — отсутствие элементов. Несогласованная база приводит к пропуску или двойному учёту границы.

Рекурсивное предположение

При доказательстве считают, что вызов правильно решает меньшую задачу, и показывают, как текущий шаг получает верный результат. Нужно указать меру, которая строго уменьшается: длина отрезка, высота поддерева или числовой аргумент.

Дерево вызовов

Каждый узел соответствует одному вызову, рёбра — порождённым подзадачам. Линейная рекурсия даёт цепочку, двоичная без мемоизации может создать экспоненциальное число узлов. Глубина определяет максимальный объём стека, а общее число узлов — время.

Переход к итерации

Хвостовую рекурсию иногда заменяют циклом и набором переменных. Для обхода, где после возврата нужно продолжить работу, требуется явный стек кадров. Такая замена раскрывает, какие данные скрыто хранит среда выполнения: аргументы, локальное состояние и адрес продолжения.

Разбор примера

Нарисуйте дерево вычисления небольшого числа Фибоначчи, отметьте повторные подзадачи и сравните с таблицей уже найденных значений. Затем оцените глубину и число вызовов. На устной части отделяйте красоту рекурсивной формулы от эффективности конкретной реализации.

Рекурсивный контракт уменьшается вместе с задачей

Быстрое возведение в степень делит показатель пополам. Для чётного n достаточно один раз вычислить aⁿ⁄² и возвести результат в квадрат; повторный рекурсивный вызов с теми же аргументами уничтожил бы логарифмическое преимущество.

def fast_power(base: int, exponent: int) -> int:
    if exponent < 0:
        raise ValueError("non-negative exponent required")
    if exponent == 0:
        return 1
    half = fast_power(base, exponent // 2)
    squared = half * half
    return squared if exponent % 2 == 0 else squared * base

assert fast_power(3, 13) == 3 ** 13

Глубина стека равна O(log n), потому что показатель уменьшается вдвое. Доказательство проводится индукцией по n с раздельными случаями чётности. Для огромных показателей и ограниченной разрядности обычно добавляют вычисление по модулю.

Практика: дерево вызовов и итеративный двойник

Нарисуйте дерево вызовов для показателей 13 и 16, отмечая возвращаемое значение. Добавьте счётчик умножений и сравните с простым повторением n раз. Затем реализуйте итеративный вариант бинарного возведения в степень, поддерживая инвариант result × base^exponent = исходное значение. Проверьте нулевой показатель, основания 0, 1 и −2. Отдельно сформулируйте, почему выражение 0⁰ требует решения на уровне контракта.