Перекрытие подзадач: почему рекурсия считает одно и то же

Коротко

Деление пополам работало, когда части НЕ ПЕРЕСЕКАЛИСЬ. Если же подзадачи повторяются, рекурсия считает одно и то же многократно, и цена взрывается: наивный Фибоначчи на n = 20 делает 21 891 вызов там, где разных подзадач всего 21. Лечение - запомнить ответ подзадачи. Два способа: мемоизация (та же рекурсия плюс кеш, сверху вниз) и таблица (цикл в правильном порядке, снизу вверх). Замер на движке: 21 891 вызов и 65 676 шагов у наивной версии против 39 вызовов и 236 шагов у мемоизации; у таблицы вызовов нет вовсе - это цикл, 19 итераций и 121 шаг. Главная работа здесь не в коде, а в выборе СОСТОЯНИЯ - набора параметров, который однозначно описывает подзадачу.

Если ты знаешь, чем мемоизация отличается от таблицы, и умеешь назвать состояние задачи, листай до «Теперь сам».

Как думаешь, сколько раз посчитается f(5)

Вот самая известная рекурсия на свете:

def f(n):
    if n < 2:
        return n
    return f(n - 1) + f(n - 2)

Прежде чем читать дальше, прикинь: при вызове f(20) сколько раз выполнится тело функции? Разных значений аргумента всего двадцать одно - от 0 до 20. Значит и вызовов около двадцати?

На что это похоже

Поиск дороги по городу, в котором ты каждый раз спрашиваешь прохожих заново. Один перекрёсток ты прошёл пять раз и пять раз спросил одно и то же. Записная книжка на один листок - «от этого перекрёстка до вокзала двадцать минут» - убирает всю лишнюю работу, и дорога становится прямой. Мемоизация и есть такая книжка.

Механизм: перекрытие, кеш, таблица

ДВА ВИДА РЕКУРСИИ

деление пополам (раздел 13):      подзадачи НЕ пересекаются
    сортировка слиянием: левая половина и правая - разные элементы
    каждая подзадача решается РОВНО ОДИН РАЗ

перекрывающиеся подзадачи:        одна и та же подзадача нужна многим
    f(5) требуется и для f(6), и для f(7)
    без запоминания она считается заново каждый раз

ТРИ СПОСОБА ПОСЧИТАТЬ ОДНО И ТО ЖЕ

1. НАИВНАЯ РЕКУРСИЯ        цена экспоненциальная
2. МЕМОИЗАЦИЯ (сверху вниз) рекурсия + кеш: перед счётом смотрим в кеш,
                            после счёта пишем в кеш
3. ТАБЛИЦА (снизу вверх)    цикл, который заполняет ответы в таком порядке,
                            что нужное уже посчитано

ЗАМЕР НА ДВИЖКЕ КУРСА, f(n) = f(n−1) + f(n−2)
(у движка жёсткий предел - 300 000 шагов; «не уложился» значит упёрлись в него)

          наивная рекурсия      мемоизация        таблица (цикл)
   n     вызовов    шагов     вызовов   шагов    итераций   шагов
  10         177      534         19     146          9       61
  20      21 891   65 676         39     236         19      121
  25   не уложился             49     281         24      151
  30   не уложился             59     326         29      181

разных подзадач при n = 20 - двадцать одна. Наивная рекурсия вызывает тело
21 891 раз, то есть примерно в тысячу раз больше, чем нужно.
У таблицы вызовов функции нет совсем: это цикл, и итераций в нём n − 1

СОСТОЯНИЕ - главное слово темы

состояние = набор параметров, однозначно описывающий подзадачу
    у Фибоначчи это одно число n
    у рюкзака - «сколько предметов рассмотрено» и «сколько места осталось»
    у двух строк - «сколько символов взято из первой и из второй»

число состояний × цена одного перехода = цена всего алгоритма

Правило

Если подзадачи ПЕРЕКРЫВАЮТСЯ, наивная рекурсия считает их заново и цена растёт экспоненциально. Лечение - запомнить ответ каждой подзадачи один раз. Мемоизация: та же рекурсия плюс кеш, порядок получается сам. Таблица: цикл, заполняющий ответы снизу вверх в порядке, при котором нужное уже готово. Цена обоих способов одна и та же и считается так: ЧИСЛО СОСТОЯНИЙ умножить на цену ОДНОГО ПЕРЕХОДА. Поэтому вся работа при решении - подобрать состояние: минимальный набор параметров, который однозначно описывает подзадачу. Лишний параметр умножает цену, недостающий делает ответ неверным.

Разбор: дерево вызовов и почему оно двоичное

Посмотрим, откуда берутся 21 891 вызов. Нарисуем начало дерева для f(5):

                    f(5)
            f(4)            f(3)
        f(3)    f(2)    f(2)    f(1)
     f(2) f(1) f(1)f(0) f(1)f(0)
  f(1)f(0)

f(3) появилось дважды, f(2) - трижды, f(1) - пять раз. Каждый узел порождает двух детей, но дерево НЕПОЛНОЕ: ветка f(n−2) короче ветки f(n−1), и до глубины n доходит не всё. Поэтому узлов не 2^n, а заметно меньше: точное число вызовов равно 2·f(n+1) − 1, то есть растёт как 1.618^n (золотое сечение). Сверим с замером: 2·f(21) − 1 = 2·10946 − 1 = 21 891 - ровно столько, сколько насчитал счётчик. Для сравнения, 2^20 = 1 048 576 - в 48 раз больше, так что «двоичное дерево» здесь сильно завысило бы оценку.

Теперь та же рекурсия с кешем:

kesh = [0] * 60

def f(n):
    if n < 2:
        return n
    if kesh[n] > 0:
        return kesh[n]
    kesh[n] = f(n - 1) + f(n - 2)
    return kesh[n]

Вызовов стало 39 при n = 20, и это число раскладывается точно: 19 вызовов для состояний 2...20, каждое считается один раз, плюс 20 вызовов, которые сразу вернулись - из кеша или из базы (n < 2). Итого 19 + 20 = 39 = 2n − 1. Главное - зависимость стала ЛИНЕЙНОЙ, и это видно в замере на n = 25 и n = 30, где наивная версия уже не укладывается в предел шагов.

Про if kesh[n] > 0 стоит сказать отдельно, потому что ниже в уроке есть прямо противоположное предупреждение: ноль плохой признак «ещё не считали». Здесь он безопасен по двум причинам: состояния 0 и 1 обрабатывает база и до кеша не доходят, а f(n) при n >= 2 строго положительно. Как только появится задача, где честный ответ может быть нулём, признак придётся делать отдельным - массивом флагов или значением −1.

ВАЖНО: кеш проверяется ДО вычисления и пишется ПОСЛЕ
если поменять местами - кеш не сработает, а ошибки не будет:
программа останется верной и останется экспоненциальной

Разбор: та же задача снизу вверх

У Фибоначчи порядок очевиден - по возрастанию n:

a = 0           # f(0)
b = 1           # f(1)
i = 1
while i < n:
    c = a + b
    a = b
    b = c
    i = i + 1
# после цикла b = f(n) при n >= 1; при n = 0 цикл не выполнится,
# и ответ надо взять из a

Здесь нет ни рекурсии, ни кеша на n элементов - только две переменные. Это второй подарок таблицы: когда порядок известен, часто видно, что из всей таблицы нужны лишь последние её клетки. Про экономию памяти - отдельная глава этого раздела.

                      мемоизация            таблица
порядок вычисления    получается сам        надо придумать
память                все состояния         иногда хватает двух строк
стек                  глубина рекурсии      нет
удобно, когда         состояний много, но   нужны все состояния
                      нужны далеко не все   или важна память

Выбор между ними - вопрос удобства, а не правильности: цена одинаковая. Мемоизация выигрывает, когда состояний формально много, а достижимых мало (так бывает у игр и у задач с ограничениями); таблица - когда нужны все и хочется сэкономить память и стек.

Что ломается без этого

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

Зачем это в работе

Мемоизация в прикладном коде встречается чаще, чем таблицы, и почти всегда под другим именем: кеширование результата функции. В Python это functools.lru_cache, в вебе - кеш ответа по ключу запроса, в сборщиках - кеш по хешу входных файлов. Условие применимости везде одно и то же, и его стоит проговаривать вслух: функция должна быть ЧИСТОЙ - на одних аргументах всегда давать один ответ. Как только внутри появляется чтение времени, случайного числа или изменяемого состояния, кеш превращается в источник плавающих дефектов. Второе практическое следствие - про диагностику: если рекурсивная функция работает подозрительно долго, первый вопрос не «как её ускорить», а «сколько разных значений аргументов у неё бывает». Если разных мало, а вызовов много - это перекрытие, и лечится оно одной строкой кеша, а не переписыванием.

Теперь сам

Функция считает число способов подняться по лестнице из n ступеней, если за шаг можно перепрыгнуть одну или две:

def sposoby(n):
    if n <= 1:
        return 1
    return sposoby(n - 1) + sposoby(n - 2)

Сколько разных состояний у этой задачи и сколько вызовов сделает наивная версия при n = 20?

Ответ. Состояние одно - число оставшихся ступеней, то есть разных состояний n + 1 = 21 (от 0 до 20).

Вызовов же будет столько же, сколько у Фибоначчи, потому что это ТОТ ЖЕ рекуррентный переход - 21 891. Проверяется счётчиком в одну строку:

vyzovy = [0]

def sposoby(n):
    vyzovy[0] = vyzovy[0] + 1
    ...

Заметь, что задача про лестницу и задача про Фибоначчи - одна и та же задача с разной обёрткой: различаются только базовые случаи (sposoby(0) = 1, а f(0) = 0). Это типичная ситуация: в динамическом программировании условие задачи почти всегда переодето, и первый шаг решения - раздеть его до состояния и перехода.

Главное

Деление пополам работает, когда подзадачи НЕ пересекаются. Если пересекаются, наивная рекурсия считает их заново и цена растёт экспоненциально: наивный Фибоначчи при n = 20 вызывает тело 21 891 раз (ровно 2·f(21) − 1) при двадцати одном разном состоянии, а на n = 25 уже не укладывается в предел шагов. Лечение - запомнить ответ подзадачи: мемоизация (рекурсия плюс кеш, 39 вызовов) или таблица снизу вверх (20). Цена обоих способов = ЧИСЛО СОСТОЯНИЙ × цена одного перехода, поэтому главная работа - выбрать состояние: лишний параметр умножает цену, недостающий делает ответ неверным. Кеш проверяют ДО вычисления и пишут ПОСЛЕ; признак «ещё не считали» не должен совпадать с возможным честным ответом.